/export/starexec/sandbox/solver/bin/starexec_run_termcomp17 /export/starexec/sandbox/benchmark/theBenchmark.smt2 /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES Solver Timeout: 4 Global Timeout: 300 Maximum number of concurrent processes: 900 No parsing errors! Init Location: 0 Transitions: ((0 + x^0) + z^0), z^0 -> (~(1) + z^0)}> ((0 + x^0) + y^0), y^0 -> (~(1) + y^0)}> Fresh variables: Undef variables: Abstraction variables: Exit nodes: Accepting locations: Asserts: Preprocessed LLVMGraph Init Location: 0 Transitions: ((0 + x^0) + z^0), z^0 -> (~(1) + z^0)}> ((0 + x^0) + y^0), y^0 -> (~(1) + y^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: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, z^0, y^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.003642 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000833s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002687s [26785 : 26787] [26785 : 26788] Successful child: 26787 [ 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: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: x^0 + y^0, y^0 -> -1 + y^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 It's unfeasible. Removing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> New Graphs: LOG: CALL check - Post:x^0 <= 0 - Process 1 * Exit transition: * Postcondition : x^0 <= 0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000281s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000346s INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: x^0 <= 0 , Narrowing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: Narrow transition size 1 Narrowing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> LOG: Narrow transition size 1 invGraph after Narrowing: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, z^0, y^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000790s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002863s [26785 : 26792] [26785 : 26793] Successful child: 26792 [ Invariant Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + y^0, y^0 -> -1 + y^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): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Ranking function: 2*x^0 - y^0 New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000632s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002311s [26785 : 27159] [26785 : 27160] Successful child: 27159 [ Invariant Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + y^0, y^0 -> -1 + y^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): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Ranking function: x^0 New Graphs: [26785 : 27179] [26785 : 27180] INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: 1 + y^0 <= 0 , z^0 <= 0 , LOG: CALL check - Post:x^0 + z^0 <= 1 + y^0 - Process 2 * Exit transition: * Postcondition : x^0 + z^0 <= 1 + y^0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000479s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000568s INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: x^0 + z^0 <= 1 + y^0 , Narrowing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: Narrow transition size 3 Narrowing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> LOG: Narrow transition size 3 invGraph after Narrowing: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, z^0, y^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.003547s Ranking function: -2 + 2*z^0 New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.002815s Ranking function: 1 + y^0 New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001983s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.019891s [26785 : 27202] [26785 : 27203] Successful child: 27203 Ranking function: 2*x^0 - y^0 Ranking function and negation of Quasi-Invariant applied New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001209s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.005304s [26785 : 27222] [26785 : 27223] Successful child: 27223 Ranking function: x^0 - y^0 + z^0 Ranking function and negation of Quasi-Invariant applied New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000573s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001992s [26785 : 27242] [26785 : 27243] Successful child: 27242 [ Invariant Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility It's unfeasible. Removing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> [ Termination Graph ] Strengthening and disabling transitions... > It's unfeasible. Removing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> New Graphs: LOG: CALL check - Post:1 + y^0 <= 0 - Process 3 * Exit transition: * Postcondition : 1 + y^0 <= 0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000475s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000566s INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: 1 + y^0 <= 0 , It's unfeasible. Removing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> It's unfeasible. Removing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Narrowing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: Narrow transition size 1 It's unfeasible. Removing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> It's unfeasible. Removing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Narrowing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> LOG: Narrow transition size 1 invGraph after Narrowing: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, z^0, y^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001567s Ranking function: y^0 New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000538s LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001965s [26785 : 27303] [26785 : 27304] Successful child: 27303 [ Invariant Graph ] Strengthening and disabling transitions... LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: CALL solverLinear in Graph for feasibility LOG: RETURN solveLinear in Graph for feasibility Strengthening transition (result): x^0 + y^0, y^0 -> -1 + y^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): x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Ranking function: x^0 New Graphs: LOG: CALL check - Post:1 + y^0 + z^0 <= 0 - Process 4 * Exit transition: * Postcondition : 1 + y^0 + z^0 <= 0 LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000517s > Postcondition is not implied! LOG: RETURN check - Elapsed time: 0.000603s INVARIANTS: 1: Quasi-INVARIANTS to narrow Graph: 1: 1 + y^0 + z^0 <= 0 , Narrowing transition: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> LOG: Narrow transition size 1 Narrowing transition: x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> LOG: Narrow transition size 1 invGraph after Narrowing: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> x^0 + y^0, y^0 -> -1 + y^0, rest remain the same}> Variables: x^0, z^0, y^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.001828s Ranking function: y^0 New Graphs: Transitions: x^0 + z^0, z^0 -> -1 + z^0, rest remain the same}> Variables: x^0, y^0, z^0 Checking conditional termination of SCC {l1}... LOG: CALL solveLinear LOG: RETURN solveLinear - Elapsed time: 0.000978s Ranking function: y^0 + z^0 New Graphs: Program Terminates