30.06/8.83 YES 30.06/8.83 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 30.06/8.83 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 30.06/8.83 30.06/8.83 30.06/8.83 Termination w.r.t. Q of the given QTRS could be proven: 30.06/8.83 30.06/8.83 (0) QTRS 30.06/8.83 (1) QTRS Reverse [EQUIVALENT, 0 ms] 30.06/8.83 (2) QTRS 30.06/8.83 (3) QTRSRRRProof [EQUIVALENT, 30 ms] 30.06/8.83 (4) QTRS 30.06/8.83 (5) DependencyPairsProof [EQUIVALENT, 20 ms] 30.06/8.83 (6) QDP 30.06/8.83 (7) DependencyGraphProof [EQUIVALENT, 5 ms] 30.06/8.83 (8) AND 30.06/8.83 (9) QDP 30.06/8.83 (10) UsableRulesProof [EQUIVALENT, 1 ms] 30.06/8.83 (11) QDP 30.06/8.83 (12) QDPSizeChangeProof [EQUIVALENT, 0 ms] 30.06/8.83 (13) YES 30.06/8.83 (14) QDP 30.06/8.83 (15) UsableRulesProof [EQUIVALENT, 0 ms] 30.06/8.83 (16) QDP 30.06/8.83 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 30.06/8.83 (18) YES 30.06/8.83 (19) QDP 30.06/8.83 (20) UsableRulesProof [EQUIVALENT, 0 ms] 30.06/8.83 (21) QDP 30.06/8.83 (22) QDPSizeChangeProof [EQUIVALENT, 0 ms] 30.06/8.83 (23) YES 30.06/8.83 (24) QDP 30.06/8.83 (25) UsableRulesProof [EQUIVALENT, 0 ms] 30.06/8.83 (26) QDP 30.06/8.83 (27) QDPSizeChangeProof [EQUIVALENT, 0 ms] 30.06/8.83 (28) YES 30.06/8.83 (29) QDP 30.06/8.83 (30) UsableRulesProof [EQUIVALENT, 0 ms] 30.06/8.83 (31) QDP 30.06/8.83 (32) QDPOrderProof [EQUIVALENT, 0 ms] 30.06/8.83 (33) QDP 30.06/8.83 (34) PisEmptyProof [EQUIVALENT, 0 ms] 30.06/8.83 (35) YES 30.06/8.83 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (0) 30.06/8.83 Obligation: 30.06/8.83 Q restricted rewrite system: 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 r(r(x1)) -> s(r(x1)) 30.06/8.83 r(s(x1)) -> s(r(x1)) 30.06/8.83 r(n(x1)) -> s(r(x1)) 30.06/8.83 r(b(x1)) -> u(s(b(x1))) 30.06/8.83 r(u(x1)) -> u(r(x1)) 30.06/8.83 s(u(x1)) -> u(s(x1)) 30.06/8.83 n(u(x1)) -> u(n(x1)) 30.06/8.83 t(r(u(x1))) -> t(c(r(x1))) 30.06/8.83 t(s(u(x1))) -> t(c(r(x1))) 30.06/8.83 t(n(u(x1))) -> t(c(r(x1))) 30.06/8.83 c(u(x1)) -> u(c(x1)) 30.06/8.83 c(s(x1)) -> s(c(x1)) 30.06/8.83 c(r(x1)) -> r(c(x1)) 30.06/8.83 c(n(x1)) -> n(c(x1)) 30.06/8.83 c(n(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (1) QTRS Reverse (EQUIVALENT) 30.06/8.83 We applied the QTRS Reverse Processor [REVERSE]. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (2) 30.06/8.83 Obligation: 30.06/8.83 Q restricted rewrite system: 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 r(r(x1)) -> r(s(x1)) 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 n(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(r(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(n(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (3) QTRSRRRProof (EQUIVALENT) 30.06/8.83 Used ordering: 30.06/8.83 Polynomial interpretation [POLO]: 30.06/8.83 30.06/8.83 POL(b(x_1)) = x_1 30.06/8.83 POL(c(x_1)) = x_1 30.06/8.83 POL(n(x_1)) = 1 + x_1 30.06/8.83 POL(r(x_1)) = 1 + x_1 30.06/8.83 POL(s(x_1)) = x_1 30.06/8.83 POL(t(x_1)) = x_1 30.06/8.83 POL(u(x_1)) = 1 + x_1 30.06/8.83 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 30.06/8.83 30.06/8.83 r(r(x1)) -> r(s(x1)) 30.06/8.83 n(r(x1)) -> r(s(x1)) 30.06/8.83 u(r(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(n(t(x1))) -> r(c(t(x1))) 30.06/8.83 30.06/8.83 30.06/8.83 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (4) 30.06/8.83 Obligation: 30.06/8.83 Q restricted rewrite system: 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (5) DependencyPairsProof (EQUIVALENT) 30.06/8.83 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (6) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 S(r(x1)) -> R(s(x1)) 30.06/8.83 S(r(x1)) -> S(x1) 30.06/8.83 B(r(x1)) -> B(s(u(x1))) 30.06/8.83 B(r(x1)) -> S(u(x1)) 30.06/8.83 B(r(x1)) -> U(x1) 30.06/8.83 U(r(x1)) -> R(u(x1)) 30.06/8.83 U(r(x1)) -> U(x1) 30.06/8.83 U(s(x1)) -> S(u(x1)) 30.06/8.83 U(s(x1)) -> U(x1) 30.06/8.83 U(n(x1)) -> N(u(x1)) 30.06/8.83 U(n(x1)) -> U(x1) 30.06/8.83 U(s(t(x1))) -> R(c(t(x1))) 30.06/8.83 U(c(x1)) -> U(x1) 30.06/8.83 S(c(x1)) -> S(x1) 30.06/8.83 R(c(x1)) -> R(x1) 30.06/8.83 N(c(x1)) -> N(x1) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (7) DependencyGraphProof (EQUIVALENT) 30.06/8.83 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 7 less nodes. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (8) 30.06/8.83 Complex Obligation (AND) 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (9) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 N(c(x1)) -> N(x1) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (10) UsableRulesProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (11) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 N(c(x1)) -> N(x1) 30.06/8.83 30.06/8.83 R is empty. 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (12) QDPSizeChangeProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 30.06/8.83 From the DPs we obtained the following set of size-change graphs: 30.06/8.83 *N(c(x1)) -> N(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (13) 30.06/8.83 YES 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (14) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 R(c(x1)) -> R(x1) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (15) UsableRulesProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (16) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 R(c(x1)) -> R(x1) 30.06/8.83 30.06/8.83 R is empty. 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (17) QDPSizeChangeProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 30.06/8.83 From the DPs we obtained the following set of size-change graphs: 30.06/8.83 *R(c(x1)) -> R(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (18) 30.06/8.83 YES 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (19) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 S(c(x1)) -> S(x1) 30.06/8.83 S(r(x1)) -> S(x1) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (20) UsableRulesProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (21) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 S(c(x1)) -> S(x1) 30.06/8.83 S(r(x1)) -> S(x1) 30.06/8.83 30.06/8.83 R is empty. 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (22) QDPSizeChangeProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 30.06/8.83 From the DPs we obtained the following set of size-change graphs: 30.06/8.83 *S(c(x1)) -> S(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 *S(r(x1)) -> S(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (23) 30.06/8.83 YES 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (24) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 U(s(x1)) -> U(x1) 30.06/8.83 U(r(x1)) -> U(x1) 30.06/8.83 U(n(x1)) -> U(x1) 30.06/8.83 U(c(x1)) -> U(x1) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (25) UsableRulesProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (26) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 U(s(x1)) -> U(x1) 30.06/8.83 U(r(x1)) -> U(x1) 30.06/8.83 U(n(x1)) -> U(x1) 30.06/8.83 U(c(x1)) -> U(x1) 30.06/8.83 30.06/8.83 R is empty. 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (27) QDPSizeChangeProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 30.06/8.83 From the DPs we obtained the following set of size-change graphs: 30.06/8.83 *U(s(x1)) -> U(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 *U(r(x1)) -> U(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 *U(n(x1)) -> U(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 *U(c(x1)) -> U(x1) 30.06/8.83 The graph contains the following edges 1 > 1 30.06/8.83 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (28) 30.06/8.83 YES 30.06/8.83 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (29) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 B(r(x1)) -> B(s(u(x1))) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 b(r(x1)) -> b(s(u(x1))) 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (30) UsableRulesProof (EQUIVALENT) 30.06/8.83 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. 30.06/8.83 ---------------------------------------- 30.06/8.83 30.06/8.83 (31) 30.06/8.83 Obligation: 30.06/8.83 Q DP problem: 30.06/8.83 The TRS P consists of the following rules: 30.06/8.83 30.06/8.83 B(r(x1)) -> B(s(u(x1))) 30.06/8.83 30.06/8.83 The TRS R consists of the following rules: 30.06/8.83 30.06/8.83 u(r(x1)) -> r(u(x1)) 30.06/8.83 u(s(x1)) -> s(u(x1)) 30.06/8.83 u(n(x1)) -> n(u(x1)) 30.06/8.83 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.83 u(c(x1)) -> c(u(x1)) 30.06/8.83 s(r(x1)) -> r(s(x1)) 30.06/8.83 s(c(x1)) -> c(s(x1)) 30.06/8.83 r(c(x1)) -> c(r(x1)) 30.06/8.83 n(c(x1)) -> c(n(x1)) 30.06/8.83 n(c(x1)) -> n(x1) 30.06/8.83 30.06/8.83 Q is empty. 30.06/8.83 We have to consider all minimal (P,Q,R)-chains. 30.06/8.83 ---------------------------------------- 30.06/8.84 30.06/8.84 (32) QDPOrderProof (EQUIVALENT) 30.06/8.84 We use the reduction pair processor [LPAR04,JAR06]. 30.06/8.84 30.06/8.84 30.06/8.84 The following pairs can be oriented strictly and are deleted. 30.06/8.84 30.06/8.84 B(r(x1)) -> B(s(u(x1))) 30.06/8.84 The remaining pairs can at least be oriented weakly. 30.06/8.84 Used ordering: Polynomial interpretation [POLO]: 30.06/8.84 30.06/8.84 POL(B(x_1)) = x_1 30.06/8.84 POL(c(x_1)) = 0 30.06/8.84 POL(n(x_1)) = 1 30.06/8.84 POL(r(x_1)) = 1 + x_1 30.06/8.84 POL(s(x_1)) = x_1 30.06/8.84 POL(t(x_1)) = 1 + x_1 30.06/8.84 POL(u(x_1)) = x_1 30.06/8.84 30.06/8.84 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 30.06/8.84 30.06/8.84 u(r(x1)) -> r(u(x1)) 30.06/8.84 u(s(x1)) -> s(u(x1)) 30.06/8.84 u(n(x1)) -> n(u(x1)) 30.06/8.84 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.84 u(c(x1)) -> c(u(x1)) 30.06/8.84 s(r(x1)) -> r(s(x1)) 30.06/8.84 s(c(x1)) -> c(s(x1)) 30.06/8.84 r(c(x1)) -> c(r(x1)) 30.06/8.84 n(c(x1)) -> c(n(x1)) 30.06/8.84 n(c(x1)) -> n(x1) 30.06/8.84 30.06/8.84 30.06/8.84 ---------------------------------------- 30.06/8.84 30.06/8.84 (33) 30.06/8.84 Obligation: 30.06/8.84 Q DP problem: 30.06/8.84 P is empty. 30.06/8.84 The TRS R consists of the following rules: 30.06/8.84 30.06/8.84 u(r(x1)) -> r(u(x1)) 30.06/8.84 u(s(x1)) -> s(u(x1)) 30.06/8.84 u(n(x1)) -> n(u(x1)) 30.06/8.84 u(s(t(x1))) -> r(c(t(x1))) 30.06/8.84 u(c(x1)) -> c(u(x1)) 30.06/8.84 s(r(x1)) -> r(s(x1)) 30.06/8.84 s(c(x1)) -> c(s(x1)) 30.06/8.84 r(c(x1)) -> c(r(x1)) 30.06/8.84 n(c(x1)) -> c(n(x1)) 30.06/8.84 n(c(x1)) -> n(x1) 30.06/8.84 30.06/8.84 Q is empty. 30.06/8.84 We have to consider all minimal (P,Q,R)-chains. 30.06/8.84 ---------------------------------------- 30.06/8.84 30.06/8.84 (34) PisEmptyProof (EQUIVALENT) 30.06/8.84 The TRS P is empty. Hence, there is no (P,Q,R) chain. 30.06/8.84 ---------------------------------------- 30.06/8.84 30.06/8.84 (35) 30.06/8.84 YES 30.82/8.92 EOF