7.74/2.99 YES 7.74/3.00 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 7.74/3.00 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 7.74/3.00 7.74/3.00 7.74/3.00 Termination w.r.t. Q of the given QTRS could be proven: 7.74/3.00 7.74/3.00 (0) QTRS 7.74/3.00 (1) QTRSRRRProof [EQUIVALENT, 122 ms] 7.74/3.00 (2) QTRS 7.74/3.00 (3) QTRSRRRProof [EQUIVALENT, 34 ms] 7.74/3.00 (4) QTRS 7.74/3.00 (5) DependencyPairsProof [EQUIVALENT, 50 ms] 7.74/3.00 (6) QDP 7.74/3.00 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 7.74/3.00 (8) AND 7.74/3.00 (9) QDP 7.74/3.00 (10) UsableRulesProof [EQUIVALENT, 0 ms] 7.74/3.00 (11) QDP 7.74/3.00 (12) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (13) QDP 7.74/3.00 (14) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.74/3.00 (15) YES 7.74/3.00 (16) QDP 7.74/3.00 (17) UsableRulesProof [EQUIVALENT, 0 ms] 7.74/3.00 (18) QDP 7.74/3.00 (19) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (20) QDP 7.74/3.00 (21) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.74/3.00 (22) YES 7.74/3.00 (23) QDP 7.74/3.00 (24) UsableRulesProof [EQUIVALENT, 0 ms] 7.74/3.00 (25) QDP 7.74/3.00 (26) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (27) QDP 7.74/3.00 (28) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.74/3.00 (29) YES 7.74/3.00 (30) QDP 7.74/3.00 (31) UsableRulesProof [EQUIVALENT, 0 ms] 7.74/3.00 (32) QDP 7.74/3.00 (33) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (34) QDP 7.74/3.00 (35) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.74/3.00 (36) YES 7.74/3.00 (37) QDP 7.74/3.00 (38) UsableRulesProof [EQUIVALENT, 0 ms] 7.74/3.00 (39) QDP 7.74/3.00 (40) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (41) QDP 7.74/3.00 (42) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.74/3.00 (43) YES 7.74/3.00 (44) QDP 7.74/3.00 (45) MRRProof [EQUIVALENT, 36 ms] 7.74/3.00 (46) QDP 7.74/3.00 (47) MRRProof [EQUIVALENT, 27 ms] 7.74/3.00 (48) QDP 7.74/3.00 (49) QDPOrderProof [EQUIVALENT, 106 ms] 7.74/3.00 (50) QDP 7.74/3.00 (51) DependencyGraphProof [EQUIVALENT, 0 ms] 7.74/3.00 (52) AND 7.74/3.00 (53) QDP 7.74/3.00 (54) QDPOrderProof [EQUIVALENT, 0 ms] 7.74/3.00 (55) QDP 7.74/3.00 (56) PisEmptyProof [EQUIVALENT, 0 ms] 7.74/3.00 (57) YES 7.74/3.00 (58) QDP 7.74/3.00 (59) UsableRulesProof [EQUIVALENT, 0 ms] 7.74/3.00 (60) QDP 7.74/3.00 (61) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (62) QDP 7.74/3.00 (63) UsableRulesReductionPairsProof [EQUIVALENT, 6 ms] 7.74/3.00 (64) QDP 7.74/3.00 (65) QReductionProof [EQUIVALENT, 0 ms] 7.74/3.00 (66) QDP 7.74/3.00 (67) MRRProof [EQUIVALENT, 0 ms] 7.74/3.00 (68) QDP 7.74/3.00 (69) QDPSizeChangeProof [EQUIVALENT, 0 ms] 7.74/3.00 (70) YES 7.74/3.00 7.74/3.00 7.74/3.00 ---------------------------------------- 7.74/3.00 7.74/3.00 (0) 7.74/3.00 Obligation: 7.74/3.00 Q restricted rewrite system: 7.74/3.00 The TRS R consists of the following rules: 7.74/3.00 7.74/3.00 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.00 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.00 active(odds) -> mark(incr(pairs)) 7.74/3.00 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.00 active(head(cons(X, XS))) -> mark(X) 7.74/3.00 active(tail(cons(X, XS))) -> mark(XS) 7.74/3.00 mark(nats) -> active(nats) 7.74/3.00 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.00 mark(0) -> active(0) 7.74/3.00 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.00 mark(pairs) -> active(pairs) 7.74/3.00 mark(odds) -> active(odds) 7.74/3.00 mark(s(X)) -> active(s(mark(X))) 7.74/3.00 mark(head(X)) -> active(head(mark(X))) 7.74/3.00 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.00 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.00 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.00 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.00 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.00 incr(mark(X)) -> incr(X) 7.74/3.00 incr(active(X)) -> incr(X) 7.74/3.00 s(mark(X)) -> s(X) 7.74/3.00 s(active(X)) -> s(X) 7.74/3.00 head(mark(X)) -> head(X) 7.74/3.00 head(active(X)) -> head(X) 7.74/3.00 tail(mark(X)) -> tail(X) 7.74/3.00 tail(active(X)) -> tail(X) 7.74/3.00 7.74/3.00 The set Q consists of the following terms: 7.74/3.00 7.74/3.00 active(nats) 7.74/3.00 active(pairs) 7.74/3.00 active(odds) 7.74/3.00 active(incr(cons(x0, x1))) 7.74/3.00 active(head(cons(x0, x1))) 7.74/3.00 active(tail(cons(x0, x1))) 7.74/3.00 mark(nats) 7.74/3.00 mark(cons(x0, x1)) 7.74/3.00 mark(0) 7.74/3.00 mark(incr(x0)) 7.74/3.00 mark(pairs) 7.74/3.00 mark(odds) 7.74/3.00 mark(s(x0)) 7.74/3.00 mark(head(x0)) 7.74/3.00 mark(tail(x0)) 7.74/3.00 cons(mark(x0), x1) 7.74/3.00 cons(x0, mark(x1)) 7.74/3.00 cons(active(x0), x1) 7.74/3.00 cons(x0, active(x1)) 7.74/3.00 incr(mark(x0)) 7.74/3.00 incr(active(x0)) 7.74/3.00 s(mark(x0)) 7.74/3.00 s(active(x0)) 7.74/3.00 head(mark(x0)) 7.74/3.00 head(active(x0)) 7.74/3.00 tail(mark(x0)) 7.74/3.00 tail(active(x0)) 7.74/3.00 7.74/3.00 7.74/3.00 ---------------------------------------- 7.74/3.00 7.74/3.00 (1) QTRSRRRProof (EQUIVALENT) 7.74/3.00 Used ordering: 7.74/3.00 Polynomial interpretation [POLO]: 7.74/3.00 7.74/3.00 POL(0) = 0 7.74/3.00 POL(active(x_1)) = x_1 7.74/3.00 POL(cons(x_1, x_2)) = x_1 + x_2 7.74/3.00 POL(head(x_1)) = 1 + x_1 7.74/3.00 POL(incr(x_1)) = 2*x_1 7.74/3.00 POL(mark(x_1)) = x_1 7.74/3.00 POL(nats) = 0 7.74/3.00 POL(odds) = 0 7.74/3.00 POL(pairs) = 0 7.74/3.00 POL(s(x_1)) = x_1 7.74/3.00 POL(tail(x_1)) = x_1 7.74/3.00 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.74/3.00 7.74/3.00 active(head(cons(X, XS))) -> mark(X) 7.74/3.00 7.74/3.00 7.74/3.00 7.74/3.00 7.74/3.00 ---------------------------------------- 7.74/3.00 7.74/3.00 (2) 7.74/3.00 Obligation: 7.74/3.00 Q restricted rewrite system: 7.74/3.00 The TRS R consists of the following rules: 7.74/3.00 7.74/3.00 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.00 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.00 active(odds) -> mark(incr(pairs)) 7.74/3.00 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.00 active(tail(cons(X, XS))) -> mark(XS) 7.74/3.00 mark(nats) -> active(nats) 7.74/3.00 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.00 mark(0) -> active(0) 7.74/3.00 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.00 mark(pairs) -> active(pairs) 7.74/3.00 mark(odds) -> active(odds) 7.74/3.00 mark(s(X)) -> active(s(mark(X))) 7.74/3.00 mark(head(X)) -> active(head(mark(X))) 7.74/3.00 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.00 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.00 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.00 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.00 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.00 incr(mark(X)) -> incr(X) 7.74/3.00 incr(active(X)) -> incr(X) 7.74/3.00 s(mark(X)) -> s(X) 7.74/3.00 s(active(X)) -> s(X) 7.74/3.00 head(mark(X)) -> head(X) 7.74/3.00 head(active(X)) -> head(X) 7.74/3.00 tail(mark(X)) -> tail(X) 7.74/3.00 tail(active(X)) -> tail(X) 7.74/3.00 7.74/3.00 The set Q consists of the following terms: 7.74/3.00 7.74/3.00 active(nats) 7.74/3.00 active(pairs) 7.74/3.00 active(odds) 7.74/3.00 active(incr(cons(x0, x1))) 7.74/3.00 active(head(cons(x0, x1))) 7.74/3.00 active(tail(cons(x0, x1))) 7.74/3.00 mark(nats) 7.74/3.00 mark(cons(x0, x1)) 7.74/3.00 mark(0) 7.74/3.00 mark(incr(x0)) 7.74/3.00 mark(pairs) 7.74/3.00 mark(odds) 7.74/3.00 mark(s(x0)) 7.74/3.00 mark(head(x0)) 7.74/3.00 mark(tail(x0)) 7.74/3.00 cons(mark(x0), x1) 7.74/3.00 cons(x0, mark(x1)) 7.74/3.00 cons(active(x0), x1) 7.74/3.00 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (3) QTRSRRRProof (EQUIVALENT) 7.74/3.01 Used ordering: 7.74/3.01 Polynomial interpretation [POLO]: 7.74/3.01 7.74/3.01 POL(0) = 0 7.74/3.01 POL(active(x_1)) = x_1 7.74/3.01 POL(cons(x_1, x_2)) = x_1 + x_2 7.74/3.01 POL(head(x_1)) = 2*x_1 7.74/3.01 POL(incr(x_1)) = 2*x_1 7.74/3.01 POL(mark(x_1)) = x_1 7.74/3.01 POL(nats) = 0 7.74/3.01 POL(odds) = 0 7.74/3.01 POL(pairs) = 0 7.74/3.01 POL(s(x_1)) = x_1 7.74/3.01 POL(tail(x_1)) = 1 + 2*x_1 7.74/3.01 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 7.74/3.01 7.74/3.01 active(tail(cons(X, XS))) -> mark(XS) 7.74/3.01 7.74/3.01 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (4) 7.74/3.01 Obligation: 7.74/3.01 Q restricted rewrite system: 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (5) DependencyPairsProof (EQUIVALENT) 7.74/3.01 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (6) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 ACTIVE(nats) -> MARK(cons(0, incr(nats))) 7.74/3.01 ACTIVE(nats) -> CONS(0, incr(nats)) 7.74/3.01 ACTIVE(nats) -> INCR(nats) 7.74/3.01 ACTIVE(pairs) -> MARK(cons(0, incr(odds))) 7.74/3.01 ACTIVE(pairs) -> CONS(0, incr(odds)) 7.74/3.01 ACTIVE(pairs) -> INCR(odds) 7.74/3.01 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.01 ACTIVE(odds) -> INCR(pairs) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> CONS(s(X), incr(XS)) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> S(X) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> INCR(XS) 7.74/3.01 MARK(nats) -> ACTIVE(nats) 7.74/3.01 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.01 MARK(cons(X1, X2)) -> CONS(mark(X1), X2) 7.74/3.01 MARK(cons(X1, X2)) -> MARK(X1) 7.74/3.01 MARK(0) -> ACTIVE(0) 7.74/3.01 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 7.74/3.01 MARK(incr(X)) -> INCR(mark(X)) 7.74/3.01 MARK(incr(X)) -> MARK(X) 7.74/3.01 MARK(pairs) -> ACTIVE(pairs) 7.74/3.01 MARK(odds) -> ACTIVE(odds) 7.74/3.01 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.74/3.01 MARK(s(X)) -> S(mark(X)) 7.74/3.01 MARK(s(X)) -> MARK(X) 7.74/3.01 MARK(head(X)) -> ACTIVE(head(mark(X))) 7.74/3.01 MARK(head(X)) -> HEAD(mark(X)) 7.74/3.01 MARK(head(X)) -> MARK(X) 7.74/3.01 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 7.74/3.01 MARK(tail(X)) -> TAIL(mark(X)) 7.74/3.01 MARK(tail(X)) -> MARK(X) 7.74/3.01 CONS(mark(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.74/3.01 CONS(active(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(X1, active(X2)) -> CONS(X1, X2) 7.74/3.01 INCR(mark(X)) -> INCR(X) 7.74/3.01 INCR(active(X)) -> INCR(X) 7.74/3.01 S(mark(X)) -> S(X) 7.74/3.01 S(active(X)) -> S(X) 7.74/3.01 HEAD(mark(X)) -> HEAD(X) 7.74/3.01 HEAD(active(X)) -> HEAD(X) 7.74/3.01 TAIL(mark(X)) -> TAIL(X) 7.74/3.01 TAIL(active(X)) -> TAIL(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (7) DependencyGraphProof (EQUIVALENT) 7.74/3.01 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 6 SCCs with 14 less nodes. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (8) 7.74/3.01 Complex Obligation (AND) 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (9) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 TAIL(active(X)) -> TAIL(X) 7.74/3.01 TAIL(mark(X)) -> TAIL(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (10) UsableRulesProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (11) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 TAIL(active(X)) -> TAIL(X) 7.74/3.01 TAIL(mark(X)) -> TAIL(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (12) QReductionProof (EQUIVALENT) 7.74/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.01 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (13) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 TAIL(active(X)) -> TAIL(X) 7.74/3.01 TAIL(mark(X)) -> TAIL(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (14) QDPSizeChangeProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 7.74/3.01 From the DPs we obtained the following set of size-change graphs: 7.74/3.01 *TAIL(active(X)) -> TAIL(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 *TAIL(mark(X)) -> TAIL(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (15) 7.74/3.01 YES 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (16) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 HEAD(active(X)) -> HEAD(X) 7.74/3.01 HEAD(mark(X)) -> HEAD(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (17) UsableRulesProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (18) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 HEAD(active(X)) -> HEAD(X) 7.74/3.01 HEAD(mark(X)) -> HEAD(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (19) QReductionProof (EQUIVALENT) 7.74/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.01 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (20) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 HEAD(active(X)) -> HEAD(X) 7.74/3.01 HEAD(mark(X)) -> HEAD(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (21) QDPSizeChangeProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 7.74/3.01 From the DPs we obtained the following set of size-change graphs: 7.74/3.01 *HEAD(active(X)) -> HEAD(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 *HEAD(mark(X)) -> HEAD(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (22) 7.74/3.01 YES 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (23) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 S(active(X)) -> S(X) 7.74/3.01 S(mark(X)) -> S(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (24) UsableRulesProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (25) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 S(active(X)) -> S(X) 7.74/3.01 S(mark(X)) -> S(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (26) QReductionProof (EQUIVALENT) 7.74/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.01 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (27) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 S(active(X)) -> S(X) 7.74/3.01 S(mark(X)) -> S(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (28) QDPSizeChangeProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 7.74/3.01 From the DPs we obtained the following set of size-change graphs: 7.74/3.01 *S(active(X)) -> S(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 *S(mark(X)) -> S(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (29) 7.74/3.01 YES 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (30) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 INCR(active(X)) -> INCR(X) 7.74/3.01 INCR(mark(X)) -> INCR(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (31) UsableRulesProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (32) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 INCR(active(X)) -> INCR(X) 7.74/3.01 INCR(mark(X)) -> INCR(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (33) QReductionProof (EQUIVALENT) 7.74/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.01 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (34) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 INCR(active(X)) -> INCR(X) 7.74/3.01 INCR(mark(X)) -> INCR(X) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (35) QDPSizeChangeProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 7.74/3.01 From the DPs we obtained the following set of size-change graphs: 7.74/3.01 *INCR(active(X)) -> INCR(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 *INCR(mark(X)) -> INCR(X) 7.74/3.01 The graph contains the following edges 1 > 1 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (36) 7.74/3.01 YES 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (37) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.74/3.01 CONS(mark(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(active(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(X1, active(X2)) -> CONS(X1, X2) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (38) UsableRulesProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (39) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.74/3.01 CONS(mark(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(active(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(X1, active(X2)) -> CONS(X1, X2) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (40) QReductionProof (EQUIVALENT) 7.74/3.01 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.01 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (41) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 CONS(X1, mark(X2)) -> CONS(X1, X2) 7.74/3.01 CONS(mark(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(active(X1), X2) -> CONS(X1, X2) 7.74/3.01 CONS(X1, active(X2)) -> CONS(X1, X2) 7.74/3.01 7.74/3.01 R is empty. 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (42) QDPSizeChangeProof (EQUIVALENT) 7.74/3.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. 7.74/3.01 7.74/3.01 From the DPs we obtained the following set of size-change graphs: 7.74/3.01 *CONS(X1, mark(X2)) -> CONS(X1, X2) 7.74/3.01 The graph contains the following edges 1 >= 1, 2 > 2 7.74/3.01 7.74/3.01 7.74/3.01 *CONS(mark(X1), X2) -> CONS(X1, X2) 7.74/3.01 The graph contains the following edges 1 > 1, 2 >= 2 7.74/3.01 7.74/3.01 7.74/3.01 *CONS(active(X1), X2) -> CONS(X1, X2) 7.74/3.01 The graph contains the following edges 1 > 1, 2 >= 2 7.74/3.01 7.74/3.01 7.74/3.01 *CONS(X1, active(X2)) -> CONS(X1, X2) 7.74/3.01 The graph contains the following edges 1 >= 1, 2 > 2 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (43) 7.74/3.01 YES 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (44) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.01 MARK(cons(X1, X2)) -> MARK(X1) 7.74/3.01 MARK(nats) -> ACTIVE(nats) 7.74/3.01 ACTIVE(nats) -> MARK(cons(0, incr(nats))) 7.74/3.01 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 7.74/3.01 MARK(incr(X)) -> MARK(X) 7.74/3.01 MARK(pairs) -> ACTIVE(pairs) 7.74/3.01 ACTIVE(pairs) -> MARK(cons(0, incr(odds))) 7.74/3.01 MARK(odds) -> ACTIVE(odds) 7.74/3.01 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.01 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.74/3.01 MARK(s(X)) -> MARK(X) 7.74/3.01 MARK(head(X)) -> ACTIVE(head(mark(X))) 7.74/3.01 MARK(head(X)) -> MARK(X) 7.74/3.01 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 7.74/3.01 MARK(tail(X)) -> MARK(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (45) MRRProof (EQUIVALENT) 7.74/3.01 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 7.74/3.01 7.74/3.01 Strictly oriented dependency pairs: 7.74/3.01 7.74/3.01 MARK(head(X)) -> MARK(X) 7.74/3.01 7.74/3.01 7.74/3.01 Used ordering: Polynomial interpretation [POLO]: 7.74/3.01 7.74/3.01 POL(0) = 0 7.74/3.01 POL(ACTIVE(x_1)) = x_1 7.74/3.01 POL(MARK(x_1)) = x_1 7.74/3.01 POL(active(x_1)) = x_1 7.74/3.01 POL(cons(x_1, x_2)) = x_1 + x_2 7.74/3.01 POL(head(x_1)) = 2 + 2*x_1 7.74/3.01 POL(incr(x_1)) = 2*x_1 7.74/3.01 POL(mark(x_1)) = x_1 7.74/3.01 POL(nats) = 0 7.74/3.01 POL(odds) = 0 7.74/3.01 POL(pairs) = 0 7.74/3.01 POL(s(x_1)) = x_1 7.74/3.01 POL(tail(x_1)) = 2*x_1 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (46) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.01 MARK(cons(X1, X2)) -> MARK(X1) 7.74/3.01 MARK(nats) -> ACTIVE(nats) 7.74/3.01 ACTIVE(nats) -> MARK(cons(0, incr(nats))) 7.74/3.01 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 7.74/3.01 MARK(incr(X)) -> MARK(X) 7.74/3.01 MARK(pairs) -> ACTIVE(pairs) 7.74/3.01 ACTIVE(pairs) -> MARK(cons(0, incr(odds))) 7.74/3.01 MARK(odds) -> ACTIVE(odds) 7.74/3.01 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.01 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.74/3.01 MARK(s(X)) -> MARK(X) 7.74/3.01 MARK(head(X)) -> ACTIVE(head(mark(X))) 7.74/3.01 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 7.74/3.01 MARK(tail(X)) -> MARK(X) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (47) MRRProof (EQUIVALENT) 7.74/3.01 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 7.74/3.01 7.74/3.01 Strictly oriented dependency pairs: 7.74/3.01 7.74/3.01 MARK(tail(X)) -> MARK(X) 7.74/3.01 7.74/3.01 7.74/3.01 Used ordering: Polynomial interpretation [POLO]: 7.74/3.01 7.74/3.01 POL(0) = 0 7.74/3.01 POL(ACTIVE(x_1)) = 2*x_1 7.74/3.01 POL(MARK(x_1)) = 2*x_1 7.74/3.01 POL(active(x_1)) = x_1 7.74/3.01 POL(cons(x_1, x_2)) = 2*x_1 + x_2 7.74/3.01 POL(head(x_1)) = x_1 7.74/3.01 POL(incr(x_1)) = 2*x_1 7.74/3.01 POL(mark(x_1)) = x_1 7.74/3.01 POL(nats) = 0 7.74/3.01 POL(odds) = 0 7.74/3.01 POL(pairs) = 0 7.74/3.01 POL(s(x_1)) = x_1 7.74/3.01 POL(tail(x_1)) = 2 + 2*x_1 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (48) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.01 MARK(cons(X1, X2)) -> MARK(X1) 7.74/3.01 MARK(nats) -> ACTIVE(nats) 7.74/3.01 ACTIVE(nats) -> MARK(cons(0, incr(nats))) 7.74/3.01 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 7.74/3.01 MARK(incr(X)) -> MARK(X) 7.74/3.01 MARK(pairs) -> ACTIVE(pairs) 7.74/3.01 ACTIVE(pairs) -> MARK(cons(0, incr(odds))) 7.74/3.01 MARK(odds) -> ACTIVE(odds) 7.74/3.01 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.01 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.74/3.01 MARK(s(X)) -> MARK(X) 7.74/3.01 MARK(head(X)) -> ACTIVE(head(mark(X))) 7.74/3.01 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.01 s(active(x0)) 7.74/3.01 head(mark(x0)) 7.74/3.01 head(active(x0)) 7.74/3.01 tail(mark(x0)) 7.74/3.01 tail(active(x0)) 7.74/3.01 7.74/3.01 We have to consider all minimal (P,Q,R)-chains. 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (49) QDPOrderProof (EQUIVALENT) 7.74/3.01 We use the reduction pair processor [LPAR04,JAR06]. 7.74/3.01 7.74/3.01 7.74/3.01 The following pairs can be oriented strictly and are deleted. 7.74/3.01 7.74/3.01 MARK(cons(X1, X2)) -> MARK(X1) 7.74/3.01 ACTIVE(nats) -> MARK(cons(0, incr(nats))) 7.74/3.01 ACTIVE(pairs) -> MARK(cons(0, incr(odds))) 7.74/3.01 The remaining pairs can at least be oriented weakly. 7.74/3.01 Used ordering: Combined order from the following AFS and order. 7.74/3.01 MARK(x1) = x1 7.74/3.01 7.74/3.01 cons(x1, x2) = cons(x1) 7.74/3.01 7.74/3.01 ACTIVE(x1) = x1 7.74/3.01 7.74/3.01 mark(x1) = x1 7.74/3.01 7.74/3.01 incr(x1) = x1 7.74/3.01 7.74/3.01 s(x1) = x1 7.74/3.01 7.74/3.01 nats = nats 7.74/3.01 7.74/3.01 0 = 0 7.74/3.01 7.74/3.01 pairs = pairs 7.74/3.01 7.74/3.01 odds = odds 7.74/3.01 7.74/3.01 head(x1) = head 7.74/3.01 7.74/3.01 tail(x1) = x1 7.74/3.01 7.74/3.01 active(x1) = x1 7.74/3.01 7.74/3.01 7.74/3.01 Recursive path order with status [RPO]. 7.74/3.01 Quasi-Precedence: nats > cons_1 7.74/3.01 nats > 0 7.74/3.01 [pairs, odds] > cons_1 7.74/3.01 [pairs, odds] > 0 7.74/3.01 7.74/3.01 Status: cons_1: [1] 7.74/3.01 nats: multiset status 7.74/3.01 0: multiset status 7.74/3.01 pairs: multiset status 7.74/3.01 odds: multiset status 7.74/3.01 head: multiset status 7.74/3.01 7.74/3.01 7.74/3.01 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 7.74/3.01 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 7.74/3.01 7.74/3.01 ---------------------------------------- 7.74/3.01 7.74/3.01 (50) 7.74/3.01 Obligation: 7.74/3.01 Q DP problem: 7.74/3.01 The TRS P consists of the following rules: 7.74/3.01 7.74/3.01 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.01 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.01 MARK(nats) -> ACTIVE(nats) 7.74/3.01 MARK(incr(X)) -> ACTIVE(incr(mark(X))) 7.74/3.01 MARK(incr(X)) -> MARK(X) 7.74/3.01 MARK(pairs) -> ACTIVE(pairs) 7.74/3.01 MARK(odds) -> ACTIVE(odds) 7.74/3.01 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.01 MARK(s(X)) -> ACTIVE(s(mark(X))) 7.74/3.01 MARK(s(X)) -> MARK(X) 7.74/3.01 MARK(head(X)) -> ACTIVE(head(mark(X))) 7.74/3.01 MARK(tail(X)) -> ACTIVE(tail(mark(X))) 7.74/3.01 7.74/3.01 The TRS R consists of the following rules: 7.74/3.01 7.74/3.01 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.01 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.01 active(odds) -> mark(incr(pairs)) 7.74/3.01 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.01 mark(nats) -> active(nats) 7.74/3.01 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.01 mark(0) -> active(0) 7.74/3.01 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.01 mark(pairs) -> active(pairs) 7.74/3.01 mark(odds) -> active(odds) 7.74/3.01 mark(s(X)) -> active(s(mark(X))) 7.74/3.01 mark(head(X)) -> active(head(mark(X))) 7.74/3.01 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.01 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.01 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.01 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.01 incr(mark(X)) -> incr(X) 7.74/3.01 incr(active(X)) -> incr(X) 7.74/3.01 s(mark(X)) -> s(X) 7.74/3.01 s(active(X)) -> s(X) 7.74/3.01 head(mark(X)) -> head(X) 7.74/3.01 head(active(X)) -> head(X) 7.74/3.01 tail(mark(X)) -> tail(X) 7.74/3.01 tail(active(X)) -> tail(X) 7.74/3.01 7.74/3.01 The set Q consists of the following terms: 7.74/3.01 7.74/3.01 active(nats) 7.74/3.01 active(pairs) 7.74/3.01 active(odds) 7.74/3.01 active(incr(cons(x0, x1))) 7.74/3.01 active(head(cons(x0, x1))) 7.74/3.01 active(tail(cons(x0, x1))) 7.74/3.01 mark(nats) 7.74/3.01 mark(cons(x0, x1)) 7.74/3.01 mark(0) 7.74/3.01 mark(incr(x0)) 7.74/3.01 mark(pairs) 7.74/3.01 mark(odds) 7.74/3.01 mark(s(x0)) 7.74/3.01 mark(head(x0)) 7.74/3.01 mark(tail(x0)) 7.74/3.01 cons(mark(x0), x1) 7.74/3.01 cons(x0, mark(x1)) 7.74/3.01 cons(active(x0), x1) 7.74/3.01 cons(x0, active(x1)) 7.74/3.01 incr(mark(x0)) 7.74/3.01 incr(active(x0)) 7.74/3.01 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 head(mark(x0)) 7.74/3.02 head(active(x0)) 7.74/3.02 tail(mark(x0)) 7.74/3.02 tail(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (51) DependencyGraphProof (EQUIVALENT) 7.74/3.02 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 6 less nodes. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (52) 7.74/3.02 Complex Obligation (AND) 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (53) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.02 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.02 7.74/3.02 The TRS R consists of the following rules: 7.74/3.02 7.74/3.02 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.02 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.02 active(odds) -> mark(incr(pairs)) 7.74/3.02 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.02 mark(nats) -> active(nats) 7.74/3.02 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.02 mark(0) -> active(0) 7.74/3.02 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.02 mark(pairs) -> active(pairs) 7.74/3.02 mark(odds) -> active(odds) 7.74/3.02 mark(s(X)) -> active(s(mark(X))) 7.74/3.02 mark(head(X)) -> active(head(mark(X))) 7.74/3.02 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.02 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.02 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.02 incr(mark(X)) -> incr(X) 7.74/3.02 incr(active(X)) -> incr(X) 7.74/3.02 s(mark(X)) -> s(X) 7.74/3.02 s(active(X)) -> s(X) 7.74/3.02 head(mark(X)) -> head(X) 7.74/3.02 head(active(X)) -> head(X) 7.74/3.02 tail(mark(X)) -> tail(X) 7.74/3.02 tail(active(X)) -> tail(X) 7.74/3.02 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 active(nats) 7.74/3.02 active(pairs) 7.74/3.02 active(odds) 7.74/3.02 active(incr(cons(x0, x1))) 7.74/3.02 active(head(cons(x0, x1))) 7.74/3.02 active(tail(cons(x0, x1))) 7.74/3.02 mark(nats) 7.74/3.02 mark(cons(x0, x1)) 7.74/3.02 mark(0) 7.74/3.02 mark(incr(x0)) 7.74/3.02 mark(pairs) 7.74/3.02 mark(odds) 7.74/3.02 mark(s(x0)) 7.74/3.02 mark(head(x0)) 7.74/3.02 mark(tail(x0)) 7.74/3.02 cons(mark(x0), x1) 7.74/3.02 cons(x0, mark(x1)) 7.74/3.02 cons(active(x0), x1) 7.74/3.02 cons(x0, active(x1)) 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 head(mark(x0)) 7.74/3.02 head(active(x0)) 7.74/3.02 tail(mark(x0)) 7.74/3.02 tail(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (54) QDPOrderProof (EQUIVALENT) 7.74/3.02 We use the reduction pair processor [LPAR04,JAR06]. 7.74/3.02 7.74/3.02 7.74/3.02 The following pairs can be oriented strictly and are deleted. 7.74/3.02 7.74/3.02 ACTIVE(incr(cons(X, XS))) -> MARK(cons(s(X), incr(XS))) 7.74/3.02 MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2)) 7.74/3.02 The remaining pairs can at least be oriented weakly. 7.74/3.02 Used ordering: Combined order from the following AFS and order. 7.74/3.02 ACTIVE(x1) = x1 7.74/3.02 7.74/3.02 incr(x1) = incr 7.74/3.02 7.74/3.02 cons(x1, x2) = cons 7.74/3.02 7.74/3.02 MARK(x1) = MARK 7.74/3.02 7.74/3.02 7.74/3.02 Knuth-Bendix order [KBO] with precedence:MARK > cons 7.74/3.02 7.74/3.02 and weight map: 7.74/3.02 7.74/3.02 MARK=1 7.74/3.02 incr=2 7.74/3.02 cons=1 7.74/3.02 7.74/3.02 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 7.74/3.02 7.74/3.02 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.02 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.02 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (55) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 P is empty. 7.74/3.02 The TRS R consists of the following rules: 7.74/3.02 7.74/3.02 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.02 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.02 active(odds) -> mark(incr(pairs)) 7.74/3.02 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.02 mark(nats) -> active(nats) 7.74/3.02 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.02 mark(0) -> active(0) 7.74/3.02 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.02 mark(pairs) -> active(pairs) 7.74/3.02 mark(odds) -> active(odds) 7.74/3.02 mark(s(X)) -> active(s(mark(X))) 7.74/3.02 mark(head(X)) -> active(head(mark(X))) 7.74/3.02 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.02 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.02 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.02 incr(mark(X)) -> incr(X) 7.74/3.02 incr(active(X)) -> incr(X) 7.74/3.02 s(mark(X)) -> s(X) 7.74/3.02 s(active(X)) -> s(X) 7.74/3.02 head(mark(X)) -> head(X) 7.74/3.02 head(active(X)) -> head(X) 7.74/3.02 tail(mark(X)) -> tail(X) 7.74/3.02 tail(active(X)) -> tail(X) 7.74/3.02 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 active(nats) 7.74/3.02 active(pairs) 7.74/3.02 active(odds) 7.74/3.02 active(incr(cons(x0, x1))) 7.74/3.02 active(head(cons(x0, x1))) 7.74/3.02 active(tail(cons(x0, x1))) 7.74/3.02 mark(nats) 7.74/3.02 mark(cons(x0, x1)) 7.74/3.02 mark(0) 7.74/3.02 mark(incr(x0)) 7.74/3.02 mark(pairs) 7.74/3.02 mark(odds) 7.74/3.02 mark(s(x0)) 7.74/3.02 mark(head(x0)) 7.74/3.02 mark(tail(x0)) 7.74/3.02 cons(mark(x0), x1) 7.74/3.02 cons(x0, mark(x1)) 7.74/3.02 cons(active(x0), x1) 7.74/3.02 cons(x0, active(x1)) 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 head(mark(x0)) 7.74/3.02 head(active(x0)) 7.74/3.02 tail(mark(x0)) 7.74/3.02 tail(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (56) PisEmptyProof (EQUIVALENT) 7.74/3.02 The TRS P is empty. Hence, there is no (P,Q,R) chain. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (57) 7.74/3.02 YES 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (58) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 MARK(odds) -> ACTIVE(odds) 7.74/3.02 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.02 MARK(incr(X)) -> MARK(X) 7.74/3.02 MARK(s(X)) -> MARK(X) 7.74/3.02 7.74/3.02 The TRS R consists of the following rules: 7.74/3.02 7.74/3.02 active(nats) -> mark(cons(0, incr(nats))) 7.74/3.02 active(pairs) -> mark(cons(0, incr(odds))) 7.74/3.02 active(odds) -> mark(incr(pairs)) 7.74/3.02 active(incr(cons(X, XS))) -> mark(cons(s(X), incr(XS))) 7.74/3.02 mark(nats) -> active(nats) 7.74/3.02 mark(cons(X1, X2)) -> active(cons(mark(X1), X2)) 7.74/3.02 mark(0) -> active(0) 7.74/3.02 mark(incr(X)) -> active(incr(mark(X))) 7.74/3.02 mark(pairs) -> active(pairs) 7.74/3.02 mark(odds) -> active(odds) 7.74/3.02 mark(s(X)) -> active(s(mark(X))) 7.74/3.02 mark(head(X)) -> active(head(mark(X))) 7.74/3.02 mark(tail(X)) -> active(tail(mark(X))) 7.74/3.02 cons(mark(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, mark(X2)) -> cons(X1, X2) 7.74/3.02 cons(active(X1), X2) -> cons(X1, X2) 7.74/3.02 cons(X1, active(X2)) -> cons(X1, X2) 7.74/3.02 incr(mark(X)) -> incr(X) 7.74/3.02 incr(active(X)) -> incr(X) 7.74/3.02 s(mark(X)) -> s(X) 7.74/3.02 s(active(X)) -> s(X) 7.74/3.02 head(mark(X)) -> head(X) 7.74/3.02 head(active(X)) -> head(X) 7.74/3.02 tail(mark(X)) -> tail(X) 7.74/3.02 tail(active(X)) -> tail(X) 7.74/3.02 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 active(nats) 7.74/3.02 active(pairs) 7.74/3.02 active(odds) 7.74/3.02 active(incr(cons(x0, x1))) 7.74/3.02 active(head(cons(x0, x1))) 7.74/3.02 active(tail(cons(x0, x1))) 7.74/3.02 mark(nats) 7.74/3.02 mark(cons(x0, x1)) 7.74/3.02 mark(0) 7.74/3.02 mark(incr(x0)) 7.74/3.02 mark(pairs) 7.74/3.02 mark(odds) 7.74/3.02 mark(s(x0)) 7.74/3.02 mark(head(x0)) 7.74/3.02 mark(tail(x0)) 7.74/3.02 cons(mark(x0), x1) 7.74/3.02 cons(x0, mark(x1)) 7.74/3.02 cons(active(x0), x1) 7.74/3.02 cons(x0, active(x1)) 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 head(mark(x0)) 7.74/3.02 head(active(x0)) 7.74/3.02 tail(mark(x0)) 7.74/3.02 tail(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (59) UsableRulesProof (EQUIVALENT) 7.74/3.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. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (60) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 MARK(odds) -> ACTIVE(odds) 7.74/3.02 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.02 MARK(incr(X)) -> MARK(X) 7.74/3.02 MARK(s(X)) -> MARK(X) 7.74/3.02 7.74/3.02 R is empty. 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 active(nats) 7.74/3.02 active(pairs) 7.74/3.02 active(odds) 7.74/3.02 active(incr(cons(x0, x1))) 7.74/3.02 active(head(cons(x0, x1))) 7.74/3.02 active(tail(cons(x0, x1))) 7.74/3.02 mark(nats) 7.74/3.02 mark(cons(x0, x1)) 7.74/3.02 mark(0) 7.74/3.02 mark(incr(x0)) 7.74/3.02 mark(pairs) 7.74/3.02 mark(odds) 7.74/3.02 mark(s(x0)) 7.74/3.02 mark(head(x0)) 7.74/3.02 mark(tail(x0)) 7.74/3.02 cons(mark(x0), x1) 7.74/3.02 cons(x0, mark(x1)) 7.74/3.02 cons(active(x0), x1) 7.74/3.02 cons(x0, active(x1)) 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 head(mark(x0)) 7.74/3.02 head(active(x0)) 7.74/3.02 tail(mark(x0)) 7.74/3.02 tail(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (61) QReductionProof (EQUIVALENT) 7.74/3.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.02 7.74/3.02 active(nats) 7.74/3.02 active(pairs) 7.74/3.02 active(odds) 7.74/3.02 active(incr(cons(x0, x1))) 7.74/3.02 active(head(cons(x0, x1))) 7.74/3.02 active(tail(cons(x0, x1))) 7.74/3.02 mark(nats) 7.74/3.02 mark(cons(x0, x1)) 7.74/3.02 mark(0) 7.74/3.02 mark(incr(x0)) 7.74/3.02 mark(pairs) 7.74/3.02 mark(odds) 7.74/3.02 mark(s(x0)) 7.74/3.02 mark(head(x0)) 7.74/3.02 mark(tail(x0)) 7.74/3.02 cons(mark(x0), x1) 7.74/3.02 cons(x0, mark(x1)) 7.74/3.02 cons(active(x0), x1) 7.74/3.02 cons(x0, active(x1)) 7.74/3.02 head(mark(x0)) 7.74/3.02 head(active(x0)) 7.74/3.02 tail(mark(x0)) 7.74/3.02 tail(active(x0)) 7.74/3.02 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (62) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 MARK(odds) -> ACTIVE(odds) 7.74/3.02 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.02 MARK(incr(X)) -> MARK(X) 7.74/3.02 MARK(s(X)) -> MARK(X) 7.74/3.02 7.74/3.02 R is empty. 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (63) UsableRulesReductionPairsProof (EQUIVALENT) 7.74/3.02 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. 7.74/3.02 7.74/3.02 The following dependency pairs can be deleted: 7.74/3.02 7.74/3.02 MARK(s(X)) -> MARK(X) 7.74/3.02 No rules are removed from R. 7.74/3.02 7.74/3.02 Used ordering: POLO with Polynomial interpretation [POLO]: 7.74/3.02 7.74/3.02 POL(ACTIVE(x_1)) = x_1 7.74/3.02 POL(MARK(x_1)) = x_1 7.74/3.02 POL(incr(x_1)) = x_1 7.74/3.02 POL(odds) = 0 7.74/3.02 POL(pairs) = 0 7.74/3.02 POL(s(x_1)) = 2*x_1 7.74/3.02 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (64) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 MARK(odds) -> ACTIVE(odds) 7.74/3.02 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.02 MARK(incr(X)) -> MARK(X) 7.74/3.02 7.74/3.02 R is empty. 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (65) QReductionProof (EQUIVALENT) 7.74/3.02 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 7.74/3.02 7.74/3.02 s(mark(x0)) 7.74/3.02 s(active(x0)) 7.74/3.02 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (66) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 MARK(odds) -> ACTIVE(odds) 7.74/3.02 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.02 MARK(incr(X)) -> MARK(X) 7.74/3.02 7.74/3.02 R is empty. 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (67) MRRProof (EQUIVALENT) 7.74/3.02 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 7.74/3.02 7.74/3.02 Strictly oriented dependency pairs: 7.74/3.02 7.74/3.02 MARK(odds) -> ACTIVE(odds) 7.74/3.02 ACTIVE(odds) -> MARK(incr(pairs)) 7.74/3.02 7.74/3.02 7.74/3.02 Used ordering: Polynomial interpretation [POLO]: 7.74/3.02 7.74/3.02 POL(ACTIVE(x_1)) = 1 + x_1 7.74/3.02 POL(MARK(x_1)) = 2*x_1 7.74/3.02 POL(incr(x_1)) = 2*x_1 7.74/3.02 POL(odds) = 2 7.74/3.02 POL(pairs) = 0 7.74/3.02 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (68) 7.74/3.02 Obligation: 7.74/3.02 Q DP problem: 7.74/3.02 The TRS P consists of the following rules: 7.74/3.02 7.74/3.02 MARK(incr(X)) -> MARK(X) 7.74/3.02 7.74/3.02 R is empty. 7.74/3.02 The set Q consists of the following terms: 7.74/3.02 7.74/3.02 incr(mark(x0)) 7.74/3.02 incr(active(x0)) 7.74/3.02 7.74/3.02 We have to consider all minimal (P,Q,R)-chains. 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (69) QDPSizeChangeProof (EQUIVALENT) 7.74/3.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. 7.74/3.02 7.74/3.02 From the DPs we obtained the following set of size-change graphs: 7.74/3.02 *MARK(incr(X)) -> MARK(X) 7.74/3.02 The graph contains the following edges 1 > 1 7.74/3.02 7.74/3.02 7.74/3.02 ---------------------------------------- 7.74/3.02 7.74/3.02 (70) 7.74/3.02 YES 7.99/3.05 EOF