8.31/3.02 YES 8.31/3.03 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.31/3.03 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.31/3.03 8.31/3.03 8.31/3.03 Termination w.r.t. Q of the given QTRS could be proven: 8.31/3.03 8.31/3.03 (0) QTRS 8.31/3.03 (1) DependencyPairsProof [EQUIVALENT, 64 ms] 8.31/3.03 (2) QDP 8.31/3.03 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 8.31/3.03 (4) AND 8.31/3.03 (5) QDP 8.31/3.03 (6) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (7) QDP 8.31/3.03 (8) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (9) QDP 8.31/3.03 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (11) YES 8.31/3.03 (12) QDP 8.31/3.03 (13) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (14) QDP 8.31/3.03 (15) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (16) QDP 8.31/3.03 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (18) YES 8.31/3.03 (19) QDP 8.31/3.03 (20) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (21) QDP 8.31/3.03 (22) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (23) QDP 8.31/3.03 (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (25) YES 8.31/3.03 (26) QDP 8.31/3.03 (27) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (28) QDP 8.31/3.03 (29) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (30) QDP 8.31/3.03 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (32) YES 8.31/3.03 (33) QDP 8.31/3.03 (34) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (35) QDP 8.31/3.03 (36) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (37) QDP 8.31/3.03 (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (39) YES 8.31/3.03 (40) QDP 8.31/3.03 (41) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (42) QDP 8.31/3.03 (43) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (44) QDP 8.31/3.03 (45) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (46) YES 8.31/3.03 (47) QDP 8.31/3.03 (48) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (49) QDP 8.31/3.03 (50) QDPOrderProof [EQUIVALENT, 35 ms] 8.31/3.03 (51) QDP 8.31/3.03 (52) QDPOrderProof [EQUIVALENT, 29 ms] 8.31/3.03 (53) QDP 8.31/3.03 (54) QDPOrderProof [EQUIVALENT, 0 ms] 8.31/3.03 (55) QDP 8.31/3.03 (56) DependencyGraphProof [EQUIVALENT, 0 ms] 8.31/3.03 (57) QDP 8.31/3.03 (58) UsableRulesProof [EQUIVALENT, 0 ms] 8.31/3.03 (59) QDP 8.31/3.03 (60) QReductionProof [EQUIVALENT, 0 ms] 8.31/3.03 (61) QDP 8.31/3.03 (62) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.31/3.03 (63) YES 8.31/3.03 8.31/3.03 8.31/3.03 ---------------------------------------- 8.31/3.03 8.31/3.03 (0) 8.31/3.03 Obligation: 8.31/3.03 Q restricted rewrite system: 8.31/3.03 The TRS R consists of the following rules: 8.31/3.03 8.31/3.03 active(fst(0, Z)) -> mark(nil) 8.31/3.03 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.03 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.03 active(add(0, X)) -> mark(X) 8.31/3.03 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.03 active(len(nil)) -> mark(0) 8.31/3.03 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.03 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.03 mark(0) -> active(0) 8.31/3.03 mark(nil) -> active(nil) 8.31/3.03 mark(s(X)) -> active(s(X)) 8.31/3.03 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.03 mark(from(X)) -> active(from(mark(X))) 8.31/3.03 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.03 mark(len(X)) -> active(len(mark(X))) 8.31/3.03 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.03 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.03 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.03 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.03 s(mark(X)) -> s(X) 8.31/3.03 s(active(X)) -> s(X) 8.31/3.03 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.03 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.03 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.03 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.03 from(mark(X)) -> from(X) 8.31/3.03 from(active(X)) -> from(X) 8.31/3.03 add(mark(X1), X2) -> add(X1, X2) 8.31/3.03 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.03 add(active(X1), X2) -> add(X1, X2) 8.31/3.03 add(X1, active(X2)) -> add(X1, X2) 8.31/3.03 len(mark(X)) -> len(X) 8.31/3.03 len(active(X)) -> len(X) 8.31/3.03 8.31/3.03 The set Q consists of the following terms: 8.31/3.03 8.31/3.03 active(fst(0, x0)) 8.31/3.03 active(fst(s(x0), cons(x1, x2))) 8.31/3.03 active(from(x0)) 8.31/3.03 active(add(0, x0)) 8.31/3.03 active(add(s(x0), x1)) 8.31/3.03 active(len(nil)) 8.31/3.03 active(len(cons(x0, x1))) 8.31/3.03 mark(fst(x0, x1)) 8.31/3.03 mark(0) 8.31/3.03 mark(nil) 8.31/3.03 mark(s(x0)) 8.31/3.03 mark(cons(x0, x1)) 8.31/3.03 mark(from(x0)) 8.31/3.03 mark(add(x0, x1)) 8.31/3.03 mark(len(x0)) 8.31/3.03 fst(mark(x0), x1) 8.31/3.03 fst(x0, mark(x1)) 8.31/3.03 fst(active(x0), x1) 8.31/3.03 fst(x0, active(x1)) 8.31/3.03 s(mark(x0)) 8.31/3.03 s(active(x0)) 8.31/3.03 cons(mark(x0), x1) 8.31/3.03 cons(x0, mark(x1)) 8.31/3.03 cons(active(x0), x1) 8.31/3.03 cons(x0, active(x1)) 8.31/3.03 from(mark(x0)) 8.31/3.03 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (1) DependencyPairsProof (EQUIVALENT) 8.31/3.04 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (2) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 ACTIVE(fst(0, Z)) -> MARK(nil) 8.31/3.04 ACTIVE(fst(s(X), cons(Y, Z))) -> MARK(cons(Y, fst(X, Z))) 8.31/3.04 ACTIVE(fst(s(X), cons(Y, Z))) -> CONS(Y, fst(X, Z)) 8.31/3.04 ACTIVE(fst(s(X), cons(Y, Z))) -> FST(X, Z) 8.31/3.04 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.31/3.04 ACTIVE(from(X)) -> CONS(X, from(s(X))) 8.31/3.04 ACTIVE(from(X)) -> FROM(s(X)) 8.31/3.04 ACTIVE(from(X)) -> S(X) 8.31/3.04 ACTIVE(add(0, X)) -> MARK(X) 8.31/3.04 ACTIVE(add(s(X), Y)) -> MARK(s(add(X, Y))) 8.31/3.04 ACTIVE(add(s(X), Y)) -> S(add(X, Y)) 8.31/3.04 ACTIVE(add(s(X), Y)) -> ADD(X, Y) 8.31/3.04 ACTIVE(len(nil)) -> MARK(0) 8.31/3.04 ACTIVE(len(cons(X, Z))) -> MARK(s(len(Z))) 8.31/3.04 ACTIVE(len(cons(X, Z))) -> S(len(Z)) 8.31/3.04 ACTIVE(len(cons(X, Z))) -> LEN(Z) 8.31/3.04 MARK(fst(X1, X2)) -> ACTIVE(fst(mark(X1), mark(X2))) 8.31/3.04 MARK(fst(X1, X2)) -> FST(mark(X1), mark(X2)) 8.31/3.04 MARK(fst(X1, X2)) -> MARK(X1) 8.31/3.04 MARK(fst(X1, X2)) -> MARK(X2) 8.31/3.04 MARK(0) -> ACTIVE(0) 8.31/3.04 MARK(nil) -> ACTIVE(nil) 8.31/3.04 MARK(s(X)) -> ACTIVE(s(X)) 8.31/3.04 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 8.31/3.04 MARK(cons(X1, X2)) -> CONS(mark(X1), X2) 8.31/3.04 MARK(cons(X1, X2)) -> MARK(X1) 8.31/3.04 MARK(from(X)) -> ACTIVE(from(mark(X))) 8.31/3.04 MARK(from(X)) -> FROM(mark(X)) 8.31/3.04 MARK(from(X)) -> MARK(X) 8.31/3.04 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 8.31/3.04 MARK(add(X1, X2)) -> ADD(mark(X1), mark(X2)) 8.31/3.04 MARK(add(X1, X2)) -> MARK(X1) 8.31/3.04 MARK(add(X1, X2)) -> MARK(X2) 8.31/3.04 MARK(len(X)) -> ACTIVE(len(mark(X))) 8.31/3.04 MARK(len(X)) -> LEN(mark(X)) 8.31/3.04 MARK(len(X)) -> MARK(X) 8.31/3.04 FST(mark(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(X1, mark(X2)) -> FST(X1, X2) 8.31/3.04 FST(active(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(X1, active(X2)) -> FST(X1, X2) 8.31/3.04 S(mark(X)) -> S(X) 8.31/3.04 S(active(X)) -> S(X) 8.31/3.04 CONS(mark(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.31/3.04 CONS(active(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(X1, active(X2)) -> CONS(X1, X2) 8.31/3.04 FROM(mark(X)) -> FROM(X) 8.31/3.04 FROM(active(X)) -> FROM(X) 8.31/3.04 ADD(mark(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.31/3.04 ADD(active(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(X1, active(X2)) -> ADD(X1, X2) 8.31/3.04 LEN(mark(X)) -> LEN(X) 8.31/3.04 LEN(active(X)) -> LEN(X) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (3) DependencyGraphProof (EQUIVALENT) 8.31/3.04 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 7 SCCs with 21 less nodes. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (4) 8.31/3.04 Complex Obligation (AND) 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (5) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 LEN(active(X)) -> LEN(X) 8.31/3.04 LEN(mark(X)) -> LEN(X) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (6) UsableRulesProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (7) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 LEN(active(X)) -> LEN(X) 8.31/3.04 LEN(mark(X)) -> LEN(X) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (8) QReductionProof (EQUIVALENT) 8.31/3.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.31/3.04 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (9) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 LEN(active(X)) -> LEN(X) 8.31/3.04 LEN(mark(X)) -> LEN(X) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (10) QDPSizeChangeProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 8.31/3.04 From the DPs we obtained the following set of size-change graphs: 8.31/3.04 *LEN(active(X)) -> LEN(X) 8.31/3.04 The graph contains the following edges 1 > 1 8.31/3.04 8.31/3.04 8.31/3.04 *LEN(mark(X)) -> LEN(X) 8.31/3.04 The graph contains the following edges 1 > 1 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (11) 8.31/3.04 YES 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (12) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.31/3.04 ADD(mark(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(active(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(X1, active(X2)) -> ADD(X1, X2) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (13) UsableRulesProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (14) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.31/3.04 ADD(mark(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(active(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(X1, active(X2)) -> ADD(X1, X2) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (15) QReductionProof (EQUIVALENT) 8.31/3.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.31/3.04 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (16) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 ADD(X1, mark(X2)) -> ADD(X1, X2) 8.31/3.04 ADD(mark(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(active(X1), X2) -> ADD(X1, X2) 8.31/3.04 ADD(X1, active(X2)) -> ADD(X1, X2) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (17) QDPSizeChangeProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 8.31/3.04 From the DPs we obtained the following set of size-change graphs: 8.31/3.04 *ADD(X1, mark(X2)) -> ADD(X1, X2) 8.31/3.04 The graph contains the following edges 1 >= 1, 2 > 2 8.31/3.04 8.31/3.04 8.31/3.04 *ADD(mark(X1), X2) -> ADD(X1, X2) 8.31/3.04 The graph contains the following edges 1 > 1, 2 >= 2 8.31/3.04 8.31/3.04 8.31/3.04 *ADD(active(X1), X2) -> ADD(X1, X2) 8.31/3.04 The graph contains the following edges 1 > 1, 2 >= 2 8.31/3.04 8.31/3.04 8.31/3.04 *ADD(X1, active(X2)) -> ADD(X1, X2) 8.31/3.04 The graph contains the following edges 1 >= 1, 2 > 2 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (18) 8.31/3.04 YES 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (19) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 FROM(active(X)) -> FROM(X) 8.31/3.04 FROM(mark(X)) -> FROM(X) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (20) UsableRulesProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (21) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 FROM(active(X)) -> FROM(X) 8.31/3.04 FROM(mark(X)) -> FROM(X) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (22) QReductionProof (EQUIVALENT) 8.31/3.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.31/3.04 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (23) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 FROM(active(X)) -> FROM(X) 8.31/3.04 FROM(mark(X)) -> FROM(X) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (24) QDPSizeChangeProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 8.31/3.04 From the DPs we obtained the following set of size-change graphs: 8.31/3.04 *FROM(active(X)) -> FROM(X) 8.31/3.04 The graph contains the following edges 1 > 1 8.31/3.04 8.31/3.04 8.31/3.04 *FROM(mark(X)) -> FROM(X) 8.31/3.04 The graph contains the following edges 1 > 1 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (25) 8.31/3.04 YES 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (26) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.31/3.04 CONS(mark(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(active(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(X1, active(X2)) -> CONS(X1, X2) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (27) UsableRulesProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (28) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.31/3.04 CONS(mark(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(active(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(X1, active(X2)) -> CONS(X1, X2) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (29) QReductionProof (EQUIVALENT) 8.31/3.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.31/3.04 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (30) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 CONS(X1, mark(X2)) -> CONS(X1, X2) 8.31/3.04 CONS(mark(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(active(X1), X2) -> CONS(X1, X2) 8.31/3.04 CONS(X1, active(X2)) -> CONS(X1, X2) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (31) QDPSizeChangeProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 8.31/3.04 From the DPs we obtained the following set of size-change graphs: 8.31/3.04 *CONS(X1, mark(X2)) -> CONS(X1, X2) 8.31/3.04 The graph contains the following edges 1 >= 1, 2 > 2 8.31/3.04 8.31/3.04 8.31/3.04 *CONS(mark(X1), X2) -> CONS(X1, X2) 8.31/3.04 The graph contains the following edges 1 > 1, 2 >= 2 8.31/3.04 8.31/3.04 8.31/3.04 *CONS(active(X1), X2) -> CONS(X1, X2) 8.31/3.04 The graph contains the following edges 1 > 1, 2 >= 2 8.31/3.04 8.31/3.04 8.31/3.04 *CONS(X1, active(X2)) -> CONS(X1, X2) 8.31/3.04 The graph contains the following edges 1 >= 1, 2 > 2 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (32) 8.31/3.04 YES 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (33) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 S(active(X)) -> S(X) 8.31/3.04 S(mark(X)) -> S(X) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (34) UsableRulesProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (35) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 S(active(X)) -> S(X) 8.31/3.04 S(mark(X)) -> S(X) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (36) QReductionProof (EQUIVALENT) 8.31/3.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.31/3.04 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (37) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 S(active(X)) -> S(X) 8.31/3.04 S(mark(X)) -> S(X) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (38) QDPSizeChangeProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 8.31/3.04 From the DPs we obtained the following set of size-change graphs: 8.31/3.04 *S(active(X)) -> S(X) 8.31/3.04 The graph contains the following edges 1 > 1 8.31/3.04 8.31/3.04 8.31/3.04 *S(mark(X)) -> S(X) 8.31/3.04 The graph contains the following edges 1 > 1 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (39) 8.31/3.04 YES 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (40) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 FST(X1, mark(X2)) -> FST(X1, X2) 8.31/3.04 FST(mark(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(active(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(X1, active(X2)) -> FST(X1, X2) 8.31/3.04 8.31/3.04 The TRS R consists of the following rules: 8.31/3.04 8.31/3.04 active(fst(0, Z)) -> mark(nil) 8.31/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.31/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.31/3.04 active(add(0, X)) -> mark(X) 8.31/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.31/3.04 active(len(nil)) -> mark(0) 8.31/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.31/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.31/3.04 mark(0) -> active(0) 8.31/3.04 mark(nil) -> active(nil) 8.31/3.04 mark(s(X)) -> active(s(X)) 8.31/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.31/3.04 mark(from(X)) -> active(from(mark(X))) 8.31/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.31/3.04 mark(len(X)) -> active(len(mark(X))) 8.31/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.31/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.31/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.31/3.04 s(mark(X)) -> s(X) 8.31/3.04 s(active(X)) -> s(X) 8.31/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.31/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.31/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.31/3.04 from(mark(X)) -> from(X) 8.31/3.04 from(active(X)) -> from(X) 8.31/3.04 add(mark(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.31/3.04 add(active(X1), X2) -> add(X1, X2) 8.31/3.04 add(X1, active(X2)) -> add(X1, X2) 8.31/3.04 len(mark(X)) -> len(X) 8.31/3.04 len(active(X)) -> len(X) 8.31/3.04 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (41) UsableRulesProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (42) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 FST(X1, mark(X2)) -> FST(X1, X2) 8.31/3.04 FST(mark(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(active(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(X1, active(X2)) -> FST(X1, X2) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (43) QReductionProof (EQUIVALENT) 8.31/3.04 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.31/3.04 8.31/3.04 fst(mark(x0), x1) 8.31/3.04 fst(x0, mark(x1)) 8.31/3.04 fst(active(x0), x1) 8.31/3.04 fst(x0, active(x1)) 8.31/3.04 s(mark(x0)) 8.31/3.04 s(active(x0)) 8.31/3.04 cons(mark(x0), x1) 8.31/3.04 cons(x0, mark(x1)) 8.31/3.04 cons(active(x0), x1) 8.31/3.04 cons(x0, active(x1)) 8.31/3.04 from(mark(x0)) 8.31/3.04 from(active(x0)) 8.31/3.04 add(mark(x0), x1) 8.31/3.04 add(x0, mark(x1)) 8.31/3.04 add(active(x0), x1) 8.31/3.04 add(x0, active(x1)) 8.31/3.04 len(mark(x0)) 8.31/3.04 len(active(x0)) 8.31/3.04 8.31/3.04 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (44) 8.31/3.04 Obligation: 8.31/3.04 Q DP problem: 8.31/3.04 The TRS P consists of the following rules: 8.31/3.04 8.31/3.04 FST(X1, mark(X2)) -> FST(X1, X2) 8.31/3.04 FST(mark(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(active(X1), X2) -> FST(X1, X2) 8.31/3.04 FST(X1, active(X2)) -> FST(X1, X2) 8.31/3.04 8.31/3.04 R is empty. 8.31/3.04 The set Q consists of the following terms: 8.31/3.04 8.31/3.04 active(fst(0, x0)) 8.31/3.04 active(fst(s(x0), cons(x1, x2))) 8.31/3.04 active(from(x0)) 8.31/3.04 active(add(0, x0)) 8.31/3.04 active(add(s(x0), x1)) 8.31/3.04 active(len(nil)) 8.31/3.04 active(len(cons(x0, x1))) 8.31/3.04 mark(fst(x0, x1)) 8.31/3.04 mark(0) 8.31/3.04 mark(nil) 8.31/3.04 mark(s(x0)) 8.31/3.04 mark(cons(x0, x1)) 8.31/3.04 mark(from(x0)) 8.31/3.04 mark(add(x0, x1)) 8.31/3.04 mark(len(x0)) 8.31/3.04 8.31/3.04 We have to consider all minimal (P,Q,R)-chains. 8.31/3.04 ---------------------------------------- 8.31/3.04 8.31/3.04 (45) QDPSizeChangeProof (EQUIVALENT) 8.31/3.04 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. 8.31/3.04 8.31/3.04 From the DPs we obtained the following set of size-change graphs: 8.31/3.04 *FST(X1, mark(X2)) -> FST(X1, X2) 8.31/3.04 The graph contains the following edges 1 >= 1, 2 > 2 8.31/3.04 8.31/3.04 8.31/3.04 *FST(mark(X1), X2) -> FST(X1, X2) 8.31/3.04 The graph contains the following edges 1 > 1, 2 >= 2 8.31/3.04 8.31/3.04 8.31/3.04 *FST(active(X1), X2) -> FST(X1, X2) 8.31/3.04 The graph contains the following edges 1 > 1, 2 >= 2 8.31/3.04 8.31/3.04 8.31/3.04 *FST(X1, active(X2)) -> FST(X1, X2) 8.42/3.04 The graph contains the following edges 1 >= 1, 2 > 2 8.42/3.04 8.42/3.04 8.42/3.04 ---------------------------------------- 8.42/3.04 8.42/3.04 (46) 8.42/3.04 YES 8.42/3.04 8.42/3.04 ---------------------------------------- 8.42/3.04 8.42/3.04 (47) 8.42/3.04 Obligation: 8.42/3.04 Q DP problem: 8.42/3.04 The TRS P consists of the following rules: 8.42/3.04 8.42/3.04 ACTIVE(fst(s(X), cons(Y, Z))) -> MARK(cons(Y, fst(X, Z))) 8.42/3.04 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 8.42/3.04 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.42/3.04 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(fst(X1, X2)) -> ACTIVE(fst(mark(X1), mark(X2))) 8.42/3.04 ACTIVE(add(0, X)) -> MARK(X) 8.42/3.04 MARK(fst(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(fst(X1, X2)) -> MARK(X2) 8.42/3.04 MARK(from(X)) -> ACTIVE(from(mark(X))) 8.42/3.04 MARK(from(X)) -> MARK(X) 8.42/3.04 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 8.42/3.04 MARK(add(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(add(X1, X2)) -> MARK(X2) 8.42/3.04 MARK(len(X)) -> ACTIVE(len(mark(X))) 8.42/3.04 MARK(len(X)) -> MARK(X) 8.42/3.04 8.42/3.04 The TRS R consists of the following rules: 8.42/3.04 8.42/3.04 active(fst(0, Z)) -> mark(nil) 8.42/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.04 active(add(0, X)) -> mark(X) 8.42/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.04 active(len(nil)) -> mark(0) 8.42/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.04 mark(0) -> active(0) 8.42/3.04 mark(nil) -> active(nil) 8.42/3.04 mark(s(X)) -> active(s(X)) 8.42/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.04 mark(from(X)) -> active(from(mark(X))) 8.42/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.04 mark(len(X)) -> active(len(mark(X))) 8.42/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.04 s(mark(X)) -> s(X) 8.42/3.04 s(active(X)) -> s(X) 8.42/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.04 from(mark(X)) -> from(X) 8.42/3.04 from(active(X)) -> from(X) 8.42/3.04 add(mark(X1), X2) -> add(X1, X2) 8.42/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.04 add(active(X1), X2) -> add(X1, X2) 8.42/3.04 add(X1, active(X2)) -> add(X1, X2) 8.42/3.04 len(mark(X)) -> len(X) 8.42/3.04 len(active(X)) -> len(X) 8.42/3.04 8.42/3.04 The set Q consists of the following terms: 8.42/3.04 8.42/3.04 active(fst(0, x0)) 8.42/3.04 active(fst(s(x0), cons(x1, x2))) 8.42/3.04 active(from(x0)) 8.42/3.04 active(add(0, x0)) 8.42/3.04 active(add(s(x0), x1)) 8.42/3.04 active(len(nil)) 8.42/3.04 active(len(cons(x0, x1))) 8.42/3.04 mark(fst(x0, x1)) 8.42/3.04 mark(0) 8.42/3.04 mark(nil) 8.42/3.04 mark(s(x0)) 8.42/3.04 mark(cons(x0, x1)) 8.42/3.04 mark(from(x0)) 8.42/3.04 mark(add(x0, x1)) 8.42/3.04 mark(len(x0)) 8.42/3.04 fst(mark(x0), x1) 8.42/3.04 fst(x0, mark(x1)) 8.42/3.04 fst(active(x0), x1) 8.42/3.04 fst(x0, active(x1)) 8.42/3.04 s(mark(x0)) 8.42/3.04 s(active(x0)) 8.42/3.04 cons(mark(x0), x1) 8.42/3.04 cons(x0, mark(x1)) 8.42/3.04 cons(active(x0), x1) 8.42/3.04 cons(x0, active(x1)) 8.42/3.04 from(mark(x0)) 8.42/3.04 from(active(x0)) 8.42/3.04 add(mark(x0), x1) 8.42/3.04 add(x0, mark(x1)) 8.42/3.04 add(active(x0), x1) 8.42/3.04 add(x0, active(x1)) 8.42/3.04 len(mark(x0)) 8.42/3.04 len(active(x0)) 8.42/3.04 8.42/3.04 We have to consider all minimal (P,Q,R)-chains. 8.42/3.04 ---------------------------------------- 8.42/3.04 8.42/3.04 (48) UsableRulesProof (EQUIVALENT) 8.42/3.04 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. 8.42/3.04 ---------------------------------------- 8.42/3.04 8.42/3.04 (49) 8.42/3.04 Obligation: 8.42/3.04 Q DP problem: 8.42/3.04 The TRS P consists of the following rules: 8.42/3.04 8.42/3.04 ACTIVE(fst(s(X), cons(Y, Z))) -> MARK(cons(Y, fst(X, Z))) 8.42/3.04 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 8.42/3.04 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.42/3.04 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(fst(X1, X2)) -> ACTIVE(fst(mark(X1), mark(X2))) 8.42/3.04 ACTIVE(add(0, X)) -> MARK(X) 8.42/3.04 MARK(fst(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(fst(X1, X2)) -> MARK(X2) 8.42/3.04 MARK(from(X)) -> ACTIVE(from(mark(X))) 8.42/3.04 MARK(from(X)) -> MARK(X) 8.42/3.04 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 8.42/3.04 MARK(add(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(add(X1, X2)) -> MARK(X2) 8.42/3.04 MARK(len(X)) -> ACTIVE(len(mark(X))) 8.42/3.04 MARK(len(X)) -> MARK(X) 8.42/3.04 8.42/3.04 The TRS R consists of the following rules: 8.42/3.04 8.42/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.04 active(add(0, X)) -> mark(X) 8.42/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.04 mark(from(X)) -> active(from(mark(X))) 8.42/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.04 mark(len(X)) -> active(len(mark(X))) 8.42/3.04 mark(0) -> active(0) 8.42/3.04 mark(nil) -> active(nil) 8.42/3.04 mark(s(X)) -> active(s(X)) 8.42/3.04 len(active(X)) -> len(X) 8.42/3.04 len(mark(X)) -> len(X) 8.42/3.04 active(fst(0, Z)) -> mark(nil) 8.42/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.04 active(len(nil)) -> mark(0) 8.42/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.04 from(active(X)) -> from(X) 8.42/3.04 from(mark(X)) -> from(X) 8.42/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.04 add(mark(X1), X2) -> add(X1, X2) 8.42/3.04 add(active(X1), X2) -> add(X1, X2) 8.42/3.04 add(X1, active(X2)) -> add(X1, X2) 8.42/3.04 8.42/3.04 The set Q consists of the following terms: 8.42/3.04 8.42/3.04 active(fst(0, x0)) 8.42/3.04 active(fst(s(x0), cons(x1, x2))) 8.42/3.04 active(from(x0)) 8.42/3.04 active(add(0, x0)) 8.42/3.04 active(add(s(x0), x1)) 8.42/3.04 active(len(nil)) 8.42/3.04 active(len(cons(x0, x1))) 8.42/3.04 mark(fst(x0, x1)) 8.42/3.04 mark(0) 8.42/3.04 mark(nil) 8.42/3.04 mark(s(x0)) 8.42/3.04 mark(cons(x0, x1)) 8.42/3.04 mark(from(x0)) 8.42/3.04 mark(add(x0, x1)) 8.42/3.04 mark(len(x0)) 8.42/3.04 fst(mark(x0), x1) 8.42/3.04 fst(x0, mark(x1)) 8.42/3.04 fst(active(x0), x1) 8.42/3.04 fst(x0, active(x1)) 8.42/3.04 s(mark(x0)) 8.42/3.04 s(active(x0)) 8.42/3.04 cons(mark(x0), x1) 8.42/3.04 cons(x0, mark(x1)) 8.42/3.04 cons(active(x0), x1) 8.42/3.04 cons(x0, active(x1)) 8.42/3.04 from(mark(x0)) 8.42/3.04 from(active(x0)) 8.42/3.04 add(mark(x0), x1) 8.42/3.04 add(x0, mark(x1)) 8.42/3.04 add(active(x0), x1) 8.42/3.04 add(x0, active(x1)) 8.42/3.04 len(mark(x0)) 8.42/3.04 len(active(x0)) 8.42/3.04 8.42/3.04 We have to consider all minimal (P,Q,R)-chains. 8.42/3.04 ---------------------------------------- 8.42/3.04 8.42/3.04 (50) QDPOrderProof (EQUIVALENT) 8.42/3.04 We use the reduction pair processor [LPAR04,JAR06]. 8.42/3.04 8.42/3.04 8.42/3.04 The following pairs can be oriented strictly and are deleted. 8.42/3.04 8.42/3.04 ACTIVE(fst(s(X), cons(Y, Z))) -> MARK(cons(Y, fst(X, Z))) 8.42/3.04 ACTIVE(add(0, X)) -> MARK(X) 8.42/3.04 MARK(fst(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(fst(X1, X2)) -> MARK(X2) 8.42/3.04 MARK(add(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(add(X1, X2)) -> MARK(X2) 8.42/3.04 The remaining pairs can at least be oriented weakly. 8.42/3.04 Used ordering: Combined order from the following AFS and order. 8.42/3.04 ACTIVE(x1) = x1 8.42/3.04 8.42/3.04 fst(x1, x2) = fst(x1, x2) 8.42/3.04 8.42/3.04 s(x1) = s 8.42/3.04 8.42/3.04 cons(x1, x2) = x1 8.42/3.04 8.42/3.04 MARK(x1) = x1 8.42/3.04 8.42/3.04 mark(x1) = x1 8.42/3.04 8.42/3.04 from(x1) = x1 8.42/3.04 8.42/3.04 add(x1, x2) = add(x1, x2) 8.42/3.04 8.42/3.04 0 = 0 8.42/3.04 8.42/3.04 len(x1) = x1 8.42/3.04 8.42/3.04 active(x1) = x1 8.42/3.04 8.42/3.04 nil = nil 8.42/3.04 8.42/3.04 8.42/3.04 Knuth-Bendix order [KBO] with precedence:trivial 8.42/3.04 8.42/3.04 and weight map: 8.42/3.04 8.42/3.04 s=3 8.42/3.04 0=6 8.42/3.04 fst_2=3 8.42/3.04 add_2=1 8.42/3.04 nil=8 8.42/3.04 8.42/3.04 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.42/3.04 8.42/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.04 active(add(0, X)) -> mark(X) 8.42/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.04 mark(from(X)) -> active(from(mark(X))) 8.42/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.04 mark(len(X)) -> active(len(mark(X))) 8.42/3.04 mark(0) -> active(0) 8.42/3.04 mark(nil) -> active(nil) 8.42/3.04 mark(s(X)) -> active(s(X)) 8.42/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.04 from(active(X)) -> from(X) 8.42/3.04 from(mark(X)) -> from(X) 8.42/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.04 add(mark(X1), X2) -> add(X1, X2) 8.42/3.04 add(active(X1), X2) -> add(X1, X2) 8.42/3.04 add(X1, active(X2)) -> add(X1, X2) 8.42/3.04 len(active(X)) -> len(X) 8.42/3.04 len(mark(X)) -> len(X) 8.42/3.04 active(fst(0, Z)) -> mark(nil) 8.42/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.04 active(len(nil)) -> mark(0) 8.42/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.04 8.42/3.04 8.42/3.04 ---------------------------------------- 8.42/3.04 8.42/3.04 (51) 8.42/3.04 Obligation: 8.42/3.04 Q DP problem: 8.42/3.04 The TRS P consists of the following rules: 8.42/3.04 8.42/3.04 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 8.42/3.04 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.42/3.04 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.04 MARK(fst(X1, X2)) -> ACTIVE(fst(mark(X1), mark(X2))) 8.42/3.04 MARK(from(X)) -> ACTIVE(from(mark(X))) 8.42/3.04 MARK(from(X)) -> MARK(X) 8.42/3.04 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 8.42/3.04 MARK(len(X)) -> ACTIVE(len(mark(X))) 8.42/3.04 MARK(len(X)) -> MARK(X) 8.42/3.04 8.42/3.04 The TRS R consists of the following rules: 8.42/3.04 8.42/3.04 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.04 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.04 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.04 active(add(0, X)) -> mark(X) 8.42/3.04 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.04 mark(from(X)) -> active(from(mark(X))) 8.42/3.04 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.04 mark(len(X)) -> active(len(mark(X))) 8.42/3.04 mark(0) -> active(0) 8.42/3.04 mark(nil) -> active(nil) 8.42/3.04 mark(s(X)) -> active(s(X)) 8.42/3.04 len(active(X)) -> len(X) 8.42/3.04 len(mark(X)) -> len(X) 8.42/3.04 active(fst(0, Z)) -> mark(nil) 8.42/3.04 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.04 active(len(nil)) -> mark(0) 8.42/3.04 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.04 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.04 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.04 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.04 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.04 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.04 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.04 from(active(X)) -> from(X) 8.42/3.04 from(mark(X)) -> from(X) 8.42/3.04 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.04 add(mark(X1), X2) -> add(X1, X2) 8.42/3.04 add(active(X1), X2) -> add(X1, X2) 8.42/3.04 add(X1, active(X2)) -> add(X1, X2) 8.42/3.04 8.42/3.04 The set Q consists of the following terms: 8.42/3.04 8.42/3.04 active(fst(0, x0)) 8.42/3.04 active(fst(s(x0), cons(x1, x2))) 8.42/3.04 active(from(x0)) 8.42/3.04 active(add(0, x0)) 8.42/3.04 active(add(s(x0), x1)) 8.42/3.04 active(len(nil)) 8.42/3.04 active(len(cons(x0, x1))) 8.42/3.04 mark(fst(x0, x1)) 8.42/3.04 mark(0) 8.42/3.04 mark(nil) 8.42/3.04 mark(s(x0)) 8.42/3.04 mark(cons(x0, x1)) 8.42/3.04 mark(from(x0)) 8.42/3.04 mark(add(x0, x1)) 8.42/3.04 mark(len(x0)) 8.42/3.04 fst(mark(x0), x1) 8.42/3.04 fst(x0, mark(x1)) 8.42/3.04 fst(active(x0), x1) 8.42/3.04 fst(x0, active(x1)) 8.42/3.05 s(mark(x0)) 8.42/3.05 s(active(x0)) 8.42/3.05 cons(mark(x0), x1) 8.42/3.05 cons(x0, mark(x1)) 8.42/3.05 cons(active(x0), x1) 8.42/3.05 cons(x0, active(x1)) 8.42/3.05 from(mark(x0)) 8.42/3.05 from(active(x0)) 8.42/3.05 add(mark(x0), x1) 8.42/3.05 add(x0, mark(x1)) 8.42/3.05 add(active(x0), x1) 8.42/3.05 add(x0, active(x1)) 8.42/3.05 len(mark(x0)) 8.42/3.05 len(active(x0)) 8.42/3.05 8.42/3.05 We have to consider all minimal (P,Q,R)-chains. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (52) QDPOrderProof (EQUIVALENT) 8.42/3.05 We use the reduction pair processor [LPAR04,JAR06]. 8.42/3.05 8.42/3.05 8.42/3.05 The following pairs can be oriented strictly and are deleted. 8.42/3.05 8.42/3.05 MARK(len(X)) -> MARK(X) 8.42/3.05 The remaining pairs can at least be oriented weakly. 8.42/3.05 Used ordering: Combined order from the following AFS and order. 8.42/3.05 MARK(x1) = x1 8.42/3.05 8.42/3.05 cons(x1, x2) = x1 8.42/3.05 8.42/3.05 ACTIVE(x1) = x1 8.42/3.05 8.42/3.05 mark(x1) = x1 8.42/3.05 8.42/3.05 from(x1) = x1 8.42/3.05 8.42/3.05 fst(x1, x2) = x2 8.42/3.05 8.42/3.05 add(x1, x2) = add(x2) 8.42/3.05 8.42/3.05 len(x1) = len(x1) 8.42/3.05 8.42/3.05 active(x1) = x1 8.42/3.05 8.42/3.05 0 = 0 8.42/3.05 8.42/3.05 nil = nil 8.42/3.05 8.42/3.05 s(x1) = s 8.42/3.05 8.42/3.05 8.42/3.05 Knuth-Bendix order [KBO] with precedence:trivial 8.42/3.05 8.42/3.05 and weight map: 8.42/3.05 8.42/3.05 s=3 8.42/3.05 0=3 8.42/3.05 len_1=4 8.42/3.05 add_1=3 8.42/3.05 nil=1 8.42/3.05 8.42/3.05 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.42/3.05 8.42/3.05 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.05 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.05 active(add(0, X)) -> mark(X) 8.42/3.05 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.05 mark(from(X)) -> active(from(mark(X))) 8.42/3.05 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.05 mark(len(X)) -> active(len(mark(X))) 8.42/3.05 mark(0) -> active(0) 8.42/3.05 mark(nil) -> active(nil) 8.42/3.05 mark(s(X)) -> active(s(X)) 8.42/3.05 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.05 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.05 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.05 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.05 from(active(X)) -> from(X) 8.42/3.05 from(mark(X)) -> from(X) 8.42/3.05 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.05 add(mark(X1), X2) -> add(X1, X2) 8.42/3.05 add(active(X1), X2) -> add(X1, X2) 8.42/3.05 add(X1, active(X2)) -> add(X1, X2) 8.42/3.05 len(active(X)) -> len(X) 8.42/3.05 len(mark(X)) -> len(X) 8.42/3.05 active(fst(0, Z)) -> mark(nil) 8.42/3.05 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.05 active(len(nil)) -> mark(0) 8.42/3.05 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.05 8.42/3.05 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (53) 8.42/3.05 Obligation: 8.42/3.05 Q DP problem: 8.42/3.05 The TRS P consists of the following rules: 8.42/3.05 8.42/3.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 8.42/3.05 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.42/3.05 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.05 MARK(fst(X1, X2)) -> ACTIVE(fst(mark(X1), mark(X2))) 8.42/3.05 MARK(from(X)) -> ACTIVE(from(mark(X))) 8.42/3.05 MARK(from(X)) -> MARK(X) 8.42/3.05 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 8.42/3.05 MARK(len(X)) -> ACTIVE(len(mark(X))) 8.42/3.05 8.42/3.05 The TRS R consists of the following rules: 8.42/3.05 8.42/3.05 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.05 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.05 active(add(0, X)) -> mark(X) 8.42/3.05 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.05 mark(from(X)) -> active(from(mark(X))) 8.42/3.05 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.05 mark(len(X)) -> active(len(mark(X))) 8.42/3.05 mark(0) -> active(0) 8.42/3.05 mark(nil) -> active(nil) 8.42/3.05 mark(s(X)) -> active(s(X)) 8.42/3.05 len(active(X)) -> len(X) 8.42/3.05 len(mark(X)) -> len(X) 8.42/3.05 active(fst(0, Z)) -> mark(nil) 8.42/3.05 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.05 active(len(nil)) -> mark(0) 8.42/3.05 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.05 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.05 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.05 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.05 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.05 from(active(X)) -> from(X) 8.42/3.05 from(mark(X)) -> from(X) 8.42/3.05 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.05 add(mark(X1), X2) -> add(X1, X2) 8.42/3.05 add(active(X1), X2) -> add(X1, X2) 8.42/3.05 add(X1, active(X2)) -> add(X1, X2) 8.42/3.05 8.42/3.05 The set Q consists of the following terms: 8.42/3.05 8.42/3.05 active(fst(0, x0)) 8.42/3.05 active(fst(s(x0), cons(x1, x2))) 8.42/3.05 active(from(x0)) 8.42/3.05 active(add(0, x0)) 8.42/3.05 active(add(s(x0), x1)) 8.42/3.05 active(len(nil)) 8.42/3.05 active(len(cons(x0, x1))) 8.42/3.05 mark(fst(x0, x1)) 8.42/3.05 mark(0) 8.42/3.05 mark(nil) 8.42/3.05 mark(s(x0)) 8.42/3.05 mark(cons(x0, x1)) 8.42/3.05 mark(from(x0)) 8.42/3.05 mark(add(x0, x1)) 8.42/3.05 mark(len(x0)) 8.42/3.05 fst(mark(x0), x1) 8.42/3.05 fst(x0, mark(x1)) 8.42/3.05 fst(active(x0), x1) 8.42/3.05 fst(x0, active(x1)) 8.42/3.05 s(mark(x0)) 8.42/3.05 s(active(x0)) 8.42/3.05 cons(mark(x0), x1) 8.42/3.05 cons(x0, mark(x1)) 8.42/3.05 cons(active(x0), x1) 8.42/3.05 cons(x0, active(x1)) 8.42/3.05 from(mark(x0)) 8.42/3.05 from(active(x0)) 8.42/3.05 add(mark(x0), x1) 8.42/3.05 add(x0, mark(x1)) 8.42/3.05 add(active(x0), x1) 8.42/3.05 add(x0, active(x1)) 8.42/3.05 len(mark(x0)) 8.42/3.05 len(active(x0)) 8.42/3.05 8.42/3.05 We have to consider all minimal (P,Q,R)-chains. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (54) QDPOrderProof (EQUIVALENT) 8.42/3.05 We use the reduction pair processor [LPAR04,JAR06]. 8.42/3.05 8.42/3.05 8.42/3.05 The following pairs can be oriented strictly and are deleted. 8.42/3.05 8.42/3.05 ACTIVE(from(X)) -> MARK(cons(X, from(s(X)))) 8.42/3.05 MARK(from(X)) -> MARK(X) 8.42/3.05 The remaining pairs can at least be oriented weakly. 8.42/3.05 Used ordering: Combined order from the following AFS and order. 8.42/3.05 MARK(x1) = x1 8.42/3.05 8.42/3.05 cons(x1, x2) = x1 8.42/3.05 8.42/3.05 ACTIVE(x1) = x1 8.42/3.05 8.42/3.05 mark(x1) = x1 8.42/3.05 8.42/3.05 from(x1) = from(x1) 8.42/3.05 8.42/3.05 fst(x1, x2) = x2 8.42/3.05 8.42/3.05 add(x1, x2) = add(x2) 8.42/3.05 8.42/3.05 len(x1) = len 8.42/3.05 8.42/3.05 active(x1) = x1 8.42/3.05 8.42/3.05 0 = 0 8.42/3.05 8.42/3.05 nil = nil 8.42/3.05 8.42/3.05 s(x1) = s 8.42/3.05 8.42/3.05 8.42/3.05 Knuth-Bendix order [KBO] with precedence:trivial 8.42/3.05 8.42/3.05 and weight map: 8.42/3.05 8.42/3.05 s=3 8.42/3.05 0=3 8.42/3.05 from_1=1 8.42/3.05 len=5 8.42/3.05 add_1=3 8.42/3.05 nil=1 8.42/3.05 8.42/3.05 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.42/3.05 8.42/3.05 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.05 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.05 active(add(0, X)) -> mark(X) 8.42/3.05 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.05 mark(from(X)) -> active(from(mark(X))) 8.42/3.05 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.05 mark(len(X)) -> active(len(mark(X))) 8.42/3.05 mark(0) -> active(0) 8.42/3.05 mark(nil) -> active(nil) 8.42/3.05 mark(s(X)) -> active(s(X)) 8.42/3.05 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.05 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.05 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.05 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.05 from(active(X)) -> from(X) 8.42/3.05 from(mark(X)) -> from(X) 8.42/3.05 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.05 add(mark(X1), X2) -> add(X1, X2) 8.42/3.05 add(active(X1), X2) -> add(X1, X2) 8.42/3.05 add(X1, active(X2)) -> add(X1, X2) 8.42/3.05 len(active(X)) -> len(X) 8.42/3.05 len(mark(X)) -> len(X) 8.42/3.05 active(fst(0, Z)) -> mark(nil) 8.42/3.05 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.05 active(len(nil)) -> mark(0) 8.42/3.05 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.05 8.42/3.05 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (55) 8.42/3.05 Obligation: 8.42/3.05 Q DP problem: 8.42/3.05 The TRS P consists of the following rules: 8.42/3.05 8.42/3.05 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 8.42/3.05 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.05 MARK(fst(X1, X2)) -> ACTIVE(fst(mark(X1), mark(X2))) 8.42/3.05 MARK(from(X)) -> ACTIVE(from(mark(X))) 8.42/3.05 MARK(add(X1, X2)) -> ACTIVE(add(mark(X1), mark(X2))) 8.42/3.05 MARK(len(X)) -> ACTIVE(len(mark(X))) 8.42/3.05 8.42/3.05 The TRS R consists of the following rules: 8.42/3.05 8.42/3.05 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.05 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.05 active(add(0, X)) -> mark(X) 8.42/3.05 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.05 mark(from(X)) -> active(from(mark(X))) 8.42/3.05 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.05 mark(len(X)) -> active(len(mark(X))) 8.42/3.05 mark(0) -> active(0) 8.42/3.05 mark(nil) -> active(nil) 8.42/3.05 mark(s(X)) -> active(s(X)) 8.42/3.05 len(active(X)) -> len(X) 8.42/3.05 len(mark(X)) -> len(X) 8.42/3.05 active(fst(0, Z)) -> mark(nil) 8.42/3.05 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.05 active(len(nil)) -> mark(0) 8.42/3.05 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.05 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.05 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.05 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.05 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.05 from(active(X)) -> from(X) 8.42/3.05 from(mark(X)) -> from(X) 8.42/3.05 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.05 add(mark(X1), X2) -> add(X1, X2) 8.42/3.05 add(active(X1), X2) -> add(X1, X2) 8.42/3.05 add(X1, active(X2)) -> add(X1, X2) 8.42/3.05 8.42/3.05 The set Q consists of the following terms: 8.42/3.05 8.42/3.05 active(fst(0, x0)) 8.42/3.05 active(fst(s(x0), cons(x1, x2))) 8.42/3.05 active(from(x0)) 8.42/3.05 active(add(0, x0)) 8.42/3.05 active(add(s(x0), x1)) 8.42/3.05 active(len(nil)) 8.42/3.05 active(len(cons(x0, x1))) 8.42/3.05 mark(fst(x0, x1)) 8.42/3.05 mark(0) 8.42/3.05 mark(nil) 8.42/3.05 mark(s(x0)) 8.42/3.05 mark(cons(x0, x1)) 8.42/3.05 mark(from(x0)) 8.42/3.05 mark(add(x0, x1)) 8.42/3.05 mark(len(x0)) 8.42/3.05 fst(mark(x0), x1) 8.42/3.05 fst(x0, mark(x1)) 8.42/3.05 fst(active(x0), x1) 8.42/3.05 fst(x0, active(x1)) 8.42/3.05 s(mark(x0)) 8.42/3.05 s(active(x0)) 8.42/3.05 cons(mark(x0), x1) 8.42/3.05 cons(x0, mark(x1)) 8.42/3.05 cons(active(x0), x1) 8.42/3.05 cons(x0, active(x1)) 8.42/3.05 from(mark(x0)) 8.42/3.05 from(active(x0)) 8.42/3.05 add(mark(x0), x1) 8.42/3.05 add(x0, mark(x1)) 8.42/3.05 add(active(x0), x1) 8.42/3.05 add(x0, active(x1)) 8.42/3.05 len(mark(x0)) 8.42/3.05 len(active(x0)) 8.42/3.05 8.42/3.05 We have to consider all minimal (P,Q,R)-chains. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (56) DependencyGraphProof (EQUIVALENT) 8.42/3.05 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (57) 8.42/3.05 Obligation: 8.42/3.05 Q DP problem: 8.42/3.05 The TRS P consists of the following rules: 8.42/3.05 8.42/3.05 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.05 8.42/3.05 The TRS R consists of the following rules: 8.42/3.05 8.42/3.05 active(fst(s(X), cons(Y, Z))) -> mark(cons(Y, fst(X, Z))) 8.42/3.05 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 8.42/3.05 active(from(X)) -> mark(cons(X, from(s(X)))) 8.42/3.05 active(add(0, X)) -> mark(X) 8.42/3.05 mark(fst(X1, X2)) -> active(fst(mark(X1), mark(X2))) 8.42/3.05 mark(from(X)) -> active(from(mark(X))) 8.42/3.05 mark(add(X1, X2)) -> active(add(mark(X1), mark(X2))) 8.42/3.05 mark(len(X)) -> active(len(mark(X))) 8.42/3.05 mark(0) -> active(0) 8.42/3.05 mark(nil) -> active(nil) 8.42/3.05 mark(s(X)) -> active(s(X)) 8.42/3.05 len(active(X)) -> len(X) 8.42/3.05 len(mark(X)) -> len(X) 8.42/3.05 active(fst(0, Z)) -> mark(nil) 8.42/3.05 active(add(s(X), Y)) -> mark(s(add(X, Y))) 8.42/3.05 active(len(nil)) -> mark(0) 8.42/3.05 active(len(cons(X, Z))) -> mark(s(len(Z))) 8.42/3.05 cons(X1, mark(X2)) -> cons(X1, X2) 8.42/3.05 cons(mark(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(active(X1), X2) -> cons(X1, X2) 8.42/3.05 cons(X1, active(X2)) -> cons(X1, X2) 8.42/3.05 fst(X1, mark(X2)) -> fst(X1, X2) 8.42/3.05 fst(mark(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(active(X1), X2) -> fst(X1, X2) 8.42/3.05 fst(X1, active(X2)) -> fst(X1, X2) 8.42/3.05 from(active(X)) -> from(X) 8.42/3.05 from(mark(X)) -> from(X) 8.42/3.05 add(X1, mark(X2)) -> add(X1, X2) 8.42/3.05 add(mark(X1), X2) -> add(X1, X2) 8.42/3.05 add(active(X1), X2) -> add(X1, X2) 8.42/3.05 add(X1, active(X2)) -> add(X1, X2) 8.42/3.05 8.42/3.05 The set Q consists of the following terms: 8.42/3.05 8.42/3.05 active(fst(0, x0)) 8.42/3.05 active(fst(s(x0), cons(x1, x2))) 8.42/3.05 active(from(x0)) 8.42/3.05 active(add(0, x0)) 8.42/3.05 active(add(s(x0), x1)) 8.42/3.05 active(len(nil)) 8.42/3.05 active(len(cons(x0, x1))) 8.42/3.05 mark(fst(x0, x1)) 8.42/3.05 mark(0) 8.42/3.05 mark(nil) 8.42/3.05 mark(s(x0)) 8.42/3.05 mark(cons(x0, x1)) 8.42/3.05 mark(from(x0)) 8.42/3.05 mark(add(x0, x1)) 8.42/3.05 mark(len(x0)) 8.42/3.05 fst(mark(x0), x1) 8.42/3.05 fst(x0, mark(x1)) 8.42/3.05 fst(active(x0), x1) 8.42/3.05 fst(x0, active(x1)) 8.42/3.05 s(mark(x0)) 8.42/3.05 s(active(x0)) 8.42/3.05 cons(mark(x0), x1) 8.42/3.05 cons(x0, mark(x1)) 8.42/3.05 cons(active(x0), x1) 8.42/3.05 cons(x0, active(x1)) 8.42/3.05 from(mark(x0)) 8.42/3.05 from(active(x0)) 8.42/3.05 add(mark(x0), x1) 8.42/3.05 add(x0, mark(x1)) 8.42/3.05 add(active(x0), x1) 8.42/3.05 add(x0, active(x1)) 8.42/3.05 len(mark(x0)) 8.42/3.05 len(active(x0)) 8.42/3.05 8.42/3.05 We have to consider all minimal (P,Q,R)-chains. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (58) UsableRulesProof (EQUIVALENT) 8.42/3.05 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. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (59) 8.42/3.05 Obligation: 8.42/3.05 Q DP problem: 8.42/3.05 The TRS P consists of the following rules: 8.42/3.05 8.42/3.05 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.05 8.42/3.05 R is empty. 8.42/3.05 The set Q consists of the following terms: 8.42/3.05 8.42/3.05 active(fst(0, x0)) 8.42/3.05 active(fst(s(x0), cons(x1, x2))) 8.42/3.05 active(from(x0)) 8.42/3.05 active(add(0, x0)) 8.42/3.05 active(add(s(x0), x1)) 8.42/3.05 active(len(nil)) 8.42/3.05 active(len(cons(x0, x1))) 8.42/3.05 mark(fst(x0, x1)) 8.42/3.05 mark(0) 8.42/3.05 mark(nil) 8.42/3.05 mark(s(x0)) 8.42/3.05 mark(cons(x0, x1)) 8.42/3.05 mark(from(x0)) 8.42/3.05 mark(add(x0, x1)) 8.42/3.05 mark(len(x0)) 8.42/3.05 fst(mark(x0), x1) 8.42/3.05 fst(x0, mark(x1)) 8.42/3.05 fst(active(x0), x1) 8.42/3.05 fst(x0, active(x1)) 8.42/3.05 s(mark(x0)) 8.42/3.05 s(active(x0)) 8.42/3.05 cons(mark(x0), x1) 8.42/3.05 cons(x0, mark(x1)) 8.42/3.05 cons(active(x0), x1) 8.42/3.05 cons(x0, active(x1)) 8.42/3.05 from(mark(x0)) 8.42/3.05 from(active(x0)) 8.42/3.05 add(mark(x0), x1) 8.42/3.05 add(x0, mark(x1)) 8.42/3.05 add(active(x0), x1) 8.42/3.05 add(x0, active(x1)) 8.42/3.05 len(mark(x0)) 8.42/3.05 len(active(x0)) 8.42/3.05 8.42/3.05 We have to consider all minimal (P,Q,R)-chains. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (60) QReductionProof (EQUIVALENT) 8.42/3.05 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.42/3.05 8.42/3.05 active(fst(0, x0)) 8.42/3.05 active(fst(s(x0), cons(x1, x2))) 8.42/3.05 active(from(x0)) 8.42/3.05 active(add(0, x0)) 8.42/3.05 active(add(s(x0), x1)) 8.42/3.05 active(len(nil)) 8.42/3.05 active(len(cons(x0, x1))) 8.42/3.05 mark(fst(x0, x1)) 8.42/3.05 mark(0) 8.42/3.05 mark(nil) 8.42/3.05 mark(s(x0)) 8.42/3.05 mark(cons(x0, x1)) 8.42/3.05 mark(from(x0)) 8.42/3.05 mark(add(x0, x1)) 8.42/3.05 mark(len(x0)) 8.42/3.05 fst(mark(x0), x1) 8.42/3.05 fst(x0, mark(x1)) 8.42/3.05 fst(active(x0), x1) 8.42/3.05 fst(x0, active(x1)) 8.42/3.05 s(mark(x0)) 8.42/3.05 s(active(x0)) 8.42/3.05 from(mark(x0)) 8.42/3.05 from(active(x0)) 8.42/3.05 add(mark(x0), x1) 8.42/3.05 add(x0, mark(x1)) 8.42/3.05 add(active(x0), x1) 8.42/3.05 add(x0, active(x1)) 8.42/3.05 len(mark(x0)) 8.42/3.05 len(active(x0)) 8.42/3.05 8.42/3.05 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (61) 8.42/3.05 Obligation: 8.42/3.05 Q DP problem: 8.42/3.05 The TRS P consists of the following rules: 8.42/3.05 8.42/3.05 MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.05 8.42/3.05 R is empty. 8.42/3.05 The set Q consists of the following terms: 8.42/3.05 8.42/3.05 cons(mark(x0), x1) 8.42/3.05 cons(x0, mark(x1)) 8.42/3.05 cons(active(x0), x1) 8.42/3.05 cons(x0, active(x1)) 8.42/3.05 8.42/3.05 We have to consider all minimal (P,Q,R)-chains. 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (62) QDPSizeChangeProof (EQUIVALENT) 8.42/3.05 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. 8.42/3.05 8.42/3.05 From the DPs we obtained the following set of size-change graphs: 8.42/3.05 *MARK(cons(X1, X2)) -> MARK(X1) 8.42/3.05 The graph contains the following edges 1 > 1 8.42/3.05 8.42/3.05 8.42/3.05 ---------------------------------------- 8.42/3.05 8.42/3.05 (63) 8.42/3.05 YES 8.42/3.08 EOF