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