13.49/8.27 YES 13.82/8.29 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 13.82/8.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 13.82/8.29 13.82/8.29 13.82/8.29 Termination w.r.t. Q of the given QTRS could be proven: 13.82/8.29 13.82/8.29 (0) QTRS 13.82/8.29 (1) DependencyPairsProof [EQUIVALENT, 33 ms] 13.82/8.29 (2) QDP 13.82/8.29 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 13.82/8.29 (4) AND 13.82/8.29 (5) QDP 13.82/8.29 (6) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (7) QDP 13.82/8.29 (8) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (9) QDP 13.82/8.29 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (11) YES 13.82/8.29 (12) QDP 13.82/8.29 (13) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (14) QDP 13.82/8.29 (15) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (16) QDP 13.82/8.29 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (18) YES 13.82/8.29 (19) QDP 13.82/8.29 (20) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (21) QDP 13.82/8.29 (22) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (23) QDP 13.82/8.29 (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (25) YES 13.82/8.29 (26) QDP 13.82/8.29 (27) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (28) QDP 13.82/8.29 (29) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (30) QDP 13.82/8.29 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (32) YES 13.82/8.29 (33) QDP 13.82/8.29 (34) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (35) QDP 13.82/8.29 (36) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (37) QDP 13.82/8.29 (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (39) YES 13.82/8.29 (40) QDP 13.82/8.29 (41) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (42) QDP 13.82/8.29 (43) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (44) QDP 13.82/8.29 (45) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (46) YES 13.82/8.29 (47) QDP 13.82/8.29 (48) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (49) QDP 13.82/8.29 (50) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (51) QDP 13.82/8.29 (52) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (53) YES 13.82/8.29 (54) QDP 13.82/8.29 (55) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (56) QDP 13.82/8.29 (57) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (58) QDP 13.82/8.29 (59) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (60) YES 13.82/8.29 (61) QDP 13.82/8.29 (62) QDPQMonotonicMRRProof [EQUIVALENT, 169 ms] 13.82/8.29 (63) QDP 13.82/8.29 (64) QDPOrderProof [EQUIVALENT, 363 ms] 13.82/8.29 (65) QDP 13.82/8.29 (66) UsableRulesProof [EQUIVALENT, 0 ms] 13.82/8.29 (67) QDP 13.82/8.29 (68) QReductionProof [EQUIVALENT, 0 ms] 13.82/8.29 (69) QDP 13.82/8.29 (70) QDPSizeChangeProof [EQUIVALENT, 0 ms] 13.82/8.29 (71) YES 13.82/8.29 13.82/8.29 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (0) 13.82/8.29 Obligation: 13.82/8.29 Q restricted rewrite system: 13.82/8.29 The TRS R consists of the following rules: 13.82/8.29 13.82/8.29 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.82/8.29 active(sqr(0)) -> mark(0) 13.82/8.29 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.82/8.29 active(dbl(0)) -> mark(0) 13.82/8.29 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.82/8.29 active(add(0, X)) -> mark(X) 13.82/8.29 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.82/8.29 active(first(0, X)) -> mark(nil) 13.82/8.29 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.82/8.29 mark(terms(X)) -> active(terms(mark(X))) 13.82/8.29 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.82/8.29 mark(recip(X)) -> active(recip(mark(X))) 13.82/8.29 mark(sqr(X)) -> active(sqr(mark(X))) 13.82/8.29 mark(s(X)) -> active(s(mark(X))) 13.82/8.29 mark(0) -> active(0) 13.82/8.29 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.82/8.29 mark(dbl(X)) -> active(dbl(mark(X))) 13.82/8.29 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.82/8.29 mark(nil) -> active(nil) 13.82/8.29 terms(mark(X)) -> terms(X) 13.82/8.29 terms(active(X)) -> terms(X) 13.82/8.29 cons(mark(X1), X2) -> cons(X1, X2) 13.82/8.29 cons(X1, mark(X2)) -> cons(X1, X2) 13.82/8.29 cons(active(X1), X2) -> cons(X1, X2) 13.82/8.29 cons(X1, active(X2)) -> cons(X1, X2) 13.82/8.29 recip(mark(X)) -> recip(X) 13.82/8.29 recip(active(X)) -> recip(X) 13.82/8.29 sqr(mark(X)) -> sqr(X) 13.82/8.29 sqr(active(X)) -> sqr(X) 13.82/8.29 s(mark(X)) -> s(X) 13.82/8.29 s(active(X)) -> s(X) 13.82/8.29 add(mark(X1), X2) -> add(X1, X2) 13.82/8.29 add(X1, mark(X2)) -> add(X1, X2) 13.82/8.29 add(active(X1), X2) -> add(X1, X2) 13.82/8.29 add(X1, active(X2)) -> add(X1, X2) 13.82/8.29 dbl(mark(X)) -> dbl(X) 13.82/8.29 dbl(active(X)) -> dbl(X) 13.82/8.29 first(mark(X1), X2) -> first(X1, X2) 13.82/8.29 first(X1, mark(X2)) -> first(X1, X2) 13.82/8.29 first(active(X1), X2) -> first(X1, X2) 13.82/8.29 first(X1, active(X2)) -> first(X1, X2) 13.82/8.29 13.82/8.29 The set Q consists of the following terms: 13.82/8.29 13.82/8.29 active(terms(x0)) 13.82/8.29 active(sqr(0)) 13.82/8.29 active(sqr(s(x0))) 13.82/8.29 active(dbl(0)) 13.82/8.29 active(dbl(s(x0))) 13.82/8.29 active(add(0, x0)) 13.82/8.29 active(add(s(x0), x1)) 13.82/8.29 active(first(0, x0)) 13.82/8.29 active(first(s(x0), cons(x1, x2))) 13.82/8.29 mark(terms(x0)) 13.82/8.29 mark(cons(x0, x1)) 13.82/8.29 mark(recip(x0)) 13.82/8.29 mark(sqr(x0)) 13.82/8.29 mark(s(x0)) 13.82/8.29 mark(0) 13.82/8.29 mark(add(x0, x1)) 13.82/8.29 mark(dbl(x0)) 13.82/8.29 mark(first(x0, x1)) 13.82/8.29 mark(nil) 13.82/8.29 terms(mark(x0)) 13.82/8.29 terms(active(x0)) 13.82/8.29 cons(mark(x0), x1) 13.82/8.29 cons(x0, mark(x1)) 13.82/8.29 cons(active(x0), x1) 13.82/8.29 cons(x0, active(x1)) 13.82/8.29 recip(mark(x0)) 13.82/8.29 recip(active(x0)) 13.82/8.29 sqr(mark(x0)) 13.82/8.29 sqr(active(x0)) 13.82/8.29 s(mark(x0)) 13.82/8.29 s(active(x0)) 13.82/8.29 add(mark(x0), x1) 13.82/8.29 add(x0, mark(x1)) 13.82/8.29 add(active(x0), x1) 13.82/8.29 add(x0, active(x1)) 13.82/8.29 dbl(mark(x0)) 13.82/8.29 dbl(active(x0)) 13.82/8.29 first(mark(x0), x1) 13.82/8.29 first(x0, mark(x1)) 13.82/8.29 first(active(x0), x1) 13.82/8.29 first(x0, active(x1)) 13.82/8.29 13.82/8.29 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (1) DependencyPairsProof (EQUIVALENT) 13.82/8.29 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (2) 13.82/8.29 Obligation: 13.82/8.29 Q DP problem: 13.82/8.29 The TRS P consists of the following rules: 13.82/8.29 13.82/8.29 ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N)))) 13.82/8.29 ACTIVE(terms(N)) -> CONS(recip(sqr(N)), terms(s(N))) 13.82/8.29 ACTIVE(terms(N)) -> RECIP(sqr(N)) 13.82/8.29 ACTIVE(terms(N)) -> SQR(N) 13.82/8.29 ACTIVE(terms(N)) -> TERMS(s(N)) 13.82/8.29 ACTIVE(terms(N)) -> S(N) 13.82/8.29 ACTIVE(sqr(0)) -> MARK(0) 13.82/8.29 ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X)))) 13.82/8.29 ACTIVE(sqr(s(X))) -> S(add(sqr(X), dbl(X))) 13.82/8.29 ACTIVE(sqr(s(X))) -> ADD(sqr(X), dbl(X)) 13.82/8.29 ACTIVE(sqr(s(X))) -> SQR(X) 13.82/8.29 ACTIVE(sqr(s(X))) -> DBL(X) 13.82/8.29 ACTIVE(dbl(0)) -> MARK(0) 13.82/8.29 ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X)))) 13.82/8.29 ACTIVE(dbl(s(X))) -> S(s(dbl(X))) 13.82/8.29 ACTIVE(dbl(s(X))) -> S(dbl(X)) 13.82/8.29 ACTIVE(dbl(s(X))) -> DBL(X) 13.82/8.29 ACTIVE(add(0, X)) -> MARK(X) 13.82/8.29 ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) 13.82/8.29 ACTIVE(add(s(X), Y)) -> S(add(X, Y)) 13.82/8.29 ACTIVE(add(s(X), Y)) -> ADD(X, Y) 13.82/8.29 ACTIVE(first(0, X)) -> MARK(nil) 13.82/8.29 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 13.82/8.29 ACTIVE(first(s(X), cons(Y, Z))) -> CONS(Y, first(X, Z)) 13.82/8.29 ACTIVE(first(s(X), cons(Y, Z))) -> FIRST(X, Z) 13.82/8.29 MARK(terms(X)) -> ACTIVE(terms(mark(X))) 13.82/8.29 MARK(terms(X)) -> TERMS(mark(X)) 13.82/8.29 MARK(terms(X)) -> MARK(X) 13.82/8.29 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 13.82/8.29 MARK(cons(X1, X2)) -> CONS(mark(X1), X2) 13.82/8.29 MARK(cons(X1, X2)) -> MARK(X1) 13.82/8.29 MARK(recip(X)) -> ACTIVE(recip(mark(X))) 13.82/8.29 MARK(recip(X)) -> RECIP(mark(X)) 13.82/8.29 MARK(recip(X)) -> MARK(X) 13.82/8.29 MARK(sqr(X)) -> ACTIVE(sqr(mark(X))) 13.82/8.29 MARK(sqr(X)) -> SQR(mark(X)) 13.82/8.29 MARK(sqr(X)) -> MARK(X) 13.82/8.29 MARK(s(X)) -> ACTIVE(s(mark(X))) 13.82/8.29 MARK(s(X)) -> S(mark(X)) 13.82/8.29 MARK(s(X)) -> MARK(X) 13.82/8.29 MARK(0) -> ACTIVE(0) 13.82/8.29 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 13.82/8.29 MARK(add(X1, X2)) -> ADD(mark(X1), mark(X2)) 13.82/8.29 MARK(add(X1, X2)) -> MARK(X1) 13.82/8.29 MARK(add(X1, X2)) -> MARK(X2) 13.82/8.29 MARK(dbl(X)) -> ACTIVE(dbl(mark(X))) 13.82/8.29 MARK(dbl(X)) -> DBL(mark(X)) 13.82/8.29 MARK(dbl(X)) -> MARK(X) 13.82/8.29 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 13.82/8.29 MARK(first(X1, X2)) -> FIRST(mark(X1), mark(X2)) 13.82/8.29 MARK(first(X1, X2)) -> MARK(X1) 13.82/8.29 MARK(first(X1, X2)) -> MARK(X2) 13.82/8.29 MARK(nil) -> ACTIVE(nil) 13.82/8.29 TERMS(mark(X)) -> TERMS(X) 13.82/8.29 TERMS(active(X)) -> TERMS(X) 13.82/8.29 CONS(mark(X1), X2) -> CONS(X1, X2) 13.82/8.29 CONS(X1, mark(X2)) -> CONS(X1, X2) 13.82/8.29 CONS(active(X1), X2) -> CONS(X1, X2) 13.82/8.29 CONS(X1, active(X2)) -> CONS(X1, X2) 13.82/8.29 RECIP(mark(X)) -> RECIP(X) 13.82/8.29 RECIP(active(X)) -> RECIP(X) 13.82/8.29 SQR(mark(X)) -> SQR(X) 13.82/8.29 SQR(active(X)) -> SQR(X) 13.82/8.29 S(mark(X)) -> S(X) 13.82/8.29 S(active(X)) -> S(X) 13.82/8.29 ADD(mark(X1), X2) -> ADD(X1, X2) 13.82/8.29 ADD(X1, mark(X2)) -> ADD(X1, X2) 13.82/8.29 ADD(active(X1), X2) -> ADD(X1, X2) 13.82/8.29 ADD(X1, active(X2)) -> ADD(X1, X2) 13.82/8.29 DBL(mark(X)) -> DBL(X) 13.82/8.29 DBL(active(X)) -> DBL(X) 13.82/8.29 FIRST(mark(X1), X2) -> FIRST(X1, X2) 13.82/8.29 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 13.82/8.29 FIRST(active(X1), X2) -> FIRST(X1, X2) 13.82/8.29 FIRST(X1, active(X2)) -> FIRST(X1, X2) 13.82/8.29 13.82/8.29 The TRS R consists of the following rules: 13.82/8.29 13.82/8.29 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.82/8.29 active(sqr(0)) -> mark(0) 13.82/8.29 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.82/8.29 active(dbl(0)) -> mark(0) 13.82/8.29 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.82/8.29 active(add(0, X)) -> mark(X) 13.82/8.29 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.82/8.29 active(first(0, X)) -> mark(nil) 13.82/8.29 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.82/8.29 mark(terms(X)) -> active(terms(mark(X))) 13.82/8.29 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.82/8.29 mark(recip(X)) -> active(recip(mark(X))) 13.82/8.29 mark(sqr(X)) -> active(sqr(mark(X))) 13.82/8.29 mark(s(X)) -> active(s(mark(X))) 13.82/8.29 mark(0) -> active(0) 13.82/8.29 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.82/8.29 mark(dbl(X)) -> active(dbl(mark(X))) 13.82/8.29 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.82/8.29 mark(nil) -> active(nil) 13.82/8.29 terms(mark(X)) -> terms(X) 13.82/8.29 terms(active(X)) -> terms(X) 13.82/8.29 cons(mark(X1), X2) -> cons(X1, X2) 13.82/8.29 cons(X1, mark(X2)) -> cons(X1, X2) 13.82/8.29 cons(active(X1), X2) -> cons(X1, X2) 13.82/8.29 cons(X1, active(X2)) -> cons(X1, X2) 13.82/8.29 recip(mark(X)) -> recip(X) 13.82/8.29 recip(active(X)) -> recip(X) 13.82/8.29 sqr(mark(X)) -> sqr(X) 13.82/8.29 sqr(active(X)) -> sqr(X) 13.82/8.29 s(mark(X)) -> s(X) 13.82/8.29 s(active(X)) -> s(X) 13.82/8.29 add(mark(X1), X2) -> add(X1, X2) 13.82/8.29 add(X1, mark(X2)) -> add(X1, X2) 13.82/8.29 add(active(X1), X2) -> add(X1, X2) 13.82/8.29 add(X1, active(X2)) -> add(X1, X2) 13.82/8.29 dbl(mark(X)) -> dbl(X) 13.82/8.29 dbl(active(X)) -> dbl(X) 13.82/8.29 first(mark(X1), X2) -> first(X1, X2) 13.82/8.29 first(X1, mark(X2)) -> first(X1, X2) 13.82/8.29 first(active(X1), X2) -> first(X1, X2) 13.82/8.29 first(X1, active(X2)) -> first(X1, X2) 13.82/8.29 13.82/8.29 The set Q consists of the following terms: 13.82/8.29 13.82/8.29 active(terms(x0)) 13.82/8.29 active(sqr(0)) 13.82/8.29 active(sqr(s(x0))) 13.82/8.29 active(dbl(0)) 13.82/8.29 active(dbl(s(x0))) 13.82/8.29 active(add(0, x0)) 13.82/8.29 active(add(s(x0), x1)) 13.82/8.29 active(first(0, x0)) 13.82/8.29 active(first(s(x0), cons(x1, x2))) 13.82/8.29 mark(terms(x0)) 13.82/8.29 mark(cons(x0, x1)) 13.82/8.29 mark(recip(x0)) 13.82/8.29 mark(sqr(x0)) 13.82/8.29 mark(s(x0)) 13.82/8.29 mark(0) 13.82/8.29 mark(add(x0, x1)) 13.82/8.29 mark(dbl(x0)) 13.82/8.29 mark(first(x0, x1)) 13.82/8.29 mark(nil) 13.82/8.29 terms(mark(x0)) 13.82/8.29 terms(active(x0)) 13.82/8.29 cons(mark(x0), x1) 13.82/8.29 cons(x0, mark(x1)) 13.82/8.29 cons(active(x0), x1) 13.82/8.29 cons(x0, active(x1)) 13.82/8.29 recip(mark(x0)) 13.82/8.29 recip(active(x0)) 13.82/8.29 sqr(mark(x0)) 13.82/8.29 sqr(active(x0)) 13.82/8.29 s(mark(x0)) 13.82/8.29 s(active(x0)) 13.82/8.29 add(mark(x0), x1) 13.82/8.29 add(x0, mark(x1)) 13.82/8.29 add(active(x0), x1) 13.82/8.29 add(x0, active(x1)) 13.82/8.29 dbl(mark(x0)) 13.82/8.29 dbl(active(x0)) 13.82/8.29 first(mark(x0), x1) 13.82/8.29 first(x0, mark(x1)) 13.82/8.29 first(active(x0), x1) 13.82/8.29 first(x0, active(x1)) 13.82/8.29 13.82/8.29 We have to consider all minimal (P,Q,R)-chains. 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (3) DependencyGraphProof (EQUIVALENT) 13.82/8.29 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 9 SCCs with 29 less nodes. 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (4) 13.82/8.29 Complex Obligation (AND) 13.82/8.29 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (5) 13.82/8.29 Obligation: 13.82/8.29 Q DP problem: 13.82/8.29 The TRS P consists of the following rules: 13.82/8.29 13.82/8.29 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 13.82/8.29 FIRST(mark(X1), X2) -> FIRST(X1, X2) 13.82/8.29 FIRST(active(X1), X2) -> FIRST(X1, X2) 13.82/8.29 FIRST(X1, active(X2)) -> FIRST(X1, X2) 13.82/8.29 13.82/8.29 The TRS R consists of the following rules: 13.82/8.29 13.82/8.29 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.82/8.29 active(sqr(0)) -> mark(0) 13.82/8.29 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.82/8.29 active(dbl(0)) -> mark(0) 13.82/8.29 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.82/8.29 active(add(0, X)) -> mark(X) 13.82/8.29 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.82/8.29 active(first(0, X)) -> mark(nil) 13.82/8.29 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.82/8.29 mark(terms(X)) -> active(terms(mark(X))) 13.82/8.29 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.82/8.29 mark(recip(X)) -> active(recip(mark(X))) 13.82/8.29 mark(sqr(X)) -> active(sqr(mark(X))) 13.82/8.29 mark(s(X)) -> active(s(mark(X))) 13.82/8.29 mark(0) -> active(0) 13.82/8.29 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.82/8.29 mark(dbl(X)) -> active(dbl(mark(X))) 13.82/8.29 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.82/8.29 mark(nil) -> active(nil) 13.82/8.29 terms(mark(X)) -> terms(X) 13.82/8.29 terms(active(X)) -> terms(X) 13.82/8.29 cons(mark(X1), X2) -> cons(X1, X2) 13.82/8.29 cons(X1, mark(X2)) -> cons(X1, X2) 13.82/8.29 cons(active(X1), X2) -> cons(X1, X2) 13.82/8.29 cons(X1, active(X2)) -> cons(X1, X2) 13.82/8.29 recip(mark(X)) -> recip(X) 13.82/8.29 recip(active(X)) -> recip(X) 13.82/8.29 sqr(mark(X)) -> sqr(X) 13.82/8.29 sqr(active(X)) -> sqr(X) 13.82/8.29 s(mark(X)) -> s(X) 13.82/8.29 s(active(X)) -> s(X) 13.82/8.29 add(mark(X1), X2) -> add(X1, X2) 13.82/8.29 add(X1, mark(X2)) -> add(X1, X2) 13.82/8.29 add(active(X1), X2) -> add(X1, X2) 13.82/8.29 add(X1, active(X2)) -> add(X1, X2) 13.82/8.29 dbl(mark(X)) -> dbl(X) 13.82/8.29 dbl(active(X)) -> dbl(X) 13.82/8.29 first(mark(X1), X2) -> first(X1, X2) 13.82/8.29 first(X1, mark(X2)) -> first(X1, X2) 13.82/8.29 first(active(X1), X2) -> first(X1, X2) 13.82/8.29 first(X1, active(X2)) -> first(X1, X2) 13.82/8.29 13.82/8.29 The set Q consists of the following terms: 13.82/8.29 13.82/8.29 active(terms(x0)) 13.82/8.29 active(sqr(0)) 13.82/8.29 active(sqr(s(x0))) 13.82/8.29 active(dbl(0)) 13.82/8.29 active(dbl(s(x0))) 13.82/8.29 active(add(0, x0)) 13.82/8.29 active(add(s(x0), x1)) 13.82/8.29 active(first(0, x0)) 13.82/8.29 active(first(s(x0), cons(x1, x2))) 13.82/8.29 mark(terms(x0)) 13.82/8.29 mark(cons(x0, x1)) 13.82/8.29 mark(recip(x0)) 13.82/8.29 mark(sqr(x0)) 13.82/8.29 mark(s(x0)) 13.82/8.29 mark(0) 13.82/8.29 mark(add(x0, x1)) 13.82/8.29 mark(dbl(x0)) 13.82/8.29 mark(first(x0, x1)) 13.82/8.29 mark(nil) 13.82/8.29 terms(mark(x0)) 13.82/8.29 terms(active(x0)) 13.82/8.29 cons(mark(x0), x1) 13.82/8.29 cons(x0, mark(x1)) 13.82/8.29 cons(active(x0), x1) 13.82/8.29 cons(x0, active(x1)) 13.82/8.29 recip(mark(x0)) 13.82/8.29 recip(active(x0)) 13.82/8.29 sqr(mark(x0)) 13.82/8.29 sqr(active(x0)) 13.82/8.29 s(mark(x0)) 13.82/8.29 s(active(x0)) 13.82/8.29 add(mark(x0), x1) 13.82/8.29 add(x0, mark(x1)) 13.82/8.29 add(active(x0), x1) 13.82/8.29 add(x0, active(x1)) 13.82/8.29 dbl(mark(x0)) 13.82/8.29 dbl(active(x0)) 13.82/8.29 first(mark(x0), x1) 13.82/8.29 first(x0, mark(x1)) 13.82/8.29 first(active(x0), x1) 13.82/8.29 first(x0, active(x1)) 13.82/8.29 13.82/8.29 We have to consider all minimal (P,Q,R)-chains. 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (6) UsableRulesProof (EQUIVALENT) 13.82/8.29 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. 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (7) 13.82/8.29 Obligation: 13.82/8.29 Q DP problem: 13.82/8.29 The TRS P consists of the following rules: 13.82/8.29 13.82/8.29 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 13.82/8.29 FIRST(mark(X1), X2) -> FIRST(X1, X2) 13.82/8.29 FIRST(active(X1), X2) -> FIRST(X1, X2) 13.82/8.29 FIRST(X1, active(X2)) -> FIRST(X1, X2) 13.82/8.29 13.82/8.29 R is empty. 13.82/8.29 The set Q consists of the following terms: 13.82/8.29 13.82/8.29 active(terms(x0)) 13.82/8.29 active(sqr(0)) 13.82/8.29 active(sqr(s(x0))) 13.82/8.29 active(dbl(0)) 13.82/8.29 active(dbl(s(x0))) 13.82/8.29 active(add(0, x0)) 13.82/8.29 active(add(s(x0), x1)) 13.82/8.29 active(first(0, x0)) 13.82/8.29 active(first(s(x0), cons(x1, x2))) 13.82/8.29 mark(terms(x0)) 13.82/8.29 mark(cons(x0, x1)) 13.82/8.29 mark(recip(x0)) 13.82/8.29 mark(sqr(x0)) 13.82/8.29 mark(s(x0)) 13.82/8.29 mark(0) 13.82/8.29 mark(add(x0, x1)) 13.82/8.29 mark(dbl(x0)) 13.82/8.29 mark(first(x0, x1)) 13.82/8.29 mark(nil) 13.82/8.29 terms(mark(x0)) 13.82/8.29 terms(active(x0)) 13.82/8.29 cons(mark(x0), x1) 13.82/8.29 cons(x0, mark(x1)) 13.82/8.29 cons(active(x0), x1) 13.82/8.29 cons(x0, active(x1)) 13.82/8.29 recip(mark(x0)) 13.82/8.29 recip(active(x0)) 13.82/8.29 sqr(mark(x0)) 13.82/8.29 sqr(active(x0)) 13.82/8.29 s(mark(x0)) 13.82/8.29 s(active(x0)) 13.82/8.29 add(mark(x0), x1) 13.82/8.29 add(x0, mark(x1)) 13.82/8.29 add(active(x0), x1) 13.82/8.29 add(x0, active(x1)) 13.82/8.29 dbl(mark(x0)) 13.82/8.29 dbl(active(x0)) 13.82/8.29 first(mark(x0), x1) 13.82/8.29 first(x0, mark(x1)) 13.82/8.29 first(active(x0), x1) 13.82/8.29 first(x0, active(x1)) 13.82/8.29 13.82/8.29 We have to consider all minimal (P,Q,R)-chains. 13.82/8.29 ---------------------------------------- 13.82/8.29 13.82/8.29 (8) QReductionProof (EQUIVALENT) 13.82/8.29 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.29 13.88/8.29 terms(mark(x0)) 13.88/8.29 terms(active(x0)) 13.88/8.29 cons(mark(x0), x1) 13.88/8.29 cons(x0, mark(x1)) 13.88/8.29 cons(active(x0), x1) 13.88/8.29 cons(x0, active(x1)) 13.88/8.29 recip(mark(x0)) 13.88/8.29 recip(active(x0)) 13.88/8.29 sqr(mark(x0)) 13.88/8.29 sqr(active(x0)) 13.88/8.29 s(mark(x0)) 13.88/8.29 s(active(x0)) 13.88/8.29 add(mark(x0), x1) 13.88/8.29 add(x0, mark(x1)) 13.88/8.29 add(active(x0), x1) 13.88/8.29 add(x0, active(x1)) 13.88/8.29 dbl(mark(x0)) 13.88/8.29 dbl(active(x0)) 13.88/8.29 first(mark(x0), x1) 13.88/8.29 first(x0, mark(x1)) 13.88/8.29 first(active(x0), x1) 13.88/8.29 first(x0, active(x1)) 13.88/8.29 13.88/8.29 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (9) 13.88/8.29 Obligation: 13.88/8.29 Q DP problem: 13.88/8.29 The TRS P consists of the following rules: 13.88/8.29 13.88/8.29 FIRST(X1, mark(X2)) -> FIRST(X1, X2) 13.88/8.29 FIRST(mark(X1), X2) -> FIRST(X1, X2) 13.88/8.29 FIRST(active(X1), X2) -> FIRST(X1, X2) 13.88/8.29 FIRST(X1, active(X2)) -> FIRST(X1, X2) 13.88/8.29 13.88/8.29 R is empty. 13.88/8.29 The set Q consists of the following terms: 13.88/8.29 13.88/8.29 active(terms(x0)) 13.88/8.29 active(sqr(0)) 13.88/8.29 active(sqr(s(x0))) 13.88/8.29 active(dbl(0)) 13.88/8.29 active(dbl(s(x0))) 13.88/8.29 active(add(0, x0)) 13.88/8.29 active(add(s(x0), x1)) 13.88/8.29 active(first(0, x0)) 13.88/8.29 active(first(s(x0), cons(x1, x2))) 13.88/8.29 mark(terms(x0)) 13.88/8.29 mark(cons(x0, x1)) 13.88/8.29 mark(recip(x0)) 13.88/8.29 mark(sqr(x0)) 13.88/8.29 mark(s(x0)) 13.88/8.29 mark(0) 13.88/8.29 mark(add(x0, x1)) 13.88/8.29 mark(dbl(x0)) 13.88/8.29 mark(first(x0, x1)) 13.88/8.29 mark(nil) 13.88/8.29 13.88/8.29 We have to consider all minimal (P,Q,R)-chains. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (10) QDPSizeChangeProof (EQUIVALENT) 13.88/8.29 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. 13.88/8.29 13.88/8.29 From the DPs we obtained the following set of size-change graphs: 13.88/8.29 *FIRST(X1, mark(X2)) -> FIRST(X1, X2) 13.88/8.29 The graph contains the following edges 1 >= 1, 2 > 2 13.88/8.29 13.88/8.29 13.88/8.29 *FIRST(mark(X1), X2) -> FIRST(X1, X2) 13.88/8.29 The graph contains the following edges 1 > 1, 2 >= 2 13.88/8.29 13.88/8.29 13.88/8.29 *FIRST(active(X1), X2) -> FIRST(X1, X2) 13.88/8.29 The graph contains the following edges 1 > 1, 2 >= 2 13.88/8.29 13.88/8.29 13.88/8.29 *FIRST(X1, active(X2)) -> FIRST(X1, X2) 13.88/8.29 The graph contains the following edges 1 >= 1, 2 > 2 13.88/8.29 13.88/8.29 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (11) 13.88/8.29 YES 13.88/8.29 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (12) 13.88/8.29 Obligation: 13.88/8.29 Q DP problem: 13.88/8.29 The TRS P consists of the following rules: 13.88/8.29 13.88/8.29 DBL(active(X)) -> DBL(X) 13.88/8.29 DBL(mark(X)) -> DBL(X) 13.88/8.29 13.88/8.29 The TRS R consists of the following rules: 13.88/8.29 13.88/8.29 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.29 active(sqr(0)) -> mark(0) 13.88/8.29 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.29 active(dbl(0)) -> mark(0) 13.88/8.29 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.29 active(add(0, X)) -> mark(X) 13.88/8.29 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.29 active(first(0, X)) -> mark(nil) 13.88/8.29 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.29 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.29 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.29 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.29 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.29 mark(s(X)) -> active(s(mark(X))) 13.88/8.29 mark(0) -> active(0) 13.88/8.29 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.29 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.29 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.29 mark(nil) -> active(nil) 13.88/8.29 terms(mark(X)) -> terms(X) 13.88/8.29 terms(active(X)) -> terms(X) 13.88/8.29 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.29 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.29 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.29 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.29 recip(mark(X)) -> recip(X) 13.88/8.29 recip(active(X)) -> recip(X) 13.88/8.29 sqr(mark(X)) -> sqr(X) 13.88/8.29 sqr(active(X)) -> sqr(X) 13.88/8.29 s(mark(X)) -> s(X) 13.88/8.29 s(active(X)) -> s(X) 13.88/8.29 add(mark(X1), X2) -> add(X1, X2) 13.88/8.29 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.29 add(active(X1), X2) -> add(X1, X2) 13.88/8.29 add(X1, active(X2)) -> add(X1, X2) 13.88/8.29 dbl(mark(X)) -> dbl(X) 13.88/8.29 dbl(active(X)) -> dbl(X) 13.88/8.29 first(mark(X1), X2) -> first(X1, X2) 13.88/8.29 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.29 first(active(X1), X2) -> first(X1, X2) 13.88/8.29 first(X1, active(X2)) -> first(X1, X2) 13.88/8.29 13.88/8.29 The set Q consists of the following terms: 13.88/8.29 13.88/8.29 active(terms(x0)) 13.88/8.29 active(sqr(0)) 13.88/8.29 active(sqr(s(x0))) 13.88/8.29 active(dbl(0)) 13.88/8.29 active(dbl(s(x0))) 13.88/8.29 active(add(0, x0)) 13.88/8.29 active(add(s(x0), x1)) 13.88/8.29 active(first(0, x0)) 13.88/8.29 active(first(s(x0), cons(x1, x2))) 13.88/8.29 mark(terms(x0)) 13.88/8.29 mark(cons(x0, x1)) 13.88/8.29 mark(recip(x0)) 13.88/8.29 mark(sqr(x0)) 13.88/8.29 mark(s(x0)) 13.88/8.29 mark(0) 13.88/8.29 mark(add(x0, x1)) 13.88/8.29 mark(dbl(x0)) 13.88/8.29 mark(first(x0, x1)) 13.88/8.29 mark(nil) 13.88/8.29 terms(mark(x0)) 13.88/8.29 terms(active(x0)) 13.88/8.29 cons(mark(x0), x1) 13.88/8.29 cons(x0, mark(x1)) 13.88/8.29 cons(active(x0), x1) 13.88/8.29 cons(x0, active(x1)) 13.88/8.29 recip(mark(x0)) 13.88/8.29 recip(active(x0)) 13.88/8.29 sqr(mark(x0)) 13.88/8.29 sqr(active(x0)) 13.88/8.29 s(mark(x0)) 13.88/8.29 s(active(x0)) 13.88/8.29 add(mark(x0), x1) 13.88/8.29 add(x0, mark(x1)) 13.88/8.29 add(active(x0), x1) 13.88/8.29 add(x0, active(x1)) 13.88/8.29 dbl(mark(x0)) 13.88/8.29 dbl(active(x0)) 13.88/8.29 first(mark(x0), x1) 13.88/8.29 first(x0, mark(x1)) 13.88/8.29 first(active(x0), x1) 13.88/8.29 first(x0, active(x1)) 13.88/8.29 13.88/8.29 We have to consider all minimal (P,Q,R)-chains. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (13) UsableRulesProof (EQUIVALENT) 13.88/8.29 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. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (14) 13.88/8.29 Obligation: 13.88/8.29 Q DP problem: 13.88/8.29 The TRS P consists of the following rules: 13.88/8.29 13.88/8.29 DBL(active(X)) -> DBL(X) 13.88/8.29 DBL(mark(X)) -> DBL(X) 13.88/8.29 13.88/8.29 R is empty. 13.88/8.29 The set Q consists of the following terms: 13.88/8.29 13.88/8.29 active(terms(x0)) 13.88/8.29 active(sqr(0)) 13.88/8.29 active(sqr(s(x0))) 13.88/8.29 active(dbl(0)) 13.88/8.29 active(dbl(s(x0))) 13.88/8.29 active(add(0, x0)) 13.88/8.29 active(add(s(x0), x1)) 13.88/8.29 active(first(0, x0)) 13.88/8.29 active(first(s(x0), cons(x1, x2))) 13.88/8.29 mark(terms(x0)) 13.88/8.29 mark(cons(x0, x1)) 13.88/8.29 mark(recip(x0)) 13.88/8.29 mark(sqr(x0)) 13.88/8.29 mark(s(x0)) 13.88/8.29 mark(0) 13.88/8.29 mark(add(x0, x1)) 13.88/8.29 mark(dbl(x0)) 13.88/8.29 mark(first(x0, x1)) 13.88/8.29 mark(nil) 13.88/8.29 terms(mark(x0)) 13.88/8.29 terms(active(x0)) 13.88/8.29 cons(mark(x0), x1) 13.88/8.29 cons(x0, mark(x1)) 13.88/8.29 cons(active(x0), x1) 13.88/8.29 cons(x0, active(x1)) 13.88/8.29 recip(mark(x0)) 13.88/8.29 recip(active(x0)) 13.88/8.29 sqr(mark(x0)) 13.88/8.29 sqr(active(x0)) 13.88/8.29 s(mark(x0)) 13.88/8.29 s(active(x0)) 13.88/8.29 add(mark(x0), x1) 13.88/8.29 add(x0, mark(x1)) 13.88/8.29 add(active(x0), x1) 13.88/8.29 add(x0, active(x1)) 13.88/8.29 dbl(mark(x0)) 13.88/8.29 dbl(active(x0)) 13.88/8.29 first(mark(x0), x1) 13.88/8.29 first(x0, mark(x1)) 13.88/8.29 first(active(x0), x1) 13.88/8.29 first(x0, active(x1)) 13.88/8.29 13.88/8.29 We have to consider all minimal (P,Q,R)-chains. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (15) QReductionProof (EQUIVALENT) 13.88/8.29 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.29 13.88/8.29 terms(mark(x0)) 13.88/8.29 terms(active(x0)) 13.88/8.29 cons(mark(x0), x1) 13.88/8.29 cons(x0, mark(x1)) 13.88/8.29 cons(active(x0), x1) 13.88/8.29 cons(x0, active(x1)) 13.88/8.29 recip(mark(x0)) 13.88/8.29 recip(active(x0)) 13.88/8.29 sqr(mark(x0)) 13.88/8.29 sqr(active(x0)) 13.88/8.29 s(mark(x0)) 13.88/8.29 s(active(x0)) 13.88/8.29 add(mark(x0), x1) 13.88/8.29 add(x0, mark(x1)) 13.88/8.29 add(active(x0), x1) 13.88/8.29 add(x0, active(x1)) 13.88/8.29 dbl(mark(x0)) 13.88/8.29 dbl(active(x0)) 13.88/8.29 first(mark(x0), x1) 13.88/8.29 first(x0, mark(x1)) 13.88/8.29 first(active(x0), x1) 13.88/8.29 first(x0, active(x1)) 13.88/8.29 13.88/8.29 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (16) 13.88/8.29 Obligation: 13.88/8.29 Q DP problem: 13.88/8.29 The TRS P consists of the following rules: 13.88/8.29 13.88/8.29 DBL(active(X)) -> DBL(X) 13.88/8.29 DBL(mark(X)) -> DBL(X) 13.88/8.29 13.88/8.29 R is empty. 13.88/8.29 The set Q consists of the following terms: 13.88/8.29 13.88/8.29 active(terms(x0)) 13.88/8.29 active(sqr(0)) 13.88/8.29 active(sqr(s(x0))) 13.88/8.29 active(dbl(0)) 13.88/8.29 active(dbl(s(x0))) 13.88/8.29 active(add(0, x0)) 13.88/8.29 active(add(s(x0), x1)) 13.88/8.29 active(first(0, x0)) 13.88/8.29 active(first(s(x0), cons(x1, x2))) 13.88/8.29 mark(terms(x0)) 13.88/8.29 mark(cons(x0, x1)) 13.88/8.29 mark(recip(x0)) 13.88/8.29 mark(sqr(x0)) 13.88/8.29 mark(s(x0)) 13.88/8.29 mark(0) 13.88/8.29 mark(add(x0, x1)) 13.88/8.29 mark(dbl(x0)) 13.88/8.29 mark(first(x0, x1)) 13.88/8.29 mark(nil) 13.88/8.29 13.88/8.29 We have to consider all minimal (P,Q,R)-chains. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (17) QDPSizeChangeProof (EQUIVALENT) 13.88/8.29 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. 13.88/8.29 13.88/8.29 From the DPs we obtained the following set of size-change graphs: 13.88/8.29 *DBL(active(X)) -> DBL(X) 13.88/8.29 The graph contains the following edges 1 > 1 13.88/8.29 13.88/8.29 13.88/8.29 *DBL(mark(X)) -> DBL(X) 13.88/8.29 The graph contains the following edges 1 > 1 13.88/8.29 13.88/8.29 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (18) 13.88/8.29 YES 13.88/8.29 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (19) 13.88/8.29 Obligation: 13.88/8.29 Q DP problem: 13.88/8.29 The TRS P consists of the following rules: 13.88/8.29 13.88/8.29 ADD(X1, mark(X2)) -> ADD(X1, X2) 13.88/8.29 ADD(mark(X1), X2) -> ADD(X1, X2) 13.88/8.29 ADD(active(X1), X2) -> ADD(X1, X2) 13.88/8.29 ADD(X1, active(X2)) -> ADD(X1, X2) 13.88/8.29 13.88/8.29 The TRS R consists of the following rules: 13.88/8.29 13.88/8.29 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.29 active(sqr(0)) -> mark(0) 13.88/8.29 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.29 active(dbl(0)) -> mark(0) 13.88/8.29 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.29 active(add(0, X)) -> mark(X) 13.88/8.29 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.29 active(first(0, X)) -> mark(nil) 13.88/8.29 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.29 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.29 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.29 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.29 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.29 mark(s(X)) -> active(s(mark(X))) 13.88/8.29 mark(0) -> active(0) 13.88/8.29 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.29 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.29 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.29 mark(nil) -> active(nil) 13.88/8.29 terms(mark(X)) -> terms(X) 13.88/8.29 terms(active(X)) -> terms(X) 13.88/8.29 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.29 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.29 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.29 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.29 recip(mark(X)) -> recip(X) 13.88/8.29 recip(active(X)) -> recip(X) 13.88/8.29 sqr(mark(X)) -> sqr(X) 13.88/8.29 sqr(active(X)) -> sqr(X) 13.88/8.29 s(mark(X)) -> s(X) 13.88/8.29 s(active(X)) -> s(X) 13.88/8.29 add(mark(X1), X2) -> add(X1, X2) 13.88/8.29 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.29 add(active(X1), X2) -> add(X1, X2) 13.88/8.29 add(X1, active(X2)) -> add(X1, X2) 13.88/8.29 dbl(mark(X)) -> dbl(X) 13.88/8.29 dbl(active(X)) -> dbl(X) 13.88/8.29 first(mark(X1), X2) -> first(X1, X2) 13.88/8.29 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.29 first(active(X1), X2) -> first(X1, X2) 13.88/8.29 first(X1, active(X2)) -> first(X1, X2) 13.88/8.29 13.88/8.29 The set Q consists of the following terms: 13.88/8.29 13.88/8.29 active(terms(x0)) 13.88/8.29 active(sqr(0)) 13.88/8.29 active(sqr(s(x0))) 13.88/8.29 active(dbl(0)) 13.88/8.29 active(dbl(s(x0))) 13.88/8.29 active(add(0, x0)) 13.88/8.29 active(add(s(x0), x1)) 13.88/8.29 active(first(0, x0)) 13.88/8.29 active(first(s(x0), cons(x1, x2))) 13.88/8.29 mark(terms(x0)) 13.88/8.29 mark(cons(x0, x1)) 13.88/8.29 mark(recip(x0)) 13.88/8.29 mark(sqr(x0)) 13.88/8.29 mark(s(x0)) 13.88/8.29 mark(0) 13.88/8.29 mark(add(x0, x1)) 13.88/8.29 mark(dbl(x0)) 13.88/8.29 mark(first(x0, x1)) 13.88/8.29 mark(nil) 13.88/8.29 terms(mark(x0)) 13.88/8.29 terms(active(x0)) 13.88/8.29 cons(mark(x0), x1) 13.88/8.29 cons(x0, mark(x1)) 13.88/8.29 cons(active(x0), x1) 13.88/8.29 cons(x0, active(x1)) 13.88/8.29 recip(mark(x0)) 13.88/8.29 recip(active(x0)) 13.88/8.29 sqr(mark(x0)) 13.88/8.29 sqr(active(x0)) 13.88/8.29 s(mark(x0)) 13.88/8.29 s(active(x0)) 13.88/8.29 add(mark(x0), x1) 13.88/8.29 add(x0, mark(x1)) 13.88/8.29 add(active(x0), x1) 13.88/8.29 add(x0, active(x1)) 13.88/8.29 dbl(mark(x0)) 13.88/8.29 dbl(active(x0)) 13.88/8.29 first(mark(x0), x1) 13.88/8.29 first(x0, mark(x1)) 13.88/8.29 first(active(x0), x1) 13.88/8.29 first(x0, active(x1)) 13.88/8.29 13.88/8.29 We have to consider all minimal (P,Q,R)-chains. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (20) UsableRulesProof (EQUIVALENT) 13.88/8.29 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. 13.88/8.29 ---------------------------------------- 13.88/8.29 13.88/8.29 (21) 13.88/8.29 Obligation: 13.88/8.29 Q DP problem: 13.88/8.29 The TRS P consists of the following rules: 13.88/8.29 13.88/8.29 ADD(X1, mark(X2)) -> ADD(X1, X2) 13.88/8.29 ADD(mark(X1), X2) -> ADD(X1, X2) 13.88/8.29 ADD(active(X1), X2) -> ADD(X1, X2) 13.88/8.29 ADD(X1, active(X2)) -> ADD(X1, X2) 13.88/8.29 13.88/8.29 R is empty. 13.88/8.29 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (22) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (23) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 ADD(X1, mark(X2)) -> ADD(X1, X2) 13.88/8.30 ADD(mark(X1), X2) -> ADD(X1, X2) 13.88/8.30 ADD(active(X1), X2) -> ADD(X1, X2) 13.88/8.30 ADD(X1, active(X2)) -> ADD(X1, X2) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (24) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *ADD(X1, mark(X2)) -> ADD(X1, X2) 13.88/8.30 The graph contains the following edges 1 >= 1, 2 > 2 13.88/8.30 13.88/8.30 13.88/8.30 *ADD(mark(X1), X2) -> ADD(X1, X2) 13.88/8.30 The graph contains the following edges 1 > 1, 2 >= 2 13.88/8.30 13.88/8.30 13.88/8.30 *ADD(active(X1), X2) -> ADD(X1, X2) 13.88/8.30 The graph contains the following edges 1 > 1, 2 >= 2 13.88/8.30 13.88/8.30 13.88/8.30 *ADD(X1, active(X2)) -> ADD(X1, X2) 13.88/8.30 The graph contains the following edges 1 >= 1, 2 > 2 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (25) 13.88/8.30 YES 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (26) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 S(active(X)) -> S(X) 13.88/8.30 S(mark(X)) -> S(X) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (27) UsableRulesProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (28) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 S(active(X)) -> S(X) 13.88/8.30 S(mark(X)) -> S(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (29) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (30) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 S(active(X)) -> S(X) 13.88/8.30 S(mark(X)) -> S(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (31) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *S(active(X)) -> S(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 *S(mark(X)) -> S(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (32) 13.88/8.30 YES 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (33) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 SQR(active(X)) -> SQR(X) 13.88/8.30 SQR(mark(X)) -> SQR(X) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (34) UsableRulesProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (35) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 SQR(active(X)) -> SQR(X) 13.88/8.30 SQR(mark(X)) -> SQR(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (36) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (37) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 SQR(active(X)) -> SQR(X) 13.88/8.30 SQR(mark(X)) -> SQR(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (38) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *SQR(active(X)) -> SQR(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 *SQR(mark(X)) -> SQR(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (39) 13.88/8.30 YES 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (40) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 RECIP(active(X)) -> RECIP(X) 13.88/8.30 RECIP(mark(X)) -> RECIP(X) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (41) UsableRulesProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (42) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 RECIP(active(X)) -> RECIP(X) 13.88/8.30 RECIP(mark(X)) -> RECIP(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (43) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (44) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 RECIP(active(X)) -> RECIP(X) 13.88/8.30 RECIP(mark(X)) -> RECIP(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (45) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *RECIP(active(X)) -> RECIP(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 *RECIP(mark(X)) -> RECIP(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (46) 13.88/8.30 YES 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (47) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 CONS(X1, mark(X2)) -> CONS(X1, X2) 13.88/8.30 CONS(mark(X1), X2) -> CONS(X1, X2) 13.88/8.30 CONS(active(X1), X2) -> CONS(X1, X2) 13.88/8.30 CONS(X1, active(X2)) -> CONS(X1, X2) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (48) UsableRulesProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (49) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 CONS(X1, mark(X2)) -> CONS(X1, X2) 13.88/8.30 CONS(mark(X1), X2) -> CONS(X1, X2) 13.88/8.30 CONS(active(X1), X2) -> CONS(X1, X2) 13.88/8.30 CONS(X1, active(X2)) -> CONS(X1, X2) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (50) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (51) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 CONS(X1, mark(X2)) -> CONS(X1, X2) 13.88/8.30 CONS(mark(X1), X2) -> CONS(X1, X2) 13.88/8.30 CONS(active(X1), X2) -> CONS(X1, X2) 13.88/8.30 CONS(X1, active(X2)) -> CONS(X1, X2) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (52) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *CONS(X1, mark(X2)) -> CONS(X1, X2) 13.88/8.30 The graph contains the following edges 1 >= 1, 2 > 2 13.88/8.30 13.88/8.30 13.88/8.30 *CONS(mark(X1), X2) -> CONS(X1, X2) 13.88/8.30 The graph contains the following edges 1 > 1, 2 >= 2 13.88/8.30 13.88/8.30 13.88/8.30 *CONS(active(X1), X2) -> CONS(X1, X2) 13.88/8.30 The graph contains the following edges 1 > 1, 2 >= 2 13.88/8.30 13.88/8.30 13.88/8.30 *CONS(X1, active(X2)) -> CONS(X1, X2) 13.88/8.30 The graph contains the following edges 1 >= 1, 2 > 2 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (53) 13.88/8.30 YES 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (54) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 TERMS(active(X)) -> TERMS(X) 13.88/8.30 TERMS(mark(X)) -> TERMS(X) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (55) UsableRulesProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (56) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 TERMS(active(X)) -> TERMS(X) 13.88/8.30 TERMS(mark(X)) -> TERMS(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (57) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (58) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 TERMS(active(X)) -> TERMS(X) 13.88/8.30 TERMS(mark(X)) -> TERMS(X) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (59) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *TERMS(active(X)) -> TERMS(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 *TERMS(mark(X)) -> TERMS(X) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (60) 13.88/8.30 YES 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (61) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 13.88/8.30 ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 MARK(cons(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(terms(X)) -> ACTIVE(terms(mark(X))) 13.88/8.30 ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X)))) 13.88/8.30 MARK(s(X)) -> ACTIVE(s(mark(X))) 13.88/8.30 ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X)))) 13.88/8.30 MARK(s(X)) -> MARK(X) 13.88/8.30 MARK(terms(X)) -> MARK(X) 13.88/8.30 MARK(recip(X)) -> ACTIVE(recip(mark(X))) 13.88/8.30 ACTIVE(add(0, X)) -> MARK(X) 13.88/8.30 MARK(recip(X)) -> MARK(X) 13.88/8.30 MARK(sqr(X)) -> ACTIVE(sqr(mark(X))) 13.88/8.30 ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) 13.88/8.30 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 13.88/8.30 MARK(sqr(X)) -> MARK(X) 13.88/8.30 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 13.88/8.30 MARK(add(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(add(X1, X2)) -> MARK(X2) 13.88/8.30 MARK(dbl(X)) -> ACTIVE(dbl(mark(X))) 13.88/8.30 MARK(dbl(X)) -> MARK(X) 13.88/8.30 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 13.88/8.30 MARK(first(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(first(X1, X2)) -> MARK(X2) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (62) QDPQMonotonicMRRProof (EQUIVALENT) 13.88/8.30 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 13.88/8.30 13.88/8.30 Strictly oriented dependency pairs: 13.88/8.30 13.88/8.30 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 13.88/8.30 MARK(s(X)) -> ACTIVE(s(mark(X))) 13.88/8.30 MARK(recip(X)) -> ACTIVE(recip(mark(X))) 13.88/8.30 13.88/8.30 13.88/8.30 Used ordering: Polynomial interpretation [POLO]: 13.88/8.30 13.88/8.30 POL(0) = 0 13.88/8.30 POL(ACTIVE(x_1)) = x_1 13.88/8.30 POL(MARK(x_1)) = 1 13.88/8.30 POL(active(x_1)) = 2*x_1 13.88/8.30 POL(add(x_1, x_2)) = 1 13.88/8.30 POL(cons(x_1, x_2)) = 0 13.88/8.30 POL(dbl(x_1)) = 1 13.88/8.30 POL(first(x_1, x_2)) = 1 13.88/8.30 POL(mark(x_1)) = 2 13.88/8.30 POL(nil) = 0 13.88/8.30 POL(recip(x_1)) = 0 13.88/8.30 POL(s(x_1)) = 0 13.88/8.30 POL(sqr(x_1)) = 1 13.88/8.30 POL(terms(x_1)) = 1 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (63) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 MARK(cons(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(terms(X)) -> ACTIVE(terms(mark(X))) 13.88/8.30 ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X)))) 13.88/8.30 ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X)))) 13.88/8.30 MARK(s(X)) -> MARK(X) 13.88/8.30 MARK(terms(X)) -> MARK(X) 13.88/8.30 ACTIVE(add(0, X)) -> MARK(X) 13.88/8.30 MARK(recip(X)) -> MARK(X) 13.88/8.30 MARK(sqr(X)) -> ACTIVE(sqr(mark(X))) 13.88/8.30 ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) 13.88/8.30 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 13.88/8.30 MARK(sqr(X)) -> MARK(X) 13.88/8.30 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 13.88/8.30 MARK(add(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(add(X1, X2)) -> MARK(X2) 13.88/8.30 MARK(dbl(X)) -> ACTIVE(dbl(mark(X))) 13.88/8.30 MARK(dbl(X)) -> MARK(X) 13.88/8.30 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 13.88/8.30 MARK(first(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(first(X1, X2)) -> MARK(X2) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (64) QDPOrderProof (EQUIVALENT) 13.88/8.30 We use the reduction pair processor [LPAR04,JAR06]. 13.88/8.30 13.88/8.30 13.88/8.30 The following pairs can be oriented strictly and are deleted. 13.88/8.30 13.88/8.30 ACTIVE(terms(N)) -> MARK(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 MARK(terms(X)) -> ACTIVE(terms(mark(X))) 13.88/8.30 ACTIVE(sqr(s(X))) -> MARK(s(add(sqr(X), dbl(X)))) 13.88/8.30 ACTIVE(dbl(s(X))) -> MARK(s(s(dbl(X)))) 13.88/8.30 MARK(s(X)) -> MARK(X) 13.88/8.30 MARK(terms(X)) -> MARK(X) 13.88/8.30 ACTIVE(add(0, X)) -> MARK(X) 13.88/8.30 MARK(recip(X)) -> MARK(X) 13.88/8.30 MARK(sqr(X)) -> ACTIVE(sqr(mark(X))) 13.88/8.30 ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) 13.88/8.30 ACTIVE(first(s(X), cons(Y, Z))) -> MARK(cons(Y, first(X, Z))) 13.88/8.30 MARK(sqr(X)) -> MARK(X) 13.88/8.30 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 13.88/8.30 MARK(add(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(add(X1, X2)) -> MARK(X2) 13.88/8.30 MARK(dbl(X)) -> ACTIVE(dbl(mark(X))) 13.88/8.30 MARK(dbl(X)) -> MARK(X) 13.88/8.30 MARK(first(X1, X2)) -> ACTIVE(first(mark(X1), mark(X2))) 13.88/8.30 MARK(first(X1, X2)) -> MARK(X1) 13.88/8.30 MARK(first(X1, X2)) -> MARK(X2) 13.88/8.30 The remaining pairs can at least be oriented weakly. 13.88/8.30 Used ordering: Combined order from the following AFS and order. 13.88/8.30 ACTIVE(x1) = x1 13.88/8.30 13.88/8.30 terms(x1) = terms(x1) 13.88/8.30 13.88/8.30 MARK(x1) = MARK(x1) 13.88/8.30 13.88/8.30 cons(x1, x2) = x1 13.88/8.30 13.88/8.30 recip(x1) = recip(x1) 13.88/8.30 13.88/8.30 sqr(x1) = sqr(x1) 13.88/8.30 13.88/8.30 s(x1) = s(x1) 13.88/8.30 13.88/8.30 mark(x1) = x1 13.88/8.30 13.88/8.30 add(x1, x2) = add(x1, x2) 13.88/8.30 13.88/8.30 dbl(x1) = dbl(x1) 13.88/8.30 13.88/8.30 0 = 0 13.88/8.30 13.88/8.30 first(x1, x2) = first(x1, x2) 13.88/8.30 13.88/8.30 active(x1) = x1 13.88/8.30 13.88/8.30 nil = nil 13.88/8.30 13.88/8.30 13.88/8.30 Recursive path order with status [RPO]. 13.88/8.30 Quasi-Precedence: terms_1 > sqr_1 > add_2 > s_1 > [MARK_1, recip_1, 0] > nil 13.88/8.30 terms_1 > sqr_1 > dbl_1 > s_1 > [MARK_1, recip_1, 0] > nil 13.88/8.30 first_2 > [MARK_1, recip_1, 0] > nil 13.88/8.30 13.88/8.30 Status: terms_1: [1] 13.88/8.30 MARK_1: multiset status 13.88/8.30 recip_1: multiset status 13.88/8.30 sqr_1: [1] 13.88/8.30 s_1: [1] 13.88/8.30 add_2: multiset status 13.88/8.30 dbl_1: [1] 13.88/8.30 0: multiset status 13.88/8.30 first_2: [1,2] 13.88/8.30 nil: multiset status 13.88/8.30 13.88/8.30 13.88/8.30 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 13.88/8.30 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (65) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 MARK(cons(X1, X2)) -> MARK(X1) 13.88/8.30 13.88/8.30 The TRS R consists of the following rules: 13.88/8.30 13.88/8.30 active(terms(N)) -> mark(cons(recip(sqr(N)), terms(s(N)))) 13.88/8.30 active(sqr(0)) -> mark(0) 13.88/8.30 active(sqr(s(X))) -> mark(s(add(sqr(X), dbl(X)))) 13.88/8.30 active(dbl(0)) -> mark(0) 13.88/8.30 active(dbl(s(X))) -> mark(s(s(dbl(X)))) 13.88/8.30 active(add(0, X)) -> mark(X) 13.88/8.30 active(add(s(X), Y)) -> mark(s(add(X, Y))) 13.88/8.30 active(first(0, X)) -> mark(nil) 13.88/8.30 active(first(s(X), cons(Y, Z))) -> mark(cons(Y, first(X, Z))) 13.88/8.30 mark(terms(X)) -> active(terms(mark(X))) 13.88/8.30 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 13.88/8.30 mark(recip(X)) -> active(recip(mark(X))) 13.88/8.30 mark(sqr(X)) -> active(sqr(mark(X))) 13.88/8.30 mark(s(X)) -> active(s(mark(X))) 13.88/8.30 mark(0) -> active(0) 13.88/8.30 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 13.88/8.30 mark(dbl(X)) -> active(dbl(mark(X))) 13.88/8.30 mark(first(X1, X2)) -> active(first(mark(X1), mark(X2))) 13.88/8.30 mark(nil) -> active(nil) 13.88/8.30 terms(mark(X)) -> terms(X) 13.88/8.30 terms(active(X)) -> terms(X) 13.88/8.30 cons(mark(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, mark(X2)) -> cons(X1, X2) 13.88/8.30 cons(active(X1), X2) -> cons(X1, X2) 13.88/8.30 cons(X1, active(X2)) -> cons(X1, X2) 13.88/8.30 recip(mark(X)) -> recip(X) 13.88/8.30 recip(active(X)) -> recip(X) 13.88/8.30 sqr(mark(X)) -> sqr(X) 13.88/8.30 sqr(active(X)) -> sqr(X) 13.88/8.30 s(mark(X)) -> s(X) 13.88/8.30 s(active(X)) -> s(X) 13.88/8.30 add(mark(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, mark(X2)) -> add(X1, X2) 13.88/8.30 add(active(X1), X2) -> add(X1, X2) 13.88/8.30 add(X1, active(X2)) -> add(X1, X2) 13.88/8.30 dbl(mark(X)) -> dbl(X) 13.88/8.30 dbl(active(X)) -> dbl(X) 13.88/8.30 first(mark(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, mark(X2)) -> first(X1, X2) 13.88/8.30 first(active(X1), X2) -> first(X1, X2) 13.88/8.30 first(X1, active(X2)) -> first(X1, X2) 13.88/8.30 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (66) UsableRulesProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (67) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 MARK(cons(X1, X2)) -> MARK(X1) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (68) QReductionProof (EQUIVALENT) 13.88/8.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 13.88/8.30 13.88/8.30 active(terms(x0)) 13.88/8.30 active(sqr(0)) 13.88/8.30 active(sqr(s(x0))) 13.88/8.30 active(dbl(0)) 13.88/8.30 active(dbl(s(x0))) 13.88/8.30 active(add(0, x0)) 13.88/8.30 active(add(s(x0), x1)) 13.88/8.30 active(first(0, x0)) 13.88/8.30 active(first(s(x0), cons(x1, x2))) 13.88/8.30 mark(terms(x0)) 13.88/8.30 mark(cons(x0, x1)) 13.88/8.30 mark(recip(x0)) 13.88/8.30 mark(sqr(x0)) 13.88/8.30 mark(s(x0)) 13.88/8.30 mark(0) 13.88/8.30 mark(add(x0, x1)) 13.88/8.30 mark(dbl(x0)) 13.88/8.30 mark(first(x0, x1)) 13.88/8.30 mark(nil) 13.88/8.30 terms(mark(x0)) 13.88/8.30 terms(active(x0)) 13.88/8.30 recip(mark(x0)) 13.88/8.30 recip(active(x0)) 13.88/8.30 sqr(mark(x0)) 13.88/8.30 sqr(active(x0)) 13.88/8.30 s(mark(x0)) 13.88/8.30 s(active(x0)) 13.88/8.30 add(mark(x0), x1) 13.88/8.30 add(x0, mark(x1)) 13.88/8.30 add(active(x0), x1) 13.88/8.30 add(x0, active(x1)) 13.88/8.30 dbl(mark(x0)) 13.88/8.30 dbl(active(x0)) 13.88/8.30 first(mark(x0), x1) 13.88/8.30 first(x0, mark(x1)) 13.88/8.30 first(active(x0), x1) 13.88/8.30 first(x0, active(x1)) 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (69) 13.88/8.30 Obligation: 13.88/8.30 Q DP problem: 13.88/8.30 The TRS P consists of the following rules: 13.88/8.30 13.88/8.30 MARK(cons(X1, X2)) -> MARK(X1) 13.88/8.30 13.88/8.30 R is empty. 13.88/8.30 The set Q consists of the following terms: 13.88/8.30 13.88/8.30 cons(mark(x0), x1) 13.88/8.30 cons(x0, mark(x1)) 13.88/8.30 cons(active(x0), x1) 13.88/8.30 cons(x0, active(x1)) 13.88/8.30 13.88/8.30 We have to consider all minimal (P,Q,R)-chains. 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (70) QDPSizeChangeProof (EQUIVALENT) 13.88/8.30 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. 13.88/8.30 13.88/8.30 From the DPs we obtained the following set of size-change graphs: 13.88/8.30 *MARK(cons(X1, X2)) -> MARK(X1) 13.88/8.30 The graph contains the following edges 1 > 1 13.88/8.30 13.88/8.30 13.88/8.30 ---------------------------------------- 13.88/8.30 13.88/8.30 (71) 13.88/8.30 YES 13.91/8.34 EOF