20.20/6.11 YES 20.20/6.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 20.20/6.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 20.20/6.14 20.20/6.14 20.20/6.14 Termination w.r.t. Q of the given QTRS could be proven: 20.20/6.14 20.20/6.14 (0) QTRS 20.20/6.14 (1) DependencyPairsProof [EQUIVALENT, 34 ms] 20.20/6.14 (2) QDP 20.20/6.14 (3) DependencyGraphProof [EQUIVALENT, 8 ms] 20.20/6.14 (4) AND 20.20/6.14 (5) QDP 20.20/6.14 (6) MNOCProof [EQUIVALENT, 0 ms] 20.20/6.14 (7) QDP 20.20/6.14 (8) UsableRulesProof [EQUIVALENT, 0 ms] 20.20/6.14 (9) QDP 20.20/6.14 (10) QReductionProof [EQUIVALENT, 0 ms] 20.20/6.14 (11) QDP 20.20/6.14 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 20.20/6.14 (13) YES 20.20/6.14 (14) QDP 20.20/6.14 (15) UsableRulesProof [EQUIVALENT, 0 ms] 20.20/6.14 (16) QDP 20.20/6.14 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 20.20/6.14 (18) YES 20.20/6.14 (19) QDP 20.20/6.14 (20) MNOCProof [EQUIVALENT, 0 ms] 20.20/6.14 (21) QDP 20.20/6.14 (22) UsableRulesProof [EQUIVALENT, 0 ms] 20.20/6.14 (23) QDP 20.20/6.14 (24) QReductionProof [EQUIVALENT, 0 ms] 20.20/6.14 (25) QDP 20.20/6.14 (26) QDPOrderProof [EQUIVALENT, 36 ms] 20.20/6.14 (27) QDP 20.20/6.14 (28) QDPOrderProof [EQUIVALENT, 21 ms] 20.20/6.14 (29) QDP 20.20/6.14 (30) PisEmptyProof [EQUIVALENT, 0 ms] 20.20/6.14 (31) YES 20.20/6.14 (32) QDP 20.20/6.14 (33) MNOCProof [EQUIVALENT, 0 ms] 20.20/6.14 (34) QDP 20.20/6.14 (35) UsableRulesProof [EQUIVALENT, 0 ms] 20.20/6.14 (36) QDP 20.20/6.14 (37) QReductionProof [EQUIVALENT, 0 ms] 20.20/6.14 (38) QDP 20.20/6.14 (39) QDPOrderProof [EQUIVALENT, 23 ms] 20.20/6.14 (40) QDP 20.20/6.14 (41) DependencyGraphProof [EQUIVALENT, 0 ms] 20.20/6.14 (42) TRUE 20.20/6.14 20.20/6.14 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (0) 20.20/6.14 Obligation: 20.20/6.14 Q restricted rewrite system: 20.20/6.14 The TRS R consists of the following rules: 20.20/6.14 20.20/6.14 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.14 p(s(x1)) -> x1 20.20/6.14 p(p(s(x1))) -> p(x1) 20.20/6.14 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.14 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.14 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.14 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.14 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.14 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.14 20.20/6.14 Q is empty. 20.20/6.14 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (1) DependencyPairsProof (EQUIVALENT) 20.20/6.14 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (2) 20.20/6.14 Obligation: 20.20/6.14 Q DP problem: 20.20/6.14 The TRS P consists of the following rules: 20.20/6.14 20.20/6.14 P(0(x1)) -> P(x1) 20.20/6.14 P(p(s(x1))) -> P(x1) 20.20/6.14 F(s(x1)) -> P(s(g(p(s(s(x1)))))) 20.20/6.14 F(s(x1)) -> G(p(s(s(x1)))) 20.20/6.14 F(s(x1)) -> P(s(s(x1))) 20.20/6.14 G(s(x1)) -> P(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.14 G(s(x1)) -> P(s(s(s(j(s(p(s(p(s(x1)))))))))) 20.20/6.14 G(s(x1)) -> J(s(p(s(p(s(x1)))))) 20.20/6.14 G(s(x1)) -> P(s(p(s(x1)))) 20.20/6.14 G(s(x1)) -> P(s(x1)) 20.20/6.14 J(s(x1)) -> P(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.14 J(s(x1)) -> P(s(f(p(s(p(p(s(x1)))))))) 20.20/6.14 J(s(x1)) -> F(p(s(p(p(s(x1)))))) 20.20/6.14 J(s(x1)) -> P(s(p(p(s(x1))))) 20.20/6.14 J(s(x1)) -> P(p(s(x1))) 20.20/6.14 J(s(x1)) -> P(s(x1)) 20.20/6.14 HALF(0(x1)) -> HALF(p(s(p(s(x1))))) 20.20/6.14 HALF(0(x1)) -> P(s(p(s(x1)))) 20.20/6.14 HALF(0(x1)) -> P(s(x1)) 20.20/6.14 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.14 HALF(s(s(x1))) -> P(p(s(s(x1)))) 20.20/6.14 HALF(s(s(x1))) -> P(s(s(x1))) 20.20/6.14 RD(0(x1)) -> RD(x1) 20.20/6.14 20.20/6.14 The TRS R consists of the following rules: 20.20/6.14 20.20/6.14 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.14 p(s(x1)) -> x1 20.20/6.14 p(p(s(x1))) -> p(x1) 20.20/6.14 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.14 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.14 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.14 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.14 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.14 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.14 20.20/6.14 Q is empty. 20.20/6.14 We have to consider all minimal (P,Q,R)-chains. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (3) DependencyGraphProof (EQUIVALENT) 20.20/6.14 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 4 SCCs with 15 less nodes. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (4) 20.20/6.14 Complex Obligation (AND) 20.20/6.14 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (5) 20.20/6.14 Obligation: 20.20/6.14 Q DP problem: 20.20/6.14 The TRS P consists of the following rules: 20.20/6.14 20.20/6.14 RD(0(x1)) -> RD(x1) 20.20/6.14 20.20/6.14 The TRS R consists of the following rules: 20.20/6.14 20.20/6.14 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.14 p(s(x1)) -> x1 20.20/6.14 p(p(s(x1))) -> p(x1) 20.20/6.14 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.14 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.14 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.14 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.14 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.14 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.14 20.20/6.14 Q is empty. 20.20/6.14 We have to consider all minimal (P,Q,R)-chains. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (6) MNOCProof (EQUIVALENT) 20.20/6.14 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (7) 20.20/6.14 Obligation: 20.20/6.14 Q DP problem: 20.20/6.14 The TRS P consists of the following rules: 20.20/6.14 20.20/6.14 RD(0(x1)) -> RD(x1) 20.20/6.14 20.20/6.14 The TRS R consists of the following rules: 20.20/6.14 20.20/6.14 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.14 p(s(x1)) -> x1 20.20/6.14 p(p(s(x1))) -> p(x1) 20.20/6.14 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.14 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.14 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.14 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.14 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.14 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.14 20.20/6.14 The set Q consists of the following terms: 20.20/6.14 20.20/6.14 p(0(x0)) 20.20/6.14 p(s(x0)) 20.20/6.14 f(s(x0)) 20.20/6.14 g(s(x0)) 20.20/6.14 j(s(x0)) 20.20/6.14 half(0(x0)) 20.20/6.14 half(s(s(x0))) 20.20/6.14 rd(0(x0)) 20.20/6.14 20.20/6.14 We have to consider all minimal (P,Q,R)-chains. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (8) UsableRulesProof (EQUIVALENT) 20.20/6.14 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. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (9) 20.20/6.14 Obligation: 20.20/6.14 Q DP problem: 20.20/6.14 The TRS P consists of the following rules: 20.20/6.14 20.20/6.14 RD(0(x1)) -> RD(x1) 20.20/6.14 20.20/6.14 R is empty. 20.20/6.14 The set Q consists of the following terms: 20.20/6.14 20.20/6.14 p(0(x0)) 20.20/6.14 p(s(x0)) 20.20/6.14 f(s(x0)) 20.20/6.14 g(s(x0)) 20.20/6.14 j(s(x0)) 20.20/6.14 half(0(x0)) 20.20/6.14 half(s(s(x0))) 20.20/6.14 rd(0(x0)) 20.20/6.14 20.20/6.14 We have to consider all minimal (P,Q,R)-chains. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (10) QReductionProof (EQUIVALENT) 20.20/6.14 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 20.20/6.14 20.20/6.14 p(0(x0)) 20.20/6.14 p(s(x0)) 20.20/6.14 f(s(x0)) 20.20/6.14 g(s(x0)) 20.20/6.14 j(s(x0)) 20.20/6.14 half(0(x0)) 20.20/6.14 half(s(s(x0))) 20.20/6.14 rd(0(x0)) 20.20/6.14 20.20/6.14 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (11) 20.20/6.14 Obligation: 20.20/6.14 Q DP problem: 20.20/6.14 The TRS P consists of the following rules: 20.20/6.14 20.20/6.14 RD(0(x1)) -> RD(x1) 20.20/6.14 20.20/6.14 R is empty. 20.20/6.14 Q is empty. 20.20/6.14 We have to consider all minimal (P,Q,R)-chains. 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (12) QDPSizeChangeProof (EQUIVALENT) 20.20/6.14 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. 20.20/6.14 20.20/6.14 From the DPs we obtained the following set of size-change graphs: 20.20/6.14 *RD(0(x1)) -> RD(x1) 20.20/6.14 The graph contains the following edges 1 > 1 20.20/6.14 20.20/6.14 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (13) 20.20/6.14 YES 20.20/6.14 20.20/6.14 ---------------------------------------- 20.20/6.14 20.20/6.14 (14) 20.20/6.14 Obligation: 20.20/6.14 Q DP problem: 20.20/6.14 The TRS P consists of the following rules: 20.20/6.14 20.20/6.14 P(p(s(x1))) -> P(x1) 20.20/6.14 P(0(x1)) -> P(x1) 20.20/6.14 20.20/6.14 The TRS R consists of the following rules: 20.20/6.14 20.20/6.14 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.14 p(s(x1)) -> x1 20.20/6.14 p(p(s(x1))) -> p(x1) 20.20/6.14 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.14 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.14 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.15 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.15 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.15 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.15 20.20/6.15 Q is empty. 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (15) UsableRulesProof (EQUIVALENT) 20.20/6.15 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. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (16) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 P(p(s(x1))) -> P(x1) 20.20/6.15 P(0(x1)) -> P(x1) 20.20/6.15 20.20/6.15 R is empty. 20.20/6.15 Q is empty. 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (17) QDPSizeChangeProof (EQUIVALENT) 20.20/6.15 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. 20.20/6.15 20.20/6.15 From the DPs we obtained the following set of size-change graphs: 20.20/6.15 *P(p(s(x1))) -> P(x1) 20.20/6.15 The graph contains the following edges 1 > 1 20.20/6.15 20.20/6.15 20.20/6.15 *P(0(x1)) -> P(x1) 20.20/6.15 The graph contains the following edges 1 > 1 20.20/6.15 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (18) 20.20/6.15 YES 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (19) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.15 HALF(0(x1)) -> HALF(p(s(p(s(x1))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(p(s(x1))) -> p(x1) 20.20/6.15 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.15 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.15 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.15 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.15 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.15 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.15 20.20/6.15 Q is empty. 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (20) MNOCProof (EQUIVALENT) 20.20/6.15 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (21) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.15 HALF(0(x1)) -> HALF(p(s(p(s(x1))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(p(s(x1))) -> p(x1) 20.20/6.15 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.15 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.15 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.15 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.15 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.15 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 f(s(x0)) 20.20/6.15 g(s(x0)) 20.20/6.15 j(s(x0)) 20.20/6.15 half(0(x0)) 20.20/6.15 half(s(s(x0))) 20.20/6.15 rd(0(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (22) UsableRulesProof (EQUIVALENT) 20.20/6.15 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. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (23) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.15 HALF(0(x1)) -> HALF(p(s(p(s(x1))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 f(s(x0)) 20.20/6.15 g(s(x0)) 20.20/6.15 j(s(x0)) 20.20/6.15 half(0(x0)) 20.20/6.15 half(s(s(x0))) 20.20/6.15 rd(0(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (24) QReductionProof (EQUIVALENT) 20.20/6.15 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 20.20/6.15 20.20/6.15 f(s(x0)) 20.20/6.15 g(s(x0)) 20.20/6.15 j(s(x0)) 20.20/6.15 half(0(x0)) 20.20/6.15 half(s(s(x0))) 20.20/6.15 rd(0(x0)) 20.20/6.15 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (25) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.15 HALF(0(x1)) -> HALF(p(s(p(s(x1))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (26) QDPOrderProof (EQUIVALENT) 20.20/6.15 We use the reduction pair processor [LPAR04,JAR06]. 20.20/6.15 20.20/6.15 20.20/6.15 The following pairs can be oriented strictly and are deleted. 20.20/6.15 20.20/6.15 HALF(0(x1)) -> HALF(p(s(p(s(x1))))) 20.20/6.15 The remaining pairs can at least be oriented weakly. 20.20/6.15 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 20.20/6.15 20.20/6.15 POL( HALF_1(x_1) ) = x_1 + 2 20.20/6.15 POL( p_1(x_1) ) = x_1 20.20/6.15 POL( s_1(x_1) ) = x_1 20.20/6.15 POL( 0_1(x_1) ) = x_1 + 1 20.20/6.15 20.20/6.15 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (27) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (28) QDPOrderProof (EQUIVALENT) 20.20/6.15 We use the reduction pair processor [LPAR04,JAR06]. 20.20/6.15 20.20/6.15 20.20/6.15 The following pairs can be oriented strictly and are deleted. 20.20/6.15 20.20/6.15 HALF(s(s(x1))) -> HALF(p(p(s(s(x1))))) 20.20/6.15 The remaining pairs can at least be oriented weakly. 20.20/6.15 Used ordering: Matrix interpretation [MATRO] with arctic natural numbers [ARCTIC]: 20.20/6.15 20.20/6.15 <<< 20.20/6.15 POL(HALF(x_1)) = [[0A]] + [[-I, -I, 0A]] * x_1 20.20/6.15 >>> 20.20/6.15 20.20/6.15 <<< 20.20/6.15 POL(s(x_1)) = [[0A], [0A], [0A]] + [[0A, 0A, -I], [0A, 0A, 0A], [0A, 1A, 0A]] * x_1 20.20/6.15 >>> 20.20/6.15 20.20/6.15 <<< 20.20/6.15 POL(p(x_1)) = [[0A], [0A], [0A]] + [[1A, 0A, 0A], [0A, -I, -I], [-I, 0A, -I]] * x_1 20.20/6.15 >>> 20.20/6.15 20.20/6.15 <<< 20.20/6.15 POL(0(x_1)) = [[1A], [0A], [0A]] + [[1A, 0A, 0A], [0A, 0A, -I], [-I, -I, -I]] * x_1 20.20/6.15 >>> 20.20/6.15 20.20/6.15 20.20/6.15 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (29) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 P is empty. 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (30) PisEmptyProof (EQUIVALENT) 20.20/6.15 The TRS P is empty. Hence, there is no (P,Q,R) chain. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (31) 20.20/6.15 YES 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (32) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 F(s(x1)) -> G(p(s(s(x1)))) 20.20/6.15 G(s(x1)) -> J(s(p(s(p(s(x1)))))) 20.20/6.15 J(s(x1)) -> F(p(s(p(p(s(x1)))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(p(s(x1))) -> p(x1) 20.20/6.15 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.15 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.15 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.15 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.15 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.15 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.15 20.20/6.15 Q is empty. 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (33) MNOCProof (EQUIVALENT) 20.20/6.15 We use the modular non-overlap check [LPAR04] to enlarge Q to all left-hand sides of R. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (34) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 F(s(x1)) -> G(p(s(s(x1)))) 20.20/6.15 G(s(x1)) -> J(s(p(s(p(s(x1)))))) 20.20/6.15 J(s(x1)) -> F(p(s(p(p(s(x1)))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(p(s(x1))) -> p(x1) 20.20/6.15 f(s(x1)) -> p(s(g(p(s(s(x1)))))) 20.20/6.15 g(s(x1)) -> p(p(s(s(s(j(s(p(s(p(s(x1))))))))))) 20.20/6.15 j(s(x1)) -> p(s(s(p(s(f(p(s(p(p(s(x1))))))))))) 20.20/6.15 half(0(x1)) -> 0(s(s(half(p(s(p(s(x1)))))))) 20.20/6.15 half(s(s(x1))) -> s(half(p(p(s(s(x1)))))) 20.20/6.15 rd(0(x1)) -> 0(s(0(0(0(0(s(0(rd(x1))))))))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 f(s(x0)) 20.20/6.15 g(s(x0)) 20.20/6.15 j(s(x0)) 20.20/6.15 half(0(x0)) 20.20/6.15 half(s(s(x0))) 20.20/6.15 rd(0(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (35) UsableRulesProof (EQUIVALENT) 20.20/6.15 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. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (36) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 F(s(x1)) -> G(p(s(s(x1)))) 20.20/6.15 G(s(x1)) -> J(s(p(s(p(s(x1)))))) 20.20/6.15 J(s(x1)) -> F(p(s(p(p(s(x1)))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 f(s(x0)) 20.20/6.15 g(s(x0)) 20.20/6.15 j(s(x0)) 20.20/6.15 half(0(x0)) 20.20/6.15 half(s(s(x0))) 20.20/6.15 rd(0(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (37) QReductionProof (EQUIVALENT) 20.20/6.15 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 20.20/6.15 20.20/6.15 f(s(x0)) 20.20/6.15 g(s(x0)) 20.20/6.15 j(s(x0)) 20.20/6.15 half(0(x0)) 20.20/6.15 half(s(s(x0))) 20.20/6.15 rd(0(x0)) 20.20/6.15 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (38) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 F(s(x1)) -> G(p(s(s(x1)))) 20.20/6.15 G(s(x1)) -> J(s(p(s(p(s(x1)))))) 20.20/6.15 J(s(x1)) -> F(p(s(p(p(s(x1)))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (39) QDPOrderProof (EQUIVALENT) 20.20/6.15 We use the reduction pair processor [LPAR04,JAR06]. 20.20/6.15 20.20/6.15 20.20/6.15 The following pairs can be oriented strictly and are deleted. 20.20/6.15 20.20/6.15 J(s(x1)) -> F(p(s(p(p(s(x1)))))) 20.20/6.15 The remaining pairs can at least be oriented weakly. 20.20/6.15 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 20.20/6.15 20.20/6.15 POL( F_1(x_1) ) = 2x_1 20.20/6.15 POL( G_1(x_1) ) = 2x_1 20.20/6.15 POL( J_1(x_1) ) = 2x_1 20.20/6.15 POL( s_1(x_1) ) = x_1 + 2 20.20/6.15 POL( p_1(x_1) ) = max{0, x_1 - 2} 20.20/6.15 POL( 0_1(x_1) ) = max{0, -2} 20.20/6.15 20.20/6.15 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (40) 20.20/6.15 Obligation: 20.20/6.15 Q DP problem: 20.20/6.15 The TRS P consists of the following rules: 20.20/6.15 20.20/6.15 F(s(x1)) -> G(p(s(s(x1)))) 20.20/6.15 G(s(x1)) -> J(s(p(s(p(s(x1)))))) 20.20/6.15 20.20/6.15 The TRS R consists of the following rules: 20.20/6.15 20.20/6.15 p(s(x1)) -> x1 20.20/6.15 p(0(x1)) -> 0(s(s(p(x1)))) 20.20/6.15 20.20/6.15 The set Q consists of the following terms: 20.20/6.15 20.20/6.15 p(0(x0)) 20.20/6.15 p(s(x0)) 20.20/6.15 20.20/6.15 We have to consider all minimal (P,Q,R)-chains. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (41) DependencyGraphProof (EQUIVALENT) 20.20/6.15 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes. 20.20/6.15 ---------------------------------------- 20.20/6.15 20.20/6.15 (42) 20.20/6.15 TRUE 20.56/6.20 EOF