YES Solver Timeout: 4 Global Timeout: 300 No parsing errors! Init Location: 0 Transitions: (~(1) + x^0)}> (~(1) + a^0), x^0 -> ((0 + x^0) + y^0), y^0 -> ((0 + y^0) + z^0), z^0 -> ((0 + a^0) + z^0)}> Fresh variables: Undef variables: Abstraction variables: Exit nodes: Accepting locations: Asserts: Preprocessed LLVMGraph Init Location: 0 Transitions: (~(1) + x^0)}> (~(1) + a^0), x^0 -> ((0 + x^0) + y^0), y^0 -> ((0 + y^0) + z^0), z^0 -> ((0 + a^0) + z^0)}> Fresh variables: Undef variables: Abstraction variables: Exit nodes: Accepting locations: Asserts: ************************************************************* ******************************************************************************************* *********************** WORKING TRANSITION SYSTEM (DAG) *********************** ******************************************************************************************* Init Location: 0 Graph 0: Transitions: Variables: Graph 1: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: x^0, a^0, y^0, z^0 Precedence: Graph 0 Graph 1 Map Locations to Subgraph: ( 0 , 0 ) ( 1 , 1 ) ******************************************************************************************* ******************************** CHECKING ASSERTIONS ******************************** ******************************************************************************************* Proving termination of subgraph 0 Proving termination of subgraph 1 Checking unfeasibility... Time used: 0.004168 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000908s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002367s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.008961s Time used: 0.00884 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.002707s Time used: 0.002258 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.010220s Time used: 0.010005 Improving Solution with cost 1 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.015431s Time used: 0.015428 LOG: SAT solveNonLinear - Elapsed time: 0.025651s Cost: 1; Total time: 0.025433 Failed at location 1: x^0 <= 0 Before Improving: Quasi-invariant at l1: x^0 <= 0 Optimizing invariants... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002802s Remaining time after improvement: 0.999357 Termination implied by a set of quasi-invariant(s): Quasi-invariant at l1: x^0 <= 0 [ Invariant Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: -1 + x^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> [ Termination Graph ] Strengthening and disabling transitions... > It's unfeasible. Removing transition: -1 + x^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> New Graphs: Calling Safety with literal x^0 <= 0 and entry LOG: CALL check - Post:x^0 <= 0 - Process 1 * Exit transition: * Postcondition : x^0 <= 0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000223s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000248s INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: x^0 <= 0 , Narrowing transition: -1 + x^0, rest remain the same}> LOG: Narrow transition size 1 Narrowing transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> LOG: Narrow transition size 1 invGraph after Narrowing: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: x^0, a^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000396s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001619s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.005946s Time used: 0.005857 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.002750s Time used: 0.002284 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.001937s Time used: 4.00173 Solving with 2 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.022739s Time used: 4.01189 Solving with 3 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.917717s Time used: 0.912178 Improving Solution with cost 3 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.088189s Time used: 0.088187 LOG: SAT solveNonLinear - Elapsed time: 1.005906s Cost: 3; Total time: 1.00036 Failed at location 1: 1 + a^0 + x^0 + y^0 + z^0 <= 0 Failed at location 1: 1 + x^0 <= a^0 Failed at location 1: 0 <= 1 + z^0 Before Improving: Quasi-invariant at l1: 1 + a^0 + x^0 + y^0 + z^0 <= 0 Quasi-invariant at l1: 1 + x^0 <= a^0 Quasi-invariant at l1: 0 <= 1 + z^0 Optimizing invariants... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.004573s Quasi-invariant improved LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001261s Remaining time after improvement: 0.996795 Termination implied by a set of quasi-invariant(s): Quasi-invariant at l1: a^0 + x^0 + y^0 + z^0 <= 1 Quasi-invariant at l1: 1 + x^0 <= a^0 Quasi-invariant at l1: 0 <= 1 + z^0 [ Invariant Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): -1 + x^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> [ Termination Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): -1 + x^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Ranking function: x^0 New Graphs: Calling Safety with literal a^0 + x^0 + y^0 + z^0 <= 1 and entry LOG: CALL check - Post:a^0 + x^0 + y^0 + z^0 <= 1 - Process 2 * Exit transition: * Postcondition : a^0 + x^0 + y^0 + z^0 <= 1 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000243s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000280s Calling Safety with literal 1 + x^0 <= a^0 and entry LOG: CALL check - Post:1 + x^0 <= a^0 - Process 3 * Exit transition: * Postcondition : 1 + x^0 <= a^0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000244s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000275s Calling Safety with literal 0 <= 1 + z^0 and entry LOG: CALL check - Post:0 <= 1 + z^0 - Process 4 * Exit transition: * Postcondition : 0 <= 1 + z^0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000235s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000261s INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: 1 + x^0 <= a^0 , a^0 + x^0 + y^0 + z^0 <= 1 , 0 <= 1 + z^0 , Narrowing transition: -1 + x^0, rest remain the same}> LOG: Narrow transition size 3 Narrowing transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> LOG: Narrow transition size 3 invGraph after Narrowing: Transitions: -1 + x^0, rest remain the same}> -1 + x^0, rest remain the same}> -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: x^0, a^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002190s Ranking function: -6 + 3*a^0 New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + x^0, rest remain the same}> -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001031s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.012866s Piecewise ranking function: min((~(3) / 2) + 4*a^0,(~(3) / 2) + (5 / 2)*a^0 + (3 / 2)*x^0) New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000527s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002393s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.005927s Time used: 0.005811 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.004356s Time used: 0.003682 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.001426s Time used: 4.00105 Solving with 2 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.003572s Time used: 4.00083 Solving with 3 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 1.011079s Time used: 1.0001 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.021006s Time used: 0.016609 Improving Solution with cost 1 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.030145s Time used: 0.030142 LOG: SAT solveNonLinear - Elapsed time: 0.051150s Cost: 1; Total time: 0.046751 Quasi-ranking function: 50000 + a^0 New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000617s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.003077s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.008499s Time used: 0.008369 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.005642s Time used: 0.005098 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.002140s Time used: 4.00173 Solving with 2 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.039867s Time used: 4.03688 Solving with 3 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 1.011113s Time used: 1.00004 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.024536s Time used: 0.019157 Improving Solution with cost 1 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.025979s Time used: 0.025977 LOG: SAT solveNonLinear - Elapsed time: 0.050515s Cost: 1; Total time: 0.045134 Quasi-ranking function: 50000 + a^0 + z^0 New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000698s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.003091s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.009431s Time used: 0.009276 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.006283s Time used: 0.005542 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.002698s Time used: 4.00224 Solving with 2 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.004139s Time used: 4.00087 Solving with 3 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 1.011259s Time used: 1.0001 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.026927s Time used: 0.021254 Improving Solution with cost 1 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.034506s Time used: 0.034503 LOG: SAT solveNonLinear - Elapsed time: 0.061434s Cost: 1; Total time: 0.055757 Quasi-ranking function: 50000 + a^0 + y^0 + z^0 New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000766s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.009062s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.008577s Time used: 0.008283 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.006858s Time used: 0.006077 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.002722s Time used: 4.00222 Solving with 2 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.004244s Time used: 4.00083 Solving with 3 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 1.011114s Time used: 1.00066 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.025465s Time used: 0.02134 Improving Solution with cost 1 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.035793s Time used: 0.035791 LOG: SAT solveNonLinear - Elapsed time: 0.061259s Cost: 1; Total time: 0.057131 Quasi-ranking function: 50000 - a^0 + x^0 + y^0 + 2*z^0 New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001021s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.023057s Trying to remove transition: -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.015039s Time used: 0.014587 Trying to remove transition: -1 + x^0, rest remain the same}> Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.012502s Time used: 0.011869 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.002907s Time used: 4.00227 Solving with 2 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 4.009955s Time used: 4.00097 Solving with 3 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 1.010447s Time used: 1.00005 Solving with 1 template(s). LOG: CALL solveNonLinearGetFirstSolution LOG: RETURN solveNonLinearGetFirstSolution - Elapsed time: 0.025539s Time used: 0.023612 Improving Solution with cost 1 ... LOG: CALL solveNonLinearGetNextSolution LOG: RETURN solveNonLinearGetNextSolution - Elapsed time: 0.037912s Time used: 0.03791 LOG: SAT solveNonLinear - Elapsed time: 0.063450s Cost: 1; Total time: 0.061522 Quasi-ranking function: 50000 + x^0 + 2*y^0 New Graphs: Transitions: -1 + x^0, rest remain the same}> -1 + a^0, x^0 -> x^0 + y^0, y^0 -> y^0 + z^0, z^0 -> a^0 + z^0, rest remain the same}> Variables: a^0, x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002954s Ranking function: (5000350005 / 25001) + (1 / 25001)*x^0 New Graphs: Program Terminates