4.30/1.99 YES 4.54/2.01 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 4.54/2.01 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.54/2.01 4.54/2.01 4.54/2.01 Termination w.r.t. Q of the given QTRS could be proven: 4.54/2.01 4.54/2.01 (0) QTRS 4.54/2.01 (1) DependencyPairsProof [EQUIVALENT, 0 ms] 4.54/2.01 (2) QDP 4.54/2.01 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 4.54/2.01 (4) AND 4.54/2.01 (5) QDP 4.54/2.01 (6) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (7) QDP 4.54/2.01 (8) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (9) QDP 4.54/2.01 (10) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (11) YES 4.54/2.01 (12) QDP 4.54/2.01 (13) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (14) QDP 4.54/2.01 (15) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (16) QDP 4.54/2.01 (17) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (18) YES 4.54/2.01 (19) QDP 4.54/2.01 (20) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (21) QDP 4.54/2.01 (22) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (23) QDP 4.54/2.01 (24) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (25) YES 4.54/2.01 (26) QDP 4.54/2.01 (27) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (28) QDP 4.54/2.01 (29) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (30) QDP 4.54/2.01 (31) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (32) YES 4.54/2.01 (33) QDP 4.54/2.01 (34) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (35) QDP 4.54/2.01 (36) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (37) QDP 4.54/2.01 (38) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (39) YES 4.54/2.01 (40) QDP 4.54/2.01 (41) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (42) QDP 4.54/2.01 (43) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (44) QDP 4.54/2.01 (45) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (46) YES 4.54/2.01 (47) QDP 4.54/2.01 (48) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (49) QDP 4.54/2.01 (50) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (51) QDP 4.54/2.01 (52) UsableRulesReductionPairsProof [EQUIVALENT, 0 ms] 4.54/2.01 (53) QDP 4.54/2.01 (54) PisEmptyProof [EQUIVALENT, 0 ms] 4.54/2.01 (55) YES 4.54/2.01 (56) QDP 4.54/2.01 (57) UsableRulesProof [EQUIVALENT, 0 ms] 4.54/2.01 (58) QDP 4.54/2.01 (59) QReductionProof [EQUIVALENT, 0 ms] 4.54/2.01 (60) QDP 4.54/2.01 (61) QDPSizeChangeProof [EQUIVALENT, 0 ms] 4.54/2.01 (62) YES 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (0) 4.54/2.01 Obligation: 4.54/2.01 Q restricted rewrite system: 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (1) DependencyPairsProof (EQUIVALENT) 4.54/2.01 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (2) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 ACTIVE(eq(0, 0)) -> MARK(true) 4.54/2.01 ACTIVE(eq(s(X), s(Y))) -> MARK(eq(X, Y)) 4.54/2.01 ACTIVE(eq(s(X), s(Y))) -> EQ(X, Y) 4.54/2.01 ACTIVE(eq(X, Y)) -> MARK(false) 4.54/2.01 ACTIVE(inf(X)) -> MARK(cons(X, inf(s(X)))) 4.54/2.01 ACTIVE(inf(X)) -> CONS(X, inf(s(X))) 4.54/2.01 ACTIVE(inf(X)) -> INF(s(X)) 4.54/2.01 ACTIVE(inf(X)) -> S(X) 4.54/2.01 ACTIVE(take(0, X)) -> MARK(nil) 4.54/2.01 ACTIVE(take(s(X), cons(Y, L))) -> MARK(cons(Y, take(X, L))) 4.54/2.01 ACTIVE(take(s(X), cons(Y, L))) -> CONS(Y, take(X, L)) 4.54/2.01 ACTIVE(take(s(X), cons(Y, L))) -> TAKE(X, L) 4.54/2.01 ACTIVE(length(nil)) -> MARK(0) 4.54/2.01 ACTIVE(length(cons(X, L))) -> MARK(s(length(L))) 4.54/2.01 ACTIVE(length(cons(X, L))) -> S(length(L)) 4.54/2.01 ACTIVE(length(cons(X, L))) -> LENGTH(L) 4.54/2.01 MARK(eq(X1, X2)) -> ACTIVE(eq(X1, X2)) 4.54/2.01 MARK(0) -> ACTIVE(0) 4.54/2.01 MARK(true) -> ACTIVE(true) 4.54/2.01 MARK(s(X)) -> ACTIVE(s(X)) 4.54/2.01 MARK(false) -> ACTIVE(false) 4.54/2.01 MARK(inf(X)) -> ACTIVE(inf(mark(X))) 4.54/2.01 MARK(inf(X)) -> INF(mark(X)) 4.54/2.01 MARK(inf(X)) -> MARK(X) 4.54/2.01 MARK(cons(X1, X2)) -> ACTIVE(cons(X1, X2)) 4.54/2.01 MARK(take(X1, X2)) -> ACTIVE(take(mark(X1), mark(X2))) 4.54/2.01 MARK(take(X1, X2)) -> TAKE(mark(X1), mark(X2)) 4.54/2.01 MARK(take(X1, X2)) -> MARK(X1) 4.54/2.01 MARK(take(X1, X2)) -> MARK(X2) 4.54/2.01 MARK(nil) -> ACTIVE(nil) 4.54/2.01 MARK(length(X)) -> ACTIVE(length(mark(X))) 4.54/2.01 MARK(length(X)) -> LENGTH(mark(X)) 4.54/2.01 MARK(length(X)) -> MARK(X) 4.54/2.01 EQ(mark(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(X1, mark(X2)) -> EQ(X1, X2) 4.54/2.01 EQ(active(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(X1, active(X2)) -> EQ(X1, X2) 4.54/2.01 S(mark(X)) -> S(X) 4.54/2.01 S(active(X)) -> S(X) 4.54/2.01 INF(mark(X)) -> INF(X) 4.54/2.01 INF(active(X)) -> INF(X) 4.54/2.01 CONS(mark(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 4.54/2.01 CONS(active(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(X1, active(X2)) -> CONS(X1, X2) 4.54/2.01 TAKE(mark(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(X1, mark(X2)) -> TAKE(X1, X2) 4.54/2.01 TAKE(active(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(X1, active(X2)) -> TAKE(X1, X2) 4.54/2.01 LENGTH(mark(X)) -> LENGTH(X) 4.54/2.01 LENGTH(active(X)) -> LENGTH(X) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (3) DependencyGraphProof (EQUIVALENT) 4.54/2.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 8 SCCs with 27 less nodes. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (4) 4.54/2.01 Complex Obligation (AND) 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (5) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 LENGTH(active(X)) -> LENGTH(X) 4.54/2.01 LENGTH(mark(X)) -> LENGTH(X) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (6) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (7) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 LENGTH(active(X)) -> LENGTH(X) 4.54/2.01 LENGTH(mark(X)) -> LENGTH(X) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (8) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (9) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 LENGTH(active(X)) -> LENGTH(X) 4.54/2.01 LENGTH(mark(X)) -> LENGTH(X) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (10) QDPSizeChangeProof (EQUIVALENT) 4.54/2.01 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.01 4.54/2.01 From the DPs we obtained the following set of size-change graphs: 4.54/2.01 *LENGTH(active(X)) -> LENGTH(X) 4.54/2.01 The graph contains the following edges 1 > 1 4.54/2.01 4.54/2.01 4.54/2.01 *LENGTH(mark(X)) -> LENGTH(X) 4.54/2.01 The graph contains the following edges 1 > 1 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (11) 4.54/2.01 YES 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (12) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 TAKE(X1, mark(X2)) -> TAKE(X1, X2) 4.54/2.01 TAKE(mark(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(active(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(X1, active(X2)) -> TAKE(X1, X2) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (13) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (14) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 TAKE(X1, mark(X2)) -> TAKE(X1, X2) 4.54/2.01 TAKE(mark(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(active(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(X1, active(X2)) -> TAKE(X1, X2) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (15) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (16) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 TAKE(X1, mark(X2)) -> TAKE(X1, X2) 4.54/2.01 TAKE(mark(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(active(X1), X2) -> TAKE(X1, X2) 4.54/2.01 TAKE(X1, active(X2)) -> TAKE(X1, X2) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (17) QDPSizeChangeProof (EQUIVALENT) 4.54/2.01 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.01 4.54/2.01 From the DPs we obtained the following set of size-change graphs: 4.54/2.01 *TAKE(X1, mark(X2)) -> TAKE(X1, X2) 4.54/2.01 The graph contains the following edges 1 >= 1, 2 > 2 4.54/2.01 4.54/2.01 4.54/2.01 *TAKE(mark(X1), X2) -> TAKE(X1, X2) 4.54/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.54/2.01 4.54/2.01 4.54/2.01 *TAKE(active(X1), X2) -> TAKE(X1, X2) 4.54/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.54/2.01 4.54/2.01 4.54/2.01 *TAKE(X1, active(X2)) -> TAKE(X1, X2) 4.54/2.01 The graph contains the following edges 1 >= 1, 2 > 2 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (18) 4.54/2.01 YES 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (19) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 4.54/2.01 CONS(mark(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(active(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(X1, active(X2)) -> CONS(X1, X2) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (20) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (21) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 4.54/2.01 CONS(mark(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(active(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(X1, active(X2)) -> CONS(X1, X2) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (22) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (23) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 4.54/2.01 CONS(mark(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(active(X1), X2) -> CONS(X1, X2) 4.54/2.01 CONS(X1, active(X2)) -> CONS(X1, X2) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (24) QDPSizeChangeProof (EQUIVALENT) 4.54/2.01 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.01 4.54/2.01 From the DPs we obtained the following set of size-change graphs: 4.54/2.01 *CONS(X1, mark(X2)) -> CONS(X1, X2) 4.54/2.01 The graph contains the following edges 1 >= 1, 2 > 2 4.54/2.01 4.54/2.01 4.54/2.01 *CONS(mark(X1), X2) -> CONS(X1, X2) 4.54/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.54/2.01 4.54/2.01 4.54/2.01 *CONS(active(X1), X2) -> CONS(X1, X2) 4.54/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.54/2.01 4.54/2.01 4.54/2.01 *CONS(X1, active(X2)) -> CONS(X1, X2) 4.54/2.01 The graph contains the following edges 1 >= 1, 2 > 2 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (25) 4.54/2.01 YES 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (26) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 INF(active(X)) -> INF(X) 4.54/2.01 INF(mark(X)) -> INF(X) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (27) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (28) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 INF(active(X)) -> INF(X) 4.54/2.01 INF(mark(X)) -> INF(X) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (29) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (30) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 INF(active(X)) -> INF(X) 4.54/2.01 INF(mark(X)) -> INF(X) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (31) QDPSizeChangeProof (EQUIVALENT) 4.54/2.01 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.01 4.54/2.01 From the DPs we obtained the following set of size-change graphs: 4.54/2.01 *INF(active(X)) -> INF(X) 4.54/2.01 The graph contains the following edges 1 > 1 4.54/2.01 4.54/2.01 4.54/2.01 *INF(mark(X)) -> INF(X) 4.54/2.01 The graph contains the following edges 1 > 1 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (32) 4.54/2.01 YES 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (33) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 S(active(X)) -> S(X) 4.54/2.01 S(mark(X)) -> S(X) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (34) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (35) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 S(active(X)) -> S(X) 4.54/2.01 S(mark(X)) -> S(X) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (36) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (37) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 S(active(X)) -> S(X) 4.54/2.01 S(mark(X)) -> S(X) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (38) QDPSizeChangeProof (EQUIVALENT) 4.54/2.01 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.01 4.54/2.01 From the DPs we obtained the following set of size-change graphs: 4.54/2.01 *S(active(X)) -> S(X) 4.54/2.01 The graph contains the following edges 1 > 1 4.54/2.01 4.54/2.01 4.54/2.01 *S(mark(X)) -> S(X) 4.54/2.01 The graph contains the following edges 1 > 1 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (39) 4.54/2.01 YES 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (40) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 EQ(X1, mark(X2)) -> EQ(X1, X2) 4.54/2.01 EQ(mark(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(active(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(X1, active(X2)) -> EQ(X1, X2) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (41) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (42) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 EQ(X1, mark(X2)) -> EQ(X1, X2) 4.54/2.01 EQ(mark(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(active(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(X1, active(X2)) -> EQ(X1, X2) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (43) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (44) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 EQ(X1, mark(X2)) -> EQ(X1, X2) 4.54/2.01 EQ(mark(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(active(X1), X2) -> EQ(X1, X2) 4.54/2.01 EQ(X1, active(X2)) -> EQ(X1, X2) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (45) QDPSizeChangeProof (EQUIVALENT) 4.54/2.01 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.01 4.54/2.01 From the DPs we obtained the following set of size-change graphs: 4.54/2.01 *EQ(X1, mark(X2)) -> EQ(X1, X2) 4.54/2.01 The graph contains the following edges 1 >= 1, 2 > 2 4.54/2.01 4.54/2.01 4.54/2.01 *EQ(mark(X1), X2) -> EQ(X1, X2) 4.54/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.54/2.01 4.54/2.01 4.54/2.01 *EQ(active(X1), X2) -> EQ(X1, X2) 4.54/2.01 The graph contains the following edges 1 > 1, 2 >= 2 4.54/2.01 4.54/2.01 4.54/2.01 *EQ(X1, active(X2)) -> EQ(X1, X2) 4.54/2.01 The graph contains the following edges 1 >= 1, 2 > 2 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (46) 4.54/2.01 YES 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (47) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 ACTIVE(eq(s(X), s(Y))) -> MARK(eq(X, Y)) 4.54/2.01 MARK(eq(X1, X2)) -> ACTIVE(eq(X1, X2)) 4.54/2.01 4.54/2.01 The TRS R consists of the following rules: 4.54/2.01 4.54/2.01 active(eq(0, 0)) -> mark(true) 4.54/2.01 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.01 active(eq(X, Y)) -> mark(false) 4.54/2.01 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.01 active(take(0, X)) -> mark(nil) 4.54/2.01 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.01 active(length(nil)) -> mark(0) 4.54/2.01 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.01 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.01 mark(0) -> active(0) 4.54/2.01 mark(true) -> active(true) 4.54/2.01 mark(s(X)) -> active(s(X)) 4.54/2.01 mark(false) -> active(false) 4.54/2.01 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.01 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.01 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.01 mark(nil) -> active(nil) 4.54/2.01 mark(length(X)) -> active(length(mark(X))) 4.54/2.01 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.01 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.01 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.01 s(mark(X)) -> s(X) 4.54/2.01 s(active(X)) -> s(X) 4.54/2.01 inf(mark(X)) -> inf(X) 4.54/2.01 inf(active(X)) -> inf(X) 4.54/2.01 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.01 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.01 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.01 take(mark(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.01 take(active(X1), X2) -> take(X1, X2) 4.54/2.01 take(X1, active(X2)) -> take(X1, X2) 4.54/2.01 length(mark(X)) -> length(X) 4.54/2.01 length(active(X)) -> length(X) 4.54/2.01 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (48) UsableRulesProof (EQUIVALENT) 4.54/2.01 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. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (49) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 ACTIVE(eq(s(X), s(Y))) -> MARK(eq(X, Y)) 4.54/2.01 MARK(eq(X1, X2)) -> ACTIVE(eq(X1, X2)) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (50) QReductionProof (EQUIVALENT) 4.54/2.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.01 4.54/2.01 active(eq(x0, x1)) 4.54/2.01 active(inf(x0)) 4.54/2.01 active(take(0, x0)) 4.54/2.01 active(take(s(x0), cons(x1, x2))) 4.54/2.01 active(length(nil)) 4.54/2.01 active(length(cons(x0, x1))) 4.54/2.01 mark(eq(x0, x1)) 4.54/2.01 mark(0) 4.54/2.01 mark(true) 4.54/2.01 mark(s(x0)) 4.54/2.01 mark(false) 4.54/2.01 mark(inf(x0)) 4.54/2.01 mark(cons(x0, x1)) 4.54/2.01 mark(take(x0, x1)) 4.54/2.01 mark(nil) 4.54/2.01 mark(length(x0)) 4.54/2.01 inf(mark(x0)) 4.54/2.01 inf(active(x0)) 4.54/2.01 cons(mark(x0), x1) 4.54/2.01 cons(x0, mark(x1)) 4.54/2.01 cons(active(x0), x1) 4.54/2.01 cons(x0, active(x1)) 4.54/2.01 take(mark(x0), x1) 4.54/2.01 take(x0, mark(x1)) 4.54/2.01 take(active(x0), x1) 4.54/2.01 take(x0, active(x1)) 4.54/2.01 length(mark(x0)) 4.54/2.01 length(active(x0)) 4.54/2.01 4.54/2.01 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (51) 4.54/2.01 Obligation: 4.54/2.01 Q DP problem: 4.54/2.01 The TRS P consists of the following rules: 4.54/2.01 4.54/2.01 ACTIVE(eq(s(X), s(Y))) -> MARK(eq(X, Y)) 4.54/2.01 MARK(eq(X1, X2)) -> ACTIVE(eq(X1, X2)) 4.54/2.01 4.54/2.01 R is empty. 4.54/2.01 The set Q consists of the following terms: 4.54/2.01 4.54/2.01 eq(mark(x0), x1) 4.54/2.01 eq(x0, mark(x1)) 4.54/2.01 eq(active(x0), x1) 4.54/2.01 eq(x0, active(x1)) 4.54/2.01 s(mark(x0)) 4.54/2.01 s(active(x0)) 4.54/2.01 4.54/2.01 We have to consider all minimal (P,Q,R)-chains. 4.54/2.01 ---------------------------------------- 4.54/2.01 4.54/2.01 (52) UsableRulesReductionPairsProof (EQUIVALENT) 4.54/2.01 By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well. 4.54/2.02 4.54/2.02 The following dependency pairs can be deleted: 4.54/2.02 4.54/2.02 ACTIVE(eq(s(X), s(Y))) -> MARK(eq(X, Y)) 4.54/2.02 MARK(eq(X1, X2)) -> ACTIVE(eq(X1, X2)) 4.54/2.02 No rules are removed from R. 4.54/2.02 4.54/2.02 Used ordering: POLO with Polynomial interpretation [POLO]: 4.54/2.02 4.54/2.02 POL(ACTIVE(x_1)) = x_1 4.54/2.02 POL(MARK(x_1)) = 2*x_1 4.54/2.02 POL(eq(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 4.54/2.02 POL(s(x_1)) = 2 + 2*x_1 4.54/2.02 4.54/2.02 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (53) 4.54/2.02 Obligation: 4.54/2.02 Q DP problem: 4.54/2.02 P is empty. 4.54/2.02 R is empty. 4.54/2.02 The set Q consists of the following terms: 4.54/2.02 4.54/2.02 eq(mark(x0), x1) 4.54/2.02 eq(x0, mark(x1)) 4.54/2.02 eq(active(x0), x1) 4.54/2.02 eq(x0, active(x1)) 4.54/2.02 s(mark(x0)) 4.54/2.02 s(active(x0)) 4.54/2.02 4.54/2.02 We have to consider all minimal (P,Q,R)-chains. 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (54) PisEmptyProof (EQUIVALENT) 4.54/2.02 The TRS P is empty. Hence, there is no (P,Q,R) chain. 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (55) 4.54/2.02 YES 4.54/2.02 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (56) 4.54/2.02 Obligation: 4.54/2.02 Q DP problem: 4.54/2.02 The TRS P consists of the following rules: 4.54/2.02 4.54/2.02 MARK(take(X1, X2)) -> MARK(X1) 4.54/2.02 MARK(inf(X)) -> MARK(X) 4.54/2.02 MARK(take(X1, X2)) -> MARK(X2) 4.54/2.02 MARK(length(X)) -> MARK(X) 4.54/2.02 4.54/2.02 The TRS R consists of the following rules: 4.54/2.02 4.54/2.02 active(eq(0, 0)) -> mark(true) 4.54/2.02 active(eq(s(X), s(Y))) -> mark(eq(X, Y)) 4.54/2.02 active(eq(X, Y)) -> mark(false) 4.54/2.02 active(inf(X)) -> mark(cons(X, inf(s(X)))) 4.54/2.02 active(take(0, X)) -> mark(nil) 4.54/2.02 active(take(s(X), cons(Y, L))) -> mark(cons(Y, take(X, L))) 4.54/2.02 active(length(nil)) -> mark(0) 4.54/2.02 active(length(cons(X, L))) -> mark(s(length(L))) 4.54/2.02 mark(eq(X1, X2)) -> active(eq(X1, X2)) 4.54/2.02 mark(0) -> active(0) 4.54/2.02 mark(true) -> active(true) 4.54/2.02 mark(s(X)) -> active(s(X)) 4.54/2.02 mark(false) -> active(false) 4.54/2.02 mark(inf(X)) -> active(inf(mark(X))) 4.54/2.02 mark(cons(X1, X2)) -> active(cons(X1, X2)) 4.54/2.02 mark(take(X1, X2)) -> active(take(mark(X1), mark(X2))) 4.54/2.02 mark(nil) -> active(nil) 4.54/2.02 mark(length(X)) -> active(length(mark(X))) 4.54/2.02 eq(mark(X1), X2) -> eq(X1, X2) 4.54/2.02 eq(X1, mark(X2)) -> eq(X1, X2) 4.54/2.02 eq(active(X1), X2) -> eq(X1, X2) 4.54/2.02 eq(X1, active(X2)) -> eq(X1, X2) 4.54/2.02 s(mark(X)) -> s(X) 4.54/2.02 s(active(X)) -> s(X) 4.54/2.02 inf(mark(X)) -> inf(X) 4.54/2.02 inf(active(X)) -> inf(X) 4.54/2.02 cons(mark(X1), X2) -> cons(X1, X2) 4.54/2.02 cons(X1, mark(X2)) -> cons(X1, X2) 4.54/2.02 cons(active(X1), X2) -> cons(X1, X2) 4.54/2.02 cons(X1, active(X2)) -> cons(X1, X2) 4.54/2.02 take(mark(X1), X2) -> take(X1, X2) 4.54/2.02 take(X1, mark(X2)) -> take(X1, X2) 4.54/2.02 take(active(X1), X2) -> take(X1, X2) 4.54/2.02 take(X1, active(X2)) -> take(X1, X2) 4.54/2.02 length(mark(X)) -> length(X) 4.54/2.02 length(active(X)) -> length(X) 4.54/2.02 4.54/2.02 The set Q consists of the following terms: 4.54/2.02 4.54/2.02 active(eq(x0, x1)) 4.54/2.02 active(inf(x0)) 4.54/2.02 active(take(0, x0)) 4.54/2.02 active(take(s(x0), cons(x1, x2))) 4.54/2.02 active(length(nil)) 4.54/2.02 active(length(cons(x0, x1))) 4.54/2.02 mark(eq(x0, x1)) 4.54/2.02 mark(0) 4.54/2.02 mark(true) 4.54/2.02 mark(s(x0)) 4.54/2.02 mark(false) 4.54/2.02 mark(inf(x0)) 4.54/2.02 mark(cons(x0, x1)) 4.54/2.02 mark(take(x0, x1)) 4.54/2.02 mark(nil) 4.54/2.02 mark(length(x0)) 4.54/2.02 eq(mark(x0), x1) 4.54/2.02 eq(x0, mark(x1)) 4.54/2.02 eq(active(x0), x1) 4.54/2.02 eq(x0, active(x1)) 4.54/2.02 s(mark(x0)) 4.54/2.02 s(active(x0)) 4.54/2.02 inf(mark(x0)) 4.54/2.02 inf(active(x0)) 4.54/2.02 cons(mark(x0), x1) 4.54/2.02 cons(x0, mark(x1)) 4.54/2.02 cons(active(x0), x1) 4.54/2.02 cons(x0, active(x1)) 4.54/2.02 take(mark(x0), x1) 4.54/2.02 take(x0, mark(x1)) 4.54/2.02 take(active(x0), x1) 4.54/2.02 take(x0, active(x1)) 4.54/2.02 length(mark(x0)) 4.54/2.02 length(active(x0)) 4.54/2.02 4.54/2.02 We have to consider all minimal (P,Q,R)-chains. 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (57) UsableRulesProof (EQUIVALENT) 4.54/2.02 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. 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (58) 4.54/2.02 Obligation: 4.54/2.02 Q DP problem: 4.54/2.02 The TRS P consists of the following rules: 4.54/2.02 4.54/2.02 MARK(take(X1, X2)) -> MARK(X1) 4.54/2.02 MARK(inf(X)) -> MARK(X) 4.54/2.02 MARK(take(X1, X2)) -> MARK(X2) 4.54/2.02 MARK(length(X)) -> MARK(X) 4.54/2.02 4.54/2.02 R is empty. 4.54/2.02 The set Q consists of the following terms: 4.54/2.02 4.54/2.02 active(eq(x0, x1)) 4.54/2.02 active(inf(x0)) 4.54/2.02 active(take(0, x0)) 4.54/2.02 active(take(s(x0), cons(x1, x2))) 4.54/2.02 active(length(nil)) 4.54/2.02 active(length(cons(x0, x1))) 4.54/2.02 mark(eq(x0, x1)) 4.54/2.02 mark(0) 4.54/2.02 mark(true) 4.54/2.02 mark(s(x0)) 4.54/2.02 mark(false) 4.54/2.02 mark(inf(x0)) 4.54/2.02 mark(cons(x0, x1)) 4.54/2.02 mark(take(x0, x1)) 4.54/2.02 mark(nil) 4.54/2.02 mark(length(x0)) 4.54/2.02 eq(mark(x0), x1) 4.54/2.02 eq(x0, mark(x1)) 4.54/2.02 eq(active(x0), x1) 4.54/2.02 eq(x0, active(x1)) 4.54/2.02 s(mark(x0)) 4.54/2.02 s(active(x0)) 4.54/2.02 inf(mark(x0)) 4.54/2.02 inf(active(x0)) 4.54/2.02 cons(mark(x0), x1) 4.54/2.02 cons(x0, mark(x1)) 4.54/2.02 cons(active(x0), x1) 4.54/2.02 cons(x0, active(x1)) 4.54/2.02 take(mark(x0), x1) 4.54/2.02 take(x0, mark(x1)) 4.54/2.02 take(active(x0), x1) 4.54/2.02 take(x0, active(x1)) 4.54/2.02 length(mark(x0)) 4.54/2.02 length(active(x0)) 4.54/2.02 4.54/2.02 We have to consider all minimal (P,Q,R)-chains. 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (59) QReductionProof (EQUIVALENT) 4.54/2.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 4.54/2.02 4.54/2.02 active(eq(x0, x1)) 4.54/2.02 active(inf(x0)) 4.54/2.02 active(take(0, x0)) 4.54/2.02 active(take(s(x0), cons(x1, x2))) 4.54/2.02 active(length(nil)) 4.54/2.02 active(length(cons(x0, x1))) 4.54/2.02 mark(eq(x0, x1)) 4.54/2.02 mark(0) 4.54/2.02 mark(true) 4.54/2.02 mark(s(x0)) 4.54/2.02 mark(false) 4.54/2.02 mark(inf(x0)) 4.54/2.02 mark(cons(x0, x1)) 4.54/2.02 mark(take(x0, x1)) 4.54/2.02 mark(nil) 4.54/2.02 mark(length(x0)) 4.54/2.02 eq(mark(x0), x1) 4.54/2.02 eq(x0, mark(x1)) 4.54/2.02 eq(active(x0), x1) 4.54/2.02 eq(x0, active(x1)) 4.54/2.02 s(mark(x0)) 4.54/2.02 s(active(x0)) 4.54/2.02 cons(mark(x0), x1) 4.54/2.02 cons(x0, mark(x1)) 4.54/2.02 cons(active(x0), x1) 4.54/2.02 cons(x0, active(x1)) 4.54/2.02 4.54/2.02 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (60) 4.54/2.02 Obligation: 4.54/2.02 Q DP problem: 4.54/2.02 The TRS P consists of the following rules: 4.54/2.02 4.54/2.02 MARK(take(X1, X2)) -> MARK(X1) 4.54/2.02 MARK(inf(X)) -> MARK(X) 4.54/2.02 MARK(take(X1, X2)) -> MARK(X2) 4.54/2.02 MARK(length(X)) -> MARK(X) 4.54/2.02 4.54/2.02 R is empty. 4.54/2.02 The set Q consists of the following terms: 4.54/2.02 4.54/2.02 inf(mark(x0)) 4.54/2.02 inf(active(x0)) 4.54/2.02 take(mark(x0), x1) 4.54/2.02 take(x0, mark(x1)) 4.54/2.02 take(active(x0), x1) 4.54/2.02 take(x0, active(x1)) 4.54/2.02 length(mark(x0)) 4.54/2.02 length(active(x0)) 4.54/2.02 4.54/2.02 We have to consider all minimal (P,Q,R)-chains. 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (61) QDPSizeChangeProof (EQUIVALENT) 4.54/2.02 By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 4.54/2.02 4.54/2.02 From the DPs we obtained the following set of size-change graphs: 4.54/2.02 *MARK(take(X1, X2)) -> MARK(X1) 4.54/2.02 The graph contains the following edges 1 > 1 4.54/2.02 4.54/2.02 4.54/2.02 *MARK(inf(X)) -> MARK(X) 4.54/2.02 The graph contains the following edges 1 > 1 4.54/2.02 4.54/2.02 4.54/2.02 *MARK(take(X1, X2)) -> MARK(X2) 4.54/2.02 The graph contains the following edges 1 > 1 4.54/2.02 4.54/2.02 4.54/2.02 *MARK(length(X)) -> MARK(X) 4.54/2.02 The graph contains the following edges 1 > 1 4.54/2.02 4.54/2.02 4.54/2.02 ---------------------------------------- 4.54/2.02 4.54/2.02 (62) 4.54/2.02 YES 4.54/2.07 EOF