9.34/3.51 NO 10.04/3.53 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 10.04/3.53 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 10.04/3.53 10.04/3.53 10.04/3.53 Termination w.r.t. Q of the given QTRS could be disproven: 10.04/3.53 10.04/3.53 (0) QTRS 10.04/3.53 (1) QTRSRRRProof [EQUIVALENT, 61 ms] 10.04/3.53 (2) QTRS 10.04/3.53 (3) QTRSRRRProof [EQUIVALENT, 9 ms] 10.04/3.53 (4) QTRS 10.04/3.53 (5) QTRSRRRProof [EQUIVALENT, 17 ms] 10.04/3.53 (6) QTRS 10.04/3.53 (7) QTRSRRRProof [EQUIVALENT, 0 ms] 10.04/3.53 (8) QTRS 10.04/3.53 (9) QTRSRRRProof [EQUIVALENT, 0 ms] 10.04/3.53 (10) QTRS 10.04/3.53 (11) QTRSRRRProof [EQUIVALENT, 9 ms] 10.04/3.53 (12) QTRS 10.04/3.53 (13) QTRSRRRProof [EQUIVALENT, 0 ms] 10.04/3.53 (14) QTRS 10.04/3.53 (15) QTRSRRRProof [EQUIVALENT, 7 ms] 10.04/3.53 (16) QTRS 10.04/3.53 (17) QTRSRRRProof [EQUIVALENT, 0 ms] 10.04/3.53 (18) QTRS 10.04/3.53 (19) QTRSRRRProof [EQUIVALENT, 10 ms] 10.04/3.53 (20) QTRS 10.04/3.53 (21) DependencyPairsProof [EQUIVALENT, 0 ms] 10.04/3.53 (22) QDP 10.04/3.53 (23) DependencyGraphProof [EQUIVALENT, 0 ms] 10.04/3.53 (24) AND 10.04/3.53 (25) QDP 10.04/3.53 (26) UsableRulesProof [EQUIVALENT, 0 ms] 10.04/3.53 (27) QDP 10.04/3.53 (28) QReductionProof [EQUIVALENT, 0 ms] 10.04/3.53 (29) QDP 10.04/3.53 (30) QDPSizeChangeProof [EQUIVALENT, 0 ms] 10.04/3.53 (31) YES 10.04/3.53 (32) QDP 10.04/3.53 (33) UsableRulesProof [EQUIVALENT, 0 ms] 10.04/3.53 (34) QDP 10.04/3.53 (35) QReductionProof [EQUIVALENT, 0 ms] 10.04/3.53 (36) QDP 10.04/3.53 (37) MRRProof [EQUIVALENT, 0 ms] 10.04/3.53 (38) QDP 10.04/3.53 (39) TransformationProof [EQUIVALENT, 0 ms] 10.04/3.53 (40) QDP 10.04/3.53 (41) UsableRulesProof [EQUIVALENT, 0 ms] 10.04/3.53 (42) QDP 10.04/3.53 (43) QReductionProof [EQUIVALENT, 0 ms] 10.04/3.53 (44) QDP 10.04/3.53 (45) TransformationProof [EQUIVALENT, 0 ms] 10.04/3.53 (46) QDP 10.04/3.53 (47) UsableRulesProof [EQUIVALENT, 0 ms] 10.04/3.53 (48) QDP 10.04/3.53 (49) QReductionProof [EQUIVALENT, 0 ms] 10.04/3.53 (50) QDP 10.04/3.53 (51) TransformationProof [EQUIVALENT, 0 ms] 10.04/3.53 (52) QDP 10.04/3.53 (53) TransformationProof [EQUIVALENT, 0 ms] 10.04/3.53 (54) QDP 10.04/3.53 (55) NonTerminationLoopProof [COMPLETE, 5 ms] 10.04/3.53 (56) NO 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (0) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(nil) -> 0 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 mark(length(X)) -> a__length(mark(X)) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(tt) -> tt 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 mark(nil) -> nil 10.04/3.53 a__zeros -> zeros 10.04/3.53 a__U11(X1, X2) -> U11(X1, X2) 10.04/3.53 a__U12(X1, X2) -> U12(X1, X2) 10.04/3.53 a__length(X) -> length(X) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (1) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(length(x_1)) = x_1 10.04/3.53 POL(mark(x_1)) = x_1 10.04/3.53 POL(nil) = 2 10.04/3.53 POL(s(x_1)) = 2*x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 a__length(nil) -> 0 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (2) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 mark(length(X)) -> a__length(mark(X)) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(tt) -> tt 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 mark(nil) -> nil 10.04/3.53 a__zeros -> zeros 10.04/3.53 a__U11(X1, X2) -> U11(X1, X2) 10.04/3.53 a__U12(X1, X2) -> U12(X1, X2) 10.04/3.53 a__length(X) -> length(X) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (3) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(U12(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(length(x_1)) = x_1 10.04/3.53 POL(mark(x_1)) = 2*x_1 10.04/3.53 POL(nil) = 1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 mark(nil) -> nil 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (4) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 mark(length(X)) -> a__length(mark(X)) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(tt) -> tt 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> zeros 10.04/3.53 a__U11(X1, X2) -> U11(X1, X2) 10.04/3.53 a__U12(X1, X2) -> U12(X1, X2) 10.04/3.53 a__length(X) -> length(X) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (5) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = 1 + x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(length(x_1)) = 1 + x_1 10.04/3.53 POL(mark(x_1)) = 2*x_1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 1 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 mark(length(X)) -> a__length(mark(X)) 10.04/3.53 mark(tt) -> tt 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (6) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> zeros 10.04/3.53 a__U11(X1, X2) -> U11(X1, X2) 10.04/3.53 a__U12(X1, X2) -> U12(X1, X2) 10.04/3.53 a__length(X) -> length(X) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (7) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = 1 + x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(length(x_1)) = x_1 10.04/3.53 POL(mark(x_1)) = x_1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 1 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 a__length(X) -> length(X) 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (8) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> zeros 10.04/3.53 a__U11(X1, X2) -> U11(X1, X2) 10.04/3.53 a__U12(X1, X2) -> U12(X1, X2) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (9) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 10.04/3.53 POL(U12(x_1, x_2)) = 1 + x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = 2 + x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = 2 + x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = 2*x_1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 a__U11(X1, X2) -> U11(X1, X2) 10.04/3.53 a__U12(X1, X2) -> U12(X1, X2) 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (10) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> zeros 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (11) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(U12(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = x_1 10.04/3.53 POL(s(x_1)) = 2*x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 mark(U12(X1, X2)) -> a__U12(mark(X1), X2) 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (12) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> zeros 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (13) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 10.04/3.53 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = x_1 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = x_1 10.04/3.53 POL(s(x_1)) = 2*x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (14) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> zeros 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (15) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(a__U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = x_1 10.04/3.53 POL(a__zeros) = 2 10.04/3.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = 2*x_1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 1 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 a__zeros -> zeros 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (16) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(0) -> 0 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (17) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(a__U11(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = 2*x_1 10.04/3.53 POL(a__zeros) = 2 10.04/3.53 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = 2 + x_1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 2 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 mark(0) -> 0 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (18) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (19) QTRSRRRProof (EQUIVALENT) 10.04/3.53 Used ordering: 10.04/3.53 Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(a__U11(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 10.04/3.53 POL(a__U12(x_1, x_2)) = 1 + x_1 + 2*x_2 10.04/3.53 POL(a__length(x_1)) = x_1 10.04/3.53 POL(a__zeros) = 1 10.04/3.53 POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = 1 + 2*x_1 10.04/3.53 POL(s(x_1)) = x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 10.04/3.53 10.04/3.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (20) 10.04/3.53 Obligation: 10.04/3.53 Q restricted rewrite system: 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (21) DependencyPairsProof (EQUIVALENT) 10.04/3.53 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (22) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, L) -> A__LENGTH(mark(L)) 10.04/3.53 A__U12(tt, L) -> MARK(L) 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 MARK(zeros) -> A__ZEROS 10.04/3.53 MARK(s(X)) -> MARK(X) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (23) DependencyGraphProof (EQUIVALENT) 10.04/3.53 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (24) 10.04/3.53 Complex Obligation (AND) 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (25) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 MARK(s(X)) -> MARK(X) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (26) UsableRulesProof (EQUIVALENT) 10.04/3.53 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.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (27) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 MARK(s(X)) -> MARK(X) 10.04/3.53 10.04/3.53 R is empty. 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (28) QReductionProof (EQUIVALENT) 10.04/3.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (29) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 MARK(s(X)) -> MARK(X) 10.04/3.53 10.04/3.53 R is empty. 10.04/3.53 Q is empty. 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (30) QDPSizeChangeProof (EQUIVALENT) 10.04/3.53 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.04/3.53 10.04/3.53 From the DPs we obtained the following set of size-change graphs: 10.04/3.53 *MARK(s(X)) -> MARK(X) 10.04/3.53 The graph contains the following edges 1 > 1 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (31) 10.04/3.53 YES 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (32) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__U12(tt, L) -> A__LENGTH(mark(L)) 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 a__U11(tt, L) -> a__U12(tt, L) 10.04/3.53 a__U12(tt, L) -> s(a__length(mark(L))) 10.04/3.53 a__length(cons(N, L)) -> a__U11(tt, L) 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (33) UsableRulesProof (EQUIVALENT) 10.04/3.53 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.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (34) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__U12(tt, L) -> A__LENGTH(mark(L)) 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (35) QReductionProof (EQUIVALENT) 10.04/3.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.04/3.53 10.04/3.53 a__U11(x0, x1) 10.04/3.53 a__U12(x0, x1) 10.04/3.53 a__length(x0) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (36) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__U12(tt, L) -> A__LENGTH(mark(L)) 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (37) MRRProof (EQUIVALENT) 10.04/3.53 By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented. 10.04/3.53 10.04/3.53 10.04/3.53 Strictly oriented rules of the TRS R: 10.04/3.53 10.04/3.53 mark(s(X)) -> s(mark(X)) 10.04/3.53 10.04/3.53 Used ordering: Polynomial interpretation [POLO]: 10.04/3.53 10.04/3.53 POL(0) = 0 10.04/3.53 POL(A__LENGTH(x_1)) = x_1 10.04/3.53 POL(A__U11(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(A__U12(x_1, x_2)) = 2*x_1 + 2*x_2 10.04/3.53 POL(a__zeros) = 0 10.04/3.53 POL(cons(x_1, x_2)) = x_1 + 2*x_2 10.04/3.53 POL(mark(x_1)) = 2*x_1 10.04/3.53 POL(s(x_1)) = 2 + 2*x_1 10.04/3.53 POL(tt) = 0 10.04/3.53 POL(zeros) = 0 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (38) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__U12(tt, L) -> A__LENGTH(mark(L)) 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (39) TransformationProof (EQUIVALENT) 10.04/3.53 By narrowing [LPAR04] the rule A__U12(tt, L) -> A__LENGTH(mark(L)) at position [0] we obtained the following new rules [LPAR04]: 10.04/3.53 10.04/3.53 (A__U12(tt, zeros) -> A__LENGTH(a__zeros),A__U12(tt, zeros) -> A__LENGTH(a__zeros)) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (40) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, zeros) -> A__LENGTH(a__zeros) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 mark(zeros) -> a__zeros 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (41) UsableRulesProof (EQUIVALENT) 10.04/3.53 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.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (42) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, zeros) -> A__LENGTH(a__zeros) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (43) QReductionProof (EQUIVALENT) 10.04/3.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.04/3.53 10.04/3.53 mark(zeros) 10.04/3.53 mark(U11(x0, x1)) 10.04/3.53 mark(U12(x0, x1)) 10.04/3.53 mark(length(x0)) 10.04/3.53 mark(cons(x0, x1)) 10.04/3.53 mark(0) 10.04/3.53 mark(tt) 10.04/3.53 mark(s(x0)) 10.04/3.53 mark(nil) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (44) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, zeros) -> A__LENGTH(a__zeros) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (45) TransformationProof (EQUIVALENT) 10.04/3.53 By rewriting [LPAR04] the rule A__U12(tt, zeros) -> A__LENGTH(a__zeros) at position [0] we obtained the following new rules [LPAR04]: 10.04/3.53 10.04/3.53 (A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)),A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros))) 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (46) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.53 10.04/3.53 The TRS R consists of the following rules: 10.04/3.53 10.04/3.53 a__zeros -> cons(0, zeros) 10.04/3.53 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (47) UsableRulesProof (EQUIVALENT) 10.04/3.53 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.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (48) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.53 10.04/3.53 R is empty. 10.04/3.53 The set Q consists of the following terms: 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (49) QReductionProof (EQUIVALENT) 10.04/3.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 10.04/3.53 10.04/3.53 a__zeros 10.04/3.53 10.04/3.53 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (50) 10.04/3.53 Obligation: 10.04/3.53 Q DP problem: 10.04/3.53 The TRS P consists of the following rules: 10.04/3.53 10.04/3.53 A__LENGTH(cons(N, L)) -> A__U11(tt, L) 10.04/3.53 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.53 A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.53 10.04/3.53 R is empty. 10.04/3.53 Q is empty. 10.04/3.53 We have to consider all minimal (P,Q,R)-chains. 10.04/3.53 ---------------------------------------- 10.04/3.53 10.04/3.53 (51) TransformationProof (EQUIVALENT) 10.04/3.53 By instantiating [LPAR04] the rule A__LENGTH(cons(N, L)) -> A__U11(tt, L) we obtained the following new rules [LPAR04]: 10.04/3.54 10.04/3.54 (A__LENGTH(cons(0, zeros)) -> A__U11(tt, zeros),A__LENGTH(cons(0, zeros)) -> A__U11(tt, zeros)) 10.04/3.54 10.04/3.54 10.04/3.54 ---------------------------------------- 10.04/3.54 10.04/3.54 (52) 10.04/3.54 Obligation: 10.04/3.54 Q DP problem: 10.04/3.54 The TRS P consists of the following rules: 10.04/3.54 10.04/3.54 A__U11(tt, L) -> A__U12(tt, L) 10.04/3.54 A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.54 A__LENGTH(cons(0, zeros)) -> A__U11(tt, zeros) 10.04/3.54 10.04/3.54 R is empty. 10.04/3.54 Q is empty. 10.04/3.54 We have to consider all minimal (P,Q,R)-chains. 10.04/3.54 ---------------------------------------- 10.04/3.54 10.04/3.54 (53) TransformationProof (EQUIVALENT) 10.04/3.54 By instantiating [LPAR04] the rule A__U11(tt, L) -> A__U12(tt, L) we obtained the following new rules [LPAR04]: 10.04/3.54 10.04/3.54 (A__U11(tt, zeros) -> A__U12(tt, zeros),A__U11(tt, zeros) -> A__U12(tt, zeros)) 10.04/3.54 10.04/3.54 10.04/3.54 ---------------------------------------- 10.04/3.54 10.04/3.54 (54) 10.04/3.54 Obligation: 10.04/3.54 Q DP problem: 10.04/3.54 The TRS P consists of the following rules: 10.04/3.54 10.04/3.54 A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.54 A__LENGTH(cons(0, zeros)) -> A__U11(tt, zeros) 10.04/3.54 A__U11(tt, zeros) -> A__U12(tt, zeros) 10.04/3.54 10.04/3.54 R is empty. 10.04/3.54 Q is empty. 10.04/3.54 We have to consider all minimal (P,Q,R)-chains. 10.04/3.54 ---------------------------------------- 10.04/3.54 10.04/3.54 (55) NonTerminationLoopProof (COMPLETE) 10.04/3.54 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 10.04/3.54 Found a loop by narrowing to the left: 10.04/3.54 10.04/3.54 s = A__LENGTH(cons(0, zeros)) evaluates to t =A__LENGTH(cons(0, zeros)) 10.04/3.54 10.04/3.54 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 10.04/3.54 * Matcher: [ ] 10.04/3.54 * Semiunifier: [ ] 10.04/3.54 10.04/3.54 -------------------------------------------------------------------------------- 10.04/3.54 Rewriting sequence 10.04/3.54 10.04/3.54 A__LENGTH(cons(0, zeros)) -> A__U11(tt, zeros) 10.04/3.54 with rule A__LENGTH(cons(0, zeros)) -> A__U11(tt, zeros) at position [] and matcher [ ] 10.04/3.54 10.04/3.54 A__U11(tt, zeros) -> A__U12(tt, zeros) 10.04/3.54 with rule A__U11(tt, zeros) -> A__U12(tt, zeros) at position [] and matcher [ ] 10.04/3.54 10.04/3.54 A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.54 with rule A__U12(tt, zeros) -> A__LENGTH(cons(0, zeros)) 10.04/3.54 10.04/3.54 Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence 10.04/3.54 10.04/3.54 10.04/3.54 All these steps are and every following step will be a correct step w.r.t to Q. 10.04/3.54 10.04/3.54 10.04/3.54 10.04/3.54 10.04/3.54 ---------------------------------------- 10.04/3.54 10.04/3.54 (56) 10.04/3.54 NO 10.04/3.57 EOF