14.16/7.75 NO 14.16/7.77 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 14.16/7.77 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.16/7.77 14.16/7.77 14.16/7.77 Termination w.r.t. Q of the given QTRS could be disproven: 14.16/7.77 14.16/7.77 (0) QTRS 14.16/7.77 (1) QTRSRRRProof [EQUIVALENT, 64 ms] 14.16/7.77 (2) QTRS 14.16/7.77 (3) QTRSRRRProof [EQUIVALENT, 20 ms] 14.16/7.77 (4) QTRS 14.16/7.77 (5) DependencyPairsProof [EQUIVALENT, 0 ms] 14.16/7.77 (6) QDP 14.16/7.77 (7) DependencyGraphProof [EQUIVALENT, 5 ms] 14.16/7.77 (8) QDP 14.16/7.77 (9) MRRProof [EQUIVALENT, 0 ms] 14.16/7.77 (10) QDP 14.16/7.77 (11) MRRProof [EQUIVALENT, 21 ms] 14.16/7.77 (12) QDP 14.16/7.77 (13) DependencyGraphProof [EQUIVALENT, 0 ms] 14.16/7.77 (14) AND 14.16/7.77 (15) QDP 14.16/7.77 (16) UsableRulesProof [EQUIVALENT, 0 ms] 14.16/7.77 (17) QDP 14.16/7.77 (18) QReductionProof [EQUIVALENT, 0 ms] 14.16/7.77 (19) QDP 14.16/7.77 (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] 14.16/7.77 (21) YES 14.16/7.77 (22) QDP 14.16/7.77 (23) TransformationProof [EQUIVALENT, 0 ms] 14.16/7.77 (24) QDP 14.16/7.77 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 14.16/7.77 (26) QDP 14.16/7.77 (27) TransformationProof [EQUIVALENT, 0 ms] 14.16/7.77 (28) QDP 14.16/7.77 (29) DependencyGraphProof [EQUIVALENT, 0 ms] 14.16/7.77 (30) AND 14.16/7.77 (31) QDP 14.16/7.77 (32) UsableRulesProof [EQUIVALENT, 0 ms] 14.16/7.77 (33) QDP 14.16/7.77 (34) QReductionProof [EQUIVALENT, 0 ms] 14.16/7.77 (35) QDP 14.16/7.77 (36) TransformationProof [EQUIVALENT, 0 ms] 14.16/7.77 (37) QDP 14.16/7.77 (38) NonTerminationLoopProof [COMPLETE, 0 ms] 14.16/7.77 (39) NO 14.16/7.77 (40) QDP 14.16/7.77 (41) MRRProof [EQUIVALENT, 16 ms] 14.16/7.77 (42) QDP 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (0) 14.16/7.77 Obligation: 14.16/7.77 Q restricted rewrite system: 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__and(tt, X) -> mark(X) 14.16/7.77 a__length(nil) -> 0 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(0, IL) -> nil 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (1) QTRSRRRProof (EQUIVALENT) 14.16/7.77 Used ordering: 14.16/7.77 Polynomial interpretation [POLO]: 14.16/7.77 14.16/7.77 POL(0) = 0 14.16/7.77 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(a__length(x_1)) = x_1 14.16/7.77 POL(a__take(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(a__zeros) = 0 14.16/7.77 POL(and(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(cons(x_1, x_2)) = x_1 + x_2 14.16/7.77 POL(length(x_1)) = x_1 14.16/7.77 POL(mark(x_1)) = x_1 14.16/7.77 POL(nil) = 0 14.16/7.77 POL(s(x_1)) = x_1 14.16/7.77 POL(take(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(tt) = 1 14.16/7.77 POL(zeros) = 0 14.16/7.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 14.16/7.77 14.16/7.77 a__and(tt, X) -> mark(X) 14.16/7.77 14.16/7.77 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (2) 14.16/7.77 Obligation: 14.16/7.77 Q restricted rewrite system: 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(nil) -> 0 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(0, IL) -> nil 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (3) QTRSRRRProof (EQUIVALENT) 14.16/7.77 Used ordering: 14.16/7.77 Polynomial interpretation [POLO]: 14.16/7.77 14.16/7.77 POL(0) = 0 14.16/7.77 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(a__length(x_1)) = 2*x_1 14.16/7.77 POL(a__take(x_1, x_2)) = 2 + x_1 + x_2 14.16/7.77 POL(a__zeros) = 0 14.16/7.77 POL(and(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(cons(x_1, x_2)) = x_1 + x_2 14.16/7.77 POL(length(x_1)) = 2*x_1 14.16/7.77 POL(mark(x_1)) = x_1 14.16/7.77 POL(nil) = 1 14.16/7.77 POL(s(x_1)) = x_1 14.16/7.77 POL(take(x_1, x_2)) = 2 + x_1 + x_2 14.16/7.77 POL(tt) = 0 14.16/7.77 POL(zeros) = 0 14.16/7.77 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 14.16/7.77 14.16/7.77 a__length(nil) -> 0 14.16/7.77 a__take(0, IL) -> nil 14.16/7.77 14.16/7.77 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (4) 14.16/7.77 Obligation: 14.16/7.77 Q restricted rewrite system: 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (5) DependencyPairsProof (EQUIVALENT) 14.16/7.77 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (6) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 14.16/7.77 A__LENGTH(cons(N, L)) -> MARK(L) 14.16/7.77 A__TAKE(s(M), cons(N, IL)) -> MARK(N) 14.16/7.77 MARK(zeros) -> A__ZEROS 14.16/7.77 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 14.16/7.77 MARK(and(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(length(X)) -> A__LENGTH(mark(X)) 14.16/7.77 MARK(length(X)) -> MARK(X) 14.16/7.77 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X2) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (7) DependencyGraphProof (EQUIVALENT) 14.16/7.77 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (8) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 A__LENGTH(cons(N, L)) -> MARK(L) 14.16/7.77 MARK(and(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(length(X)) -> A__LENGTH(mark(X)) 14.16/7.77 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 14.16/7.77 MARK(length(X)) -> MARK(X) 14.16/7.77 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 14.16/7.77 A__TAKE(s(M), cons(N, IL)) -> MARK(N) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X2) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (9) MRRProof (EQUIVALENT) 14.16/7.77 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. 14.16/7.77 14.16/7.77 Strictly oriented dependency pairs: 14.16/7.77 14.16/7.77 MARK(and(X1, X2)) -> MARK(X1) 14.16/7.77 14.16/7.77 14.16/7.77 Used ordering: Polynomial interpretation [POLO]: 14.16/7.77 14.16/7.77 POL(0) = 0 14.16/7.77 POL(A__LENGTH(x_1)) = x_1 14.16/7.77 POL(A__TAKE(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(MARK(x_1)) = x_1 14.16/7.77 POL(a__and(x_1, x_2)) = 1 + x_1 + 2*x_2 14.16/7.77 POL(a__length(x_1)) = x_1 14.16/7.77 POL(a__take(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(a__zeros) = 0 14.16/7.77 POL(and(x_1, x_2)) = 1 + x_1 + 2*x_2 14.16/7.77 POL(cons(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(length(x_1)) = x_1 14.16/7.77 POL(mark(x_1)) = x_1 14.16/7.77 POL(nil) = 0 14.16/7.77 POL(s(x_1)) = 2*x_1 14.16/7.77 POL(take(x_1, x_2)) = x_1 + 2*x_2 14.16/7.77 POL(tt) = 0 14.16/7.77 POL(zeros) = 0 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (10) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 A__LENGTH(cons(N, L)) -> MARK(L) 14.16/7.77 MARK(length(X)) -> A__LENGTH(mark(X)) 14.16/7.77 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 14.16/7.77 MARK(length(X)) -> MARK(X) 14.16/7.77 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 14.16/7.77 A__TAKE(s(M), cons(N, IL)) -> MARK(N) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X2) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (11) MRRProof (EQUIVALENT) 14.16/7.77 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. 14.16/7.77 14.16/7.77 Strictly oriented dependency pairs: 14.16/7.77 14.16/7.77 A__LENGTH(cons(N, L)) -> MARK(L) 14.16/7.77 MARK(length(X)) -> A__LENGTH(mark(X)) 14.16/7.77 MARK(length(X)) -> MARK(X) 14.16/7.77 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 14.16/7.77 A__TAKE(s(M), cons(N, IL)) -> MARK(N) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(take(X1, X2)) -> MARK(X2) 14.16/7.77 14.16/7.77 14.16/7.77 Used ordering: Polynomial interpretation [POLO]: 14.16/7.77 14.16/7.77 POL(0) = 0 14.16/7.77 POL(A__LENGTH(x_1)) = 2 + 2*x_1 14.16/7.77 POL(A__TAKE(x_1, x_2)) = 1 + x_1 + 2*x_2 14.16/7.77 POL(MARK(x_1)) = 2*x_1 14.16/7.77 POL(a__and(x_1, x_2)) = 2*x_1 + 2*x_2 14.16/7.77 POL(a__length(x_1)) = 2 + x_1 14.16/7.77 POL(a__take(x_1, x_2)) = 1 + x_1 + 2*x_2 14.16/7.77 POL(a__zeros) = 0 14.16/7.77 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 14.16/7.77 POL(cons(x_1, x_2)) = x_1 + x_2 14.16/7.77 POL(length(x_1)) = 2 + x_1 14.16/7.77 POL(mark(x_1)) = x_1 14.16/7.77 POL(nil) = 0 14.16/7.77 POL(s(x_1)) = x_1 14.16/7.77 POL(take(x_1, x_2)) = 1 + x_1 + 2*x_2 14.16/7.77 POL(tt) = 0 14.16/7.77 POL(zeros) = 0 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (12) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (13) DependencyGraphProof (EQUIVALENT) 14.16/7.77 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (14) 14.16/7.77 Complex Obligation (AND) 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (15) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 14.16/7.77 The TRS R consists of the following rules: 14.16/7.77 14.16/7.77 a__zeros -> cons(0, zeros) 14.16/7.77 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.77 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.77 mark(zeros) -> a__zeros 14.16/7.77 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.77 mark(length(X)) -> a__length(mark(X)) 14.16/7.77 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.77 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.77 mark(0) -> 0 14.16/7.77 mark(tt) -> tt 14.16/7.77 mark(nil) -> nil 14.16/7.77 mark(s(X)) -> s(mark(X)) 14.16/7.77 a__zeros -> zeros 14.16/7.77 a__and(X1, X2) -> and(X1, X2) 14.16/7.77 a__length(X) -> length(X) 14.16/7.77 a__take(X1, X2) -> take(X1, X2) 14.16/7.77 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (16) UsableRulesProof (EQUIVALENT) 14.16/7.77 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. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (17) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 14.16/7.77 R is empty. 14.16/7.77 The set Q consists of the following terms: 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (18) QReductionProof (EQUIVALENT) 14.16/7.77 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 14.16/7.77 14.16/7.77 a__zeros 14.16/7.77 mark(zeros) 14.16/7.77 mark(and(x0, x1)) 14.16/7.77 mark(length(x0)) 14.16/7.77 mark(take(x0, x1)) 14.16/7.77 mark(cons(x0, x1)) 14.16/7.77 mark(0) 14.16/7.77 mark(tt) 14.16/7.77 mark(nil) 14.16/7.77 mark(s(x0)) 14.16/7.77 a__and(x0, x1) 14.16/7.77 a__length(x0) 14.16/7.77 a__take(x0, x1) 14.16/7.77 14.16/7.77 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (19) 14.16/7.77 Obligation: 14.16/7.77 Q DP problem: 14.16/7.77 The TRS P consists of the following rules: 14.16/7.77 14.16/7.77 MARK(s(X)) -> MARK(X) 14.16/7.77 MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.77 14.16/7.77 R is empty. 14.16/7.77 Q is empty. 14.16/7.77 We have to consider all minimal (P,Q,R)-chains. 14.16/7.77 ---------------------------------------- 14.16/7.77 14.16/7.77 (20) QDPSizeChangeProof (EQUIVALENT) 14.16/7.77 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. 14.16/7.78 14.16/7.78 From the DPs we obtained the following set of size-change graphs: 14.16/7.78 *MARK(s(X)) -> MARK(X) 14.16/7.78 The graph contains the following edges 1 > 1 14.16/7.78 14.16/7.78 14.16/7.78 *MARK(cons(X1, X2)) -> MARK(X1) 14.16/7.78 The graph contains the following edges 1 > 1 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (21) 14.16/7.78 YES 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (22) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (23) TransformationProof (EQUIVALENT) 14.16/7.78 By narrowing [LPAR04] the rule A__LENGTH(cons(N, L)) -> A__LENGTH(mark(L)) at position [0] we obtained the following new rules [LPAR04]: 14.16/7.78 14.16/7.78 (A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros),A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros)) 14.16/7.78 (A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1)),A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1))) 14.16/7.78 (A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0))),A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0)))) 14.16/7.78 (A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1))),A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1)))) 14.16/7.78 (A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1)),A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1))) 14.16/7.78 (A__LENGTH(cons(y0, 0)) -> A__LENGTH(0),A__LENGTH(cons(y0, 0)) -> A__LENGTH(0)) 14.16/7.78 (A__LENGTH(cons(y0, tt)) -> A__LENGTH(tt),A__LENGTH(cons(y0, tt)) -> A__LENGTH(tt)) 14.16/7.78 (A__LENGTH(cons(y0, nil)) -> A__LENGTH(nil),A__LENGTH(cons(y0, nil)) -> A__LENGTH(nil)) 14.16/7.78 (A__LENGTH(cons(y0, s(x0))) -> A__LENGTH(s(mark(x0))),A__LENGTH(cons(y0, s(x0))) -> A__LENGTH(s(mark(x0)))) 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (24) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) 14.16/7.78 A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0))) 14.16/7.78 A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1))) 14.16/7.78 A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, 0)) -> A__LENGTH(0) 14.16/7.78 A__LENGTH(cons(y0, tt)) -> A__LENGTH(tt) 14.16/7.78 A__LENGTH(cons(y0, nil)) -> A__LENGTH(nil) 14.16/7.78 A__LENGTH(cons(y0, s(x0))) -> A__LENGTH(s(mark(x0))) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (25) DependencyGraphProof (EQUIVALENT) 14.16/7.78 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (26) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) 14.16/7.78 A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0))) 14.16/7.78 A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1))) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (27) TransformationProof (EQUIVALENT) 14.16/7.78 By narrowing [LPAR04] the rule A__LENGTH(cons(y0, zeros)) -> A__LENGTH(a__zeros) at position [0] we obtained the following new rules [LPAR04]: 14.16/7.78 14.16/7.78 (A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)),A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros))) 14.16/7.78 (A__LENGTH(cons(y0, zeros)) -> A__LENGTH(zeros),A__LENGTH(cons(y0, zeros)) -> A__LENGTH(zeros)) 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (28) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0))) 14.16/7.78 A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1))) 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(zeros) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (29) DependencyGraphProof (EQUIVALENT) 14.16/7.78 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (30) 14.16/7.78 Complex Obligation (AND) 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (31) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (32) UsableRulesProof (EQUIVALENT) 14.16/7.78 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. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (33) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 14.16/7.78 14.16/7.78 R is empty. 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (34) QReductionProof (EQUIVALENT) 14.16/7.78 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (35) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) 14.16/7.78 14.16/7.78 R is empty. 14.16/7.78 Q is empty. 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (36) TransformationProof (EQUIVALENT) 14.16/7.78 By instantiating [LPAR04] the rule A__LENGTH(cons(y0, zeros)) -> A__LENGTH(cons(0, zeros)) we obtained the following new rules [LPAR04]: 14.16/7.78 14.16/7.78 (A__LENGTH(cons(0, zeros)) -> A__LENGTH(cons(0, zeros)),A__LENGTH(cons(0, zeros)) -> A__LENGTH(cons(0, zeros))) 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (37) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(0, zeros)) -> A__LENGTH(cons(0, zeros)) 14.16/7.78 14.16/7.78 R is empty. 14.16/7.78 Q is empty. 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (38) NonTerminationLoopProof (COMPLETE) 14.16/7.78 We used the non-termination processor [FROCOS05] to show that the DP problem is infinite. 14.16/7.78 Found a loop by semiunifying a rule from P directly. 14.16/7.78 14.16/7.78 s = A__LENGTH(cons(0, zeros)) evaluates to t =A__LENGTH(cons(0, zeros)) 14.16/7.78 14.16/7.78 Thus s starts an infinite chain as s semiunifies with t with the following substitutions: 14.16/7.78 * Matcher: [ ] 14.16/7.78 * Semiunifier: [ ] 14.16/7.78 14.16/7.78 -------------------------------------------------------------------------------- 14.16/7.78 Rewriting sequence 14.16/7.78 14.16/7.78 The DP semiunifies directly so there is only one rewrite step from A__LENGTH(cons(0, zeros)) to A__LENGTH(cons(0, zeros)). 14.16/7.78 14.16/7.78 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (39) 14.16/7.78 NO 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (40) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1)) 14.16/7.78 A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0))) 14.16/7.78 A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1))) 14.16/7.78 A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1)) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (41) MRRProof (EQUIVALENT) 14.16/7.78 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. 14.16/7.78 14.16/7.78 Strictly oriented dependency pairs: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, and(x0, x1))) -> A__LENGTH(a__and(mark(x0), x1)) 14.16/7.78 14.16/7.78 14.16/7.78 Used ordering: Polynomial interpretation [POLO]: 14.16/7.78 14.16/7.78 POL(0) = 0 14.16/7.78 POL(A__LENGTH(x_1)) = x_1 14.16/7.78 POL(a__and(x_1, x_2)) = 2 + 2*x_1 + x_2 14.16/7.78 POL(a__length(x_1)) = x_1 14.16/7.78 POL(a__take(x_1, x_2)) = 2*x_1 + 2*x_2 14.16/7.78 POL(a__zeros) = 0 14.16/7.78 POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2 14.16/7.78 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 14.16/7.78 POL(length(x_1)) = x_1 14.16/7.78 POL(mark(x_1)) = x_1 14.16/7.78 POL(nil) = 0 14.16/7.78 POL(s(x_1)) = 2*x_1 14.16/7.78 POL(take(x_1, x_2)) = 2*x_1 + 2*x_2 14.16/7.78 POL(tt) = 0 14.16/7.78 POL(zeros) = 0 14.16/7.78 14.16/7.78 14.16/7.78 ---------------------------------------- 14.16/7.78 14.16/7.78 (42) 14.16/7.78 Obligation: 14.16/7.78 Q DP problem: 14.16/7.78 The TRS P consists of the following rules: 14.16/7.78 14.16/7.78 A__LENGTH(cons(y0, length(x0))) -> A__LENGTH(a__length(mark(x0))) 14.16/7.78 A__LENGTH(cons(y0, take(x0, x1))) -> A__LENGTH(a__take(mark(x0), mark(x1))) 14.16/7.78 A__LENGTH(cons(y0, cons(x0, x1))) -> A__LENGTH(cons(mark(x0), x1)) 14.16/7.78 14.16/7.78 The TRS R consists of the following rules: 14.16/7.78 14.16/7.78 a__zeros -> cons(0, zeros) 14.16/7.78 a__length(cons(N, L)) -> s(a__length(mark(L))) 14.16/7.78 a__take(s(M), cons(N, IL)) -> cons(mark(N), take(M, IL)) 14.16/7.78 mark(zeros) -> a__zeros 14.16/7.78 mark(and(X1, X2)) -> a__and(mark(X1), X2) 14.16/7.78 mark(length(X)) -> a__length(mark(X)) 14.16/7.78 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.16/7.78 mark(cons(X1, X2)) -> cons(mark(X1), X2) 14.16/7.78 mark(0) -> 0 14.16/7.78 mark(tt) -> tt 14.16/7.78 mark(nil) -> nil 14.16/7.78 mark(s(X)) -> s(mark(X)) 14.16/7.78 a__zeros -> zeros 14.16/7.78 a__and(X1, X2) -> and(X1, X2) 14.16/7.78 a__length(X) -> length(X) 14.16/7.78 a__take(X1, X2) -> take(X1, X2) 14.16/7.78 14.16/7.78 The set Q consists of the following terms: 14.16/7.78 14.16/7.78 a__zeros 14.16/7.78 mark(zeros) 14.16/7.78 mark(and(x0, x1)) 14.16/7.78 mark(length(x0)) 14.16/7.78 mark(take(x0, x1)) 14.16/7.78 mark(cons(x0, x1)) 14.16/7.78 mark(0) 14.16/7.78 mark(tt) 14.16/7.78 mark(nil) 14.16/7.78 mark(s(x0)) 14.16/7.78 a__and(x0, x1) 14.16/7.78 a__length(x0) 14.16/7.78 a__take(x0, x1) 14.16/7.78 14.16/7.78 We have to consider all minimal (P,Q,R)-chains. 14.35/7.82 EOF