4.99/2.24 MAYBE 4.99/2.25 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 4.99/2.25 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.99/2.25 4.99/2.25 4.99/2.25 Quasi decreasingness of the given CTRS could not be shown: 4.99/2.25 4.99/2.25 (0) CTRS 4.99/2.25 (1) CTRSToQTRSProof [SOUND, 0 ms] 4.99/2.25 (2) QTRS 4.99/2.25 (3) DependencyPairsProof [EQUIVALENT, 0 ms] 4.99/2.25 (4) QDP 4.99/2.25 (5) DependencyGraphProof [EQUIVALENT, 0 ms] 4.99/2.25 (6) AND 4.99/2.25 (7) QDP 4.99/2.25 (8) UsableRulesProof [EQUIVALENT, 0 ms] 4.99/2.25 (9) QDP 4.99/2.25 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.99/2.25 (11) YES 4.99/2.25 (12) QDP 4.99/2.25 (13) UsableRulesProof [EQUIVALENT, 0 ms] 4.99/2.25 (14) QDP 4.99/2.25 (15) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.99/2.25 (16) YES 4.99/2.25 (17) QDP 4.99/2.25 (18) UsableRulesProof [EQUIVALENT, 0 ms] 4.99/2.25 (19) QDP 4.99/2.25 (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.99/2.25 (21) YES 4.99/2.25 (22) QDP 4.99/2.25 (23) NonTerminationLoopProof [COMPLETE, 0 ms] 4.99/2.25 (24) NO 4.99/2.25 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (0) 4.99/2.25 Obligation: 4.99/2.25 Conditional term rewrite system: 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 The conditional TRS C consists of the following conditional rules: 4.99/2.25 4.99/2.25 div(x, y) -> pair(0, y) <= greater(y, x) -> true 4.99/2.25 div(x, y) -> pair(s(q), r) <= leq(y, x) -> true, div(m(x, y), y) -> pair(q, r) 4.99/2.25 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (1) CTRSToQTRSProof (SOUND) 4.99/2.25 The conditional rules have been transormed into unconditional rules according to [CTRS,AAECCNOC]. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (2) 4.99/2.25 Obligation: 4.99/2.25 Q restricted rewrite system: 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 div(x, y) -> U1(greater(y, x), y) 4.99/2.25 U1(true, y) -> pair(0, y) 4.99/2.25 div(x, y) -> U2(leq(y, x), x, y) 4.99/2.25 U2(true, x, y) -> U3(div(m(x, y), y)) 4.99/2.25 U3(pair(q, r)) -> pair(s(q), r) 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 Q is empty. 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (3) DependencyPairsProof (EQUIVALENT) 4.99/2.25 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (4) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 DIV(x, y) -> U1^1(greater(y, x), y) 4.99/2.25 DIV(x, y) -> GREATER(y, x) 4.99/2.25 DIV(x, y) -> U2^1(leq(y, x), x, y) 4.99/2.25 DIV(x, y) -> LEQ(y, x) 4.99/2.25 U2^1(true, x, y) -> U3^1(div(m(x, y), y)) 4.99/2.25 U2^1(true, x, y) -> DIV(m(x, y), y) 4.99/2.25 U2^1(true, x, y) -> M(x, y) 4.99/2.25 M(s(x), s(y)) -> M(x, y) 4.99/2.25 GREATER(s(x), s(y)) -> GREATER(x, y) 4.99/2.25 LEQ(s(x), s(y)) -> LEQ(x, y) 4.99/2.25 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 div(x, y) -> U1(greater(y, x), y) 4.99/2.25 U1(true, y) -> pair(0, y) 4.99/2.25 div(x, y) -> U2(leq(y, x), x, y) 4.99/2.25 U2(true, x, y) -> U3(div(m(x, y), y)) 4.99/2.25 U3(pair(q, r)) -> pair(s(q), r) 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (5) DependencyGraphProof (EQUIVALENT) 4.99/2.25 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 5 less nodes. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (6) 4.99/2.25 Complex Obligation (AND) 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (7) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 LEQ(s(x), s(y)) -> LEQ(x, y) 4.99/2.25 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 div(x, y) -> U1(greater(y, x), y) 4.99/2.25 U1(true, y) -> pair(0, y) 4.99/2.25 div(x, y) -> U2(leq(y, x), x, y) 4.99/2.25 U2(true, x, y) -> U3(div(m(x, y), y)) 4.99/2.25 U3(pair(q, r)) -> pair(s(q), r) 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (8) UsableRulesProof (EQUIVALENT) 4.99/2.25 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (9) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 LEQ(s(x), s(y)) -> LEQ(x, y) 4.99/2.25 4.99/2.25 R is empty. 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (10) QDPSizeChangeProof (EQUIVALENT) 4.99/2.25 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. 4.99/2.25 4.99/2.25 From the DPs we obtained the following set of size-change graphs: 4.99/2.25 *LEQ(s(x), s(y)) -> LEQ(x, y) 4.99/2.25 The graph contains the following edges 1 > 1, 2 > 2 4.99/2.25 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (11) 4.99/2.25 YES 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (12) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 GREATER(s(x), s(y)) -> GREATER(x, y) 4.99/2.25 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 div(x, y) -> U1(greater(y, x), y) 4.99/2.25 U1(true, y) -> pair(0, y) 4.99/2.25 div(x, y) -> U2(leq(y, x), x, y) 4.99/2.25 U2(true, x, y) -> U3(div(m(x, y), y)) 4.99/2.25 U3(pair(q, r)) -> pair(s(q), r) 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (13) UsableRulesProof (EQUIVALENT) 4.99/2.25 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (14) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 GREATER(s(x), s(y)) -> GREATER(x, y) 4.99/2.25 4.99/2.25 R is empty. 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (15) QDPSizeChangeProof (EQUIVALENT) 4.99/2.25 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. 4.99/2.25 4.99/2.25 From the DPs we obtained the following set of size-change graphs: 4.99/2.25 *GREATER(s(x), s(y)) -> GREATER(x, y) 4.99/2.25 The graph contains the following edges 1 > 1, 2 > 2 4.99/2.25 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (16) 4.99/2.25 YES 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (17) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 M(s(x), s(y)) -> M(x, y) 4.99/2.25 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 div(x, y) -> U1(greater(y, x), y) 4.99/2.25 U1(true, y) -> pair(0, y) 4.99/2.25 div(x, y) -> U2(leq(y, x), x, y) 4.99/2.25 U2(true, x, y) -> U3(div(m(x, y), y)) 4.99/2.25 U3(pair(q, r)) -> pair(s(q), r) 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (18) UsableRulesProof (EQUIVALENT) 4.99/2.25 We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (19) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 M(s(x), s(y)) -> M(x, y) 4.99/2.25 4.99/2.25 R is empty. 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (20) QDPSizeChangeProof (EQUIVALENT) 4.99/2.25 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. 4.99/2.25 4.99/2.25 From the DPs we obtained the following set of size-change graphs: 4.99/2.25 *M(s(x), s(y)) -> M(x, y) 4.99/2.25 The graph contains the following edges 1 > 1, 2 > 2 4.99/2.25 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (21) 4.99/2.25 YES 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (22) 4.99/2.25 Obligation: 4.99/2.25 Q DP problem: 4.99/2.25 The TRS P consists of the following rules: 4.99/2.25 4.99/2.25 DIV(x, y) -> U2^1(leq(y, x), x, y) 4.99/2.25 U2^1(true, x, y) -> DIV(m(x, y), y) 4.99/2.25 4.99/2.25 The TRS R consists of the following rules: 4.99/2.25 4.99/2.25 div(x, y) -> U1(greater(y, x), y) 4.99/2.25 U1(true, y) -> pair(0, y) 4.99/2.25 div(x, y) -> U2(leq(y, x), x, y) 4.99/2.25 U2(true, x, y) -> U3(div(m(x, y), y)) 4.99/2.25 U3(pair(q, r)) -> pair(s(q), r) 4.99/2.25 m(x, 0) -> x 4.99/2.25 m(0, y) -> 0 4.99/2.25 m(s(x), s(y)) -> m(x, y) 4.99/2.25 greater(s(x), s(y)) -> greater(x, y) 4.99/2.25 greater(s(x), 0) -> true 4.99/2.25 leq(s(x), s(y)) -> leq(x, y) 4.99/2.25 leq(0, x) -> true 4.99/2.25 4.99/2.25 Q is empty. 4.99/2.25 We have to consider all minimal (P,Q,R)-chains. 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (23) NonTerminationLoopProof (COMPLETE) 4.99/2.25 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 4.99/2.25 Found a loop by narrowing to the left: 4.99/2.25 4.99/2.25 s = U2^1(leq(0, x), x', y') evaluates to t =U2^1(leq(y', m(x', y')), m(x', y'), y') 4.99/2.25 4.99/2.25 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 4.99/2.25 * Matcher: [x / m(x', 0), x' / m(x', 0)] 4.99/2.25 * Semiunifier: [y' / 0] 4.99/2.25 4.99/2.25 -------------------------------------------------------------------------------- 4.99/2.25 Rewriting sequence 4.99/2.25 4.99/2.25 U2^1(leq(0, x), x', 0) -> U2^1(true, x', 0) 4.99/2.25 with rule leq(0, x'') -> true at position [0] and matcher [x'' / x] 4.99/2.25 4.99/2.25 U2^1(true, x', 0) -> DIV(m(x', 0), 0) 4.99/2.25 with rule U2^1(true, x'', y') -> DIV(m(x'', y'), y') at position [] and matcher [x'' / x', y' / 0] 4.99/2.25 4.99/2.25 DIV(m(x', 0), 0) -> U2^1(leq(0, m(x', 0)), m(x', 0), 0) 4.99/2.25 with rule DIV(x, y) -> U2^1(leq(y, x), x, y) 4.99/2.25 4.99/2.25 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 4.99/2.25 4.99/2.25 4.99/2.25 All these steps are and every following step will be a correct step w.r.t to Q. 4.99/2.25 4.99/2.25 4.99/2.25 4.99/2.25 4.99/2.25 ---------------------------------------- 4.99/2.25 4.99/2.25 (24) 4.99/2.25 NO 4.99/2.27 EOF