/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) Overlay + Local Confluence [EQUIVALENT, 8 ms] (2) QTRS (3) DependencyPairsProof [EQUIVALENT, 0 ms] (4) QDP (5) DependencyGraphProof [EQUIVALENT, 0 ms] (6) AND (7) QDP (8) UsableRulesProof [EQUIVALENT, 0 ms] (9) QDP (10) QReductionProof [EQUIVALENT, 0 ms] (11) QDP (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) RemovalProof [SOUND, 0 ms] (20) QDP (21) NonInfProof [EQUIVALENT, 46 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: digits -> d(0) d(x) -> if(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) if(true, x) -> cons(x, d(s(x))) if(false, x) -> nil le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) Q is empty. ---------------------------------------- (1) Overlay + Local Confluence (EQUIVALENT) The TRS is overlay and locally confluent. By [NOC] we can switch to innermost. ---------------------------------------- (2) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: digits -> d(0) d(x) -> if(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) if(true, x) -> cons(x, d(s(x))) if(false, x) -> nil le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) ---------------------------------------- (3) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (4) Obligation: Q DP problem: The TRS P consists of the following rules: DIGITS -> D(0) D(x) -> IF(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) D(x) -> LE(x, s(s(s(s(s(s(s(s(s(0)))))))))) IF(true, x) -> D(s(x)) LE(s(x), s(y)) -> LE(x, y) The TRS R consists of the following rules: digits -> d(0) d(x) -> if(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) if(true, x) -> cons(x, d(s(x))) if(false, x) -> nil le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (5) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x), s(y)) -> LE(x, y) The TRS R consists of the following rules: digits -> d(0) d(x) -> if(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) if(true, x) -> cons(x, d(s(x))) if(false, x) -> nil le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (8) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (9) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x), s(y)) -> LE(x, y) R is empty. The set Q consists of the following terms: digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (10) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LE(s(x), s(y)) -> LE(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (12) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *LE(s(x), s(y)) -> LE(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (13) YES ---------------------------------------- (14) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x) -> D(s(x)) D(x) -> IF(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) The TRS R consists of the following rules: digits -> d(0) d(x) -> if(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) if(true, x) -> cons(x, d(s(x))) if(false, x) -> nil le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) The set Q consists of the following terms: digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (15) UsableRulesProof (EQUIVALENT) As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (16) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x) -> D(s(x)) D(x) -> IF(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) The TRS R consists of the following rules: le(0, y) -> true le(s(x), s(y)) -> le(x, y) le(s(x), 0) -> false The set Q consists of the following terms: digits d(x0) if(true, x0) if(false, x0) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (17) QReductionProof (EQUIVALENT) We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. digits d(x0) if(true, x0) if(false, x0) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x) -> D(s(x)) D(x) -> IF(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) The TRS R consists of the following rules: le(0, y) -> true le(s(x), s(y)) -> le(x, y) le(s(x), 0) -> false The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) RemovalProof (SOUND) In the following pairs the term without variables s(s(s(s(s(s(s(s(s(0))))))))) is replaced by the fresh variable x_removed. Pair: D(x) -> IF(le(x, s(s(s(s(s(s(s(s(s(0)))))))))), x) Positions in right side of the pair: *[0,1]The new variable was added to all pairs as a new argument[CONREM]. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: IF(true, x, x_removed) -> D(s(x), x_removed) D(x, x_removed) -> IF(le(x, x_removed), x, x_removed) The TRS R consists of the following rules: le(0, y) -> true le(s(x), s(y)) -> le(x, y) le(s(x), 0) -> false The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) NonInfProof (EQUIVALENT) The DP Problem is simplified using the Induction Calculus [NONINF] with the following steps: Note that final constraints are written in bold face. For Pair IF(true, x, x_removed) -> D(s(x), x_removed) the following chains were created: *We consider the chain D(x2, x3) -> IF(le(x2, x3), x2, x3), IF(true, x4, x5) -> D(s(x4), x5) which results in the following constraint: (1) (IF(le(x2, x3), x2, x3)=IF(true, x4, x5) ==> IF(true, x4, x5)_>=_D(s(x4), x5)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (le(x2, x3)=true ==> IF(true, x2, x3)_>=_D(s(x2), x3)) We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on le(x2, x3)=true which results in the following new constraints: (3) (true=true ==> IF(true, 0, x12)_>=_D(s(0), x12)) (4) (le(x14, x13)=true & (le(x14, x13)=true ==> IF(true, x14, x13)_>=_D(s(x14), x13)) ==> IF(true, s(x14), s(x13))_>=_D(s(s(x14)), s(x13))) We simplified constraint (3) using rules (I), (II) which results in the following new constraint: (5) (IF(true, 0, x12)_>=_D(s(0), x12)) We simplified constraint (4) using rule (VI) where we applied the induction hypothesis (le(x14, x13)=true ==> IF(true, x14, x13)_>=_D(s(x14), x13)) with sigma = [ ] which results in the following new constraint: (6) (IF(true, x14, x13)_>=_D(s(x14), x13) ==> IF(true, s(x14), s(x13))_>=_D(s(s(x14)), s(x13))) For Pair D(x, x_removed) -> IF(le(x, x_removed), x, x_removed) the following chains were created: *We consider the chain IF(true, x6, x7) -> D(s(x6), x7), D(x8, x9) -> IF(le(x8, x9), x8, x9) which results in the following constraint: (1) (D(s(x6), x7)=D(x8, x9) ==> D(x8, x9)_>=_IF(le(x8, x9), x8, x9)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (D(s(x6), x7)_>=_IF(le(s(x6), x7), s(x6), x7)) To summarize, we get the following constraints P__>=_ for the following pairs. *IF(true, x, x_removed) -> D(s(x), x_removed) *(IF(true, 0, x12)_>=_D(s(0), x12)) *(IF(true, x14, x13)_>=_D(s(x14), x13) ==> IF(true, s(x14), s(x13))_>=_D(s(s(x14)), s(x13))) *D(x, x_removed) -> IF(le(x, x_removed), x, x_removed) *(D(s(x6), x7)_>=_IF(le(s(x6), x7), s(x6), x7)) The constraints for P_> respective P_bound are constructed from P__>=_ where we just replace every occurence of "t _>=_ s" in P__>=_ by "t > s" respective "t _>=_ c". Here c stands for the fresh constant used for P_bound. Using the following integer polynomial ordering the resulting constraints can be solved Polynomial interpretation [NONINF]: POL(0) = 0 POL(D(x_1, x_2)) = -1 - x_1 + x_2 POL(IF(x_1, x_2, x_3)) = -1 - x_1 - x_2 + x_3 POL(c) = -2 POL(false) = 0 POL(le(x_1, x_2)) = 0 POL(s(x_1)) = 1 + x_1 POL(true) = 0 The following pairs are in P_>: IF(true, x, x_removed) -> D(s(x), x_removed) The following pairs are in P_bound: IF(true, x, x_removed) -> D(s(x), x_removed) The following rules are usable: true -> le(0, y) le(x, y) -> le(s(x), s(y)) false -> le(s(x), 0) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: D(x, x_removed) -> IF(le(x, x_removed), x, x_removed) The TRS R consists of the following rules: le(0, y) -> true le(s(x), s(y)) -> le(x, y) le(s(x), 0) -> false The set Q consists of the following terms: le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (24) TRUE