/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, 0 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, 1 ms] (13) YES (14) QDP (15) UsableRulesProof [EQUIVALENT, 0 ms] (16) QDP (17) QReductionProof [EQUIVALENT, 0 ms] (18) QDP (19) NonInfProof [EQUIVALENT, 45 ms] (20) AND (21) QDP (22) DependencyGraphProof [EQUIVALENT, 0 ms] (23) TRUE (24) QDP (25) DependencyGraphProof [EQUIVALENT, 0 ms] (26) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) minus(x, y) -> help(lt(y, x), x, y) help(true, x, y) -> s(minus(x, s(y))) help(false, x, y) -> 0 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: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) minus(x, y) -> help(lt(y, x), x, y) help(true, x, y) -> s(minus(x, s(y))) help(false, x, y) -> 0 The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, 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: LT(s(x), s(y)) -> LT(x, y) MINUS(x, y) -> HELP(lt(y, x), x, y) MINUS(x, y) -> LT(y, x) HELP(true, x, y) -> MINUS(x, s(y)) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) minus(x, y) -> help(lt(y, x), x, y) help(true, x, y) -> s(minus(x, s(y))) help(false, x, y) -> 0 The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, 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 1 less node. ---------------------------------------- (6) Complex Obligation (AND) ---------------------------------------- (7) Obligation: Q DP problem: The TRS P consists of the following rules: LT(s(x), s(y)) -> LT(x, y) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) minus(x, y) -> help(lt(y, x), x, y) help(true, x, y) -> s(minus(x, s(y))) help(false, x, y) -> 0 The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, 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: LT(s(x), s(y)) -> LT(x, y) R is empty. The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, 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]. lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, x1) ---------------------------------------- (11) Obligation: Q DP problem: The TRS P consists of the following rules: LT(s(x), s(y)) -> LT(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: *LT(s(x), s(y)) -> LT(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: MINUS(x, y) -> HELP(lt(y, x), x, y) HELP(true, x, y) -> MINUS(x, s(y)) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) minus(x, y) -> help(lt(y, x), x, y) help(true, x, y) -> s(minus(x, s(y))) help(false, x, y) -> 0 The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, 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: MINUS(x, y) -> HELP(lt(y, x), x, y) HELP(true, x, y) -> MINUS(x, s(y)) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) minus(x0, x1) help(true, x0, x1) help(false, x0, 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]. minus(x0, x1) help(true, x0, x1) help(false, x0, x1) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(x, y) -> HELP(lt(y, x), x, y) HELP(true, x, y) -> MINUS(x, s(y)) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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 MINUS(x, y) -> HELP(lt(y, x), x, y) the following chains were created: *We consider the chain HELP(true, x2, x3) -> MINUS(x2, s(x3)), MINUS(x4, x5) -> HELP(lt(x5, x4), x4, x5) which results in the following constraint: (1) (MINUS(x2, s(x3))=MINUS(x4, x5) ==> MINUS(x4, x5)_>=_HELP(lt(x5, x4), x4, x5)) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (MINUS(x2, s(x3))_>=_HELP(lt(s(x3), x2), x2, s(x3))) For Pair HELP(true, x, y) -> MINUS(x, s(y)) the following chains were created: *We consider the chain MINUS(x6, x7) -> HELP(lt(x7, x6), x6, x7), HELP(true, x8, x9) -> MINUS(x8, s(x9)) which results in the following constraint: (1) (HELP(lt(x7, x6), x6, x7)=HELP(true, x8, x9) ==> HELP(true, x8, x9)_>=_MINUS(x8, s(x9))) We simplified constraint (1) using rules (I), (II), (III) which results in the following new constraint: (2) (lt(x7, x6)=true ==> HELP(true, x6, x7)_>=_MINUS(x6, s(x7))) We simplified constraint (2) using rule (V) (with possible (I) afterwards) using induction on lt(x7, x6)=true which results in the following new constraints: (3) (true=true ==> HELP(true, s(x12), 0)_>=_MINUS(s(x12), s(0))) (4) (lt(x15, x14)=true & (lt(x15, x14)=true ==> HELP(true, x14, x15)_>=_MINUS(x14, s(x15))) ==> HELP(true, s(x14), s(x15))_>=_MINUS(s(x14), s(s(x15)))) We simplified constraint (3) using rules (I), (II) which results in the following new constraint: (5) (HELP(true, s(x12), 0)_>=_MINUS(s(x12), s(0))) We simplified constraint (4) using rule (VI) where we applied the induction hypothesis (lt(x15, x14)=true ==> HELP(true, x14, x15)_>=_MINUS(x14, s(x15))) with sigma = [ ] which results in the following new constraint: (6) (HELP(true, x14, x15)_>=_MINUS(x14, s(x15)) ==> HELP(true, s(x14), s(x15))_>=_MINUS(s(x14), s(s(x15)))) To summarize, we get the following constraints P__>=_ for the following pairs. *MINUS(x, y) -> HELP(lt(y, x), x, y) *(MINUS(x2, s(x3))_>=_HELP(lt(s(x3), x2), x2, s(x3))) *HELP(true, x, y) -> MINUS(x, s(y)) *(HELP(true, s(x12), 0)_>=_MINUS(s(x12), s(0))) *(HELP(true, x14, x15)_>=_MINUS(x14, s(x15)) ==> HELP(true, s(x14), s(x15))_>=_MINUS(s(x14), s(s(x15)))) 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(HELP(x_1, x_2, x_3)) = -x_1 + x_2 - x_3 POL(MINUS(x_1, x_2)) = 1 + x_1 - x_2 POL(c) = -1 POL(false) = 0 POL(lt(x_1, x_2)) = 0 POL(s(x_1)) = 1 + x_1 POL(true) = 0 The following pairs are in P_>: MINUS(x, y) -> HELP(lt(y, x), x, y) The following pairs are in P_bound: HELP(true, x, y) -> MINUS(x, s(y)) The following rules are usable: true -> lt(0, s(x)) false -> lt(x, 0) lt(x, y) -> lt(s(x), s(y)) ---------------------------------------- (20) Complex Obligation (AND) ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: HELP(true, x, y) -> MINUS(x, s(y)) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (23) TRUE ---------------------------------------- (24) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(x, y) -> HELP(lt(y, x), x, y) The TRS R consists of the following rules: lt(0, s(x)) -> true lt(x, 0) -> false lt(s(x), s(y)) -> lt(x, y) The set Q consists of the following terms: lt(0, s(x0)) lt(x0, 0) lt(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (25) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (26) TRUE