/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, 10 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) QDPSizeChangeProof [EQUIVALENT, 0 ms] (20) YES (21) QDP (22) UsableRulesProof [EQUIVALENT, 0 ms] (23) QDP (24) QReductionProof [EQUIVALENT, 0 ms] (25) QDP (26) TransformationProof [EQUIVALENT, 0 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) QDP (30) TransformationProof [EQUIVALENT, 0 ms] (31) QDP (32) DependencyGraphProof [EQUIVALENT, 0 ms] (33) QDP (34) QDPOrderProof [EQUIVALENT, 10 ms] (35) QDP (36) DependencyGraphProof [EQUIVALENT, 0 ms] (37) TRUE ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) quot(x, s(y)) -> if_quot(le(s(y), x), x, s(y)) if_quot(true, x, y) -> s(quot(minus(x, y), y)) if_quot(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: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) quot(x, s(y)) -> if_quot(le(s(y), x), x, s(y)) if_quot(true, x, y) -> s(quot(minus(x, y), y)) if_quot(false, x, y) -> 0 The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(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: MINUS(s(x), s(y)) -> MINUS(x, y) LE(s(x), s(y)) -> LE(x, y) QUOT(x, s(y)) -> IF_QUOT(le(s(y), x), x, s(y)) QUOT(x, s(y)) -> LE(s(y), x) IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) IF_QUOT(true, x, y) -> MINUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) quot(x, s(y)) -> if_quot(le(s(y), x), x, s(y)) if_quot(true, x, y) -> s(quot(minus(x, y), y)) if_quot(false, x, y) -> 0 The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(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 3 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: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) quot(x, s(y)) -> if_quot(le(s(y), x), x, s(y)) if_quot(true, x, y) -> s(quot(minus(x, y), y)) if_quot(false, x, y) -> 0 The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(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: LE(s(x), s(y)) -> LE(x, y) R is empty. The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(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]. minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(false, x0, 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: MINUS(s(x), s(y)) -> MINUS(x, y) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) quot(x, s(y)) -> if_quot(le(s(y), x), x, s(y)) if_quot(true, x, y) -> s(quot(minus(x, y), y)) if_quot(false, x, y) -> 0 The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(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(s(x), s(y)) -> MINUS(x, y) R is empty. The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(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, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(false, x0, x1) ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MINUS(s(x), s(y)) -> MINUS(x, y) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) 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: *MINUS(s(x), s(y)) -> MINUS(x, y) The graph contains the following edges 1 > 1, 2 > 2 ---------------------------------------- (20) YES ---------------------------------------- (21) Obligation: Q DP problem: The TRS P consists of the following rules: IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) QUOT(x, s(y)) -> IF_QUOT(le(s(y), x), x, s(y)) The TRS R consists of the following rules: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) le(0, y) -> true le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) quot(x, s(y)) -> if_quot(le(s(y), x), x, s(y)) if_quot(true, x, y) -> s(quot(minus(x, y), y)) if_quot(false, x, y) -> 0 The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(false, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (22) 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. ---------------------------------------- (23) Obligation: Q DP problem: The TRS P consists of the following rules: IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) QUOT(x, s(y)) -> IF_QUOT(le(s(y), x), x, s(y)) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(false, x0, x1) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (24) 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]. quot(x0, s(x1)) if_quot(true, x0, x1) if_quot(false, x0, x1) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) QUOT(x, s(y)) -> IF_QUOT(le(s(y), x), x, s(y)) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule QUOT(x, s(y)) -> IF_QUOT(le(s(y), x), x, s(y)) at position [0] we obtained the following new rules [LPAR04]: (QUOT(0, s(x0)) -> IF_QUOT(false, 0, s(x0)),QUOT(0, s(x0)) -> IF_QUOT(false, 0, s(x0))) (QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0)),QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0))) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) QUOT(0, s(x0)) -> IF_QUOT(false, 0, s(x0)) QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0)) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0)) IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) TransformationProof (EQUIVALENT) By narrowing [LPAR04] the rule IF_QUOT(true, x, y) -> QUOT(minus(x, y), y) at position [0] we obtained the following new rules [LPAR04]: (IF_QUOT(true, x0, 0) -> QUOT(x0, 0),IF_QUOT(true, x0, 0) -> QUOT(x0, 0)) (IF_QUOT(true, s(x0), s(x1)) -> QUOT(minus(x0, x1), s(x1)),IF_QUOT(true, s(x0), s(x1)) -> QUOT(minus(x0, x1), s(x1))) ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0)) IF_QUOT(true, x0, 0) -> QUOT(x0, 0) IF_QUOT(true, s(x0), s(x1)) -> QUOT(minus(x0, x1), s(x1)) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: IF_QUOT(true, s(x0), s(x1)) -> QUOT(minus(x0, x1), s(x1)) QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0)) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. IF_QUOT(true, s(x0), s(x1)) -> QUOT(minus(x0, x1), s(x1)) The remaining pairs can at least be oriented weakly. Used ordering: Combined order from the following AFS and order. IF_QUOT(x1, x2, x3) = x2 s(x1) = s(x1) QUOT(x1, x2) = x1 minus(x1, x2) = x1 Knuth-Bendix order [KBO] with precedence:trivial and weight map: s_1=1 dummyConstant=1 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: QUOT(s(x1), s(x0)) -> IF_QUOT(le(x0, x1), s(x1), s(x0)) The TRS R consists of the following rules: le(s(x), 0) -> false le(s(x), s(y)) -> le(x, y) le(0, y) -> true minus(x, 0) -> x minus(s(x), s(y)) -> minus(x, y) The set Q consists of the following terms: minus(x0, 0) minus(s(x0), s(x1)) le(0, x0) le(s(x0), 0) le(s(x0), s(x1)) We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (37) TRUE