8.51/3.26 YES 8.51/3.29 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 8.51/3.29 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 8.51/3.29 8.51/3.29 8.51/3.29 Termination w.r.t. Q of the given QTRS could be proven: 8.51/3.29 8.51/3.29 (0) QTRS 8.51/3.29 (1) QTRSRRRProof [EQUIVALENT, 116 ms] 8.51/3.29 (2) QTRS 8.51/3.29 (3) QTRSRRRProof [EQUIVALENT, 31 ms] 8.51/3.29 (4) QTRS 8.51/3.29 (5) QTRSRRRProof [EQUIVALENT, 20 ms] 8.51/3.29 (6) QTRS 8.51/3.29 (7) QTRSRRRProof [EQUIVALENT, 18 ms] 8.51/3.29 (8) QTRS 8.51/3.29 (9) DependencyPairsProof [EQUIVALENT, 2 ms] 8.51/3.29 (10) QDP 8.51/3.29 (11) DependencyGraphProof [EQUIVALENT, 0 ms] 8.51/3.29 (12) QDP 8.51/3.29 (13) MRRProof [EQUIVALENT, 21 ms] 8.51/3.29 (14) QDP 8.51/3.29 (15) DependencyGraphProof [EQUIVALENT, 0 ms] 8.51/3.29 (16) QDP 8.51/3.29 (17) MRRProof [EQUIVALENT, 19 ms] 8.51/3.29 (18) QDP 8.51/3.29 (19) DependencyGraphProof [EQUIVALENT, 0 ms] 8.51/3.29 (20) QDP 8.51/3.29 (21) MRRProof [EQUIVALENT, 18 ms] 8.51/3.29 (22) QDP 8.51/3.29 (23) MRRProof [EQUIVALENT, 20 ms] 8.51/3.29 (24) QDP 8.51/3.29 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 8.51/3.29 (26) QDP 8.51/3.29 (27) MRRProof [EQUIVALENT, 38 ms] 8.51/3.29 (28) QDP 8.51/3.29 (29) DependencyGraphProof [EQUIVALENT, 0 ms] 8.51/3.29 (30) QDP 8.51/3.29 (31) QDPOrderProof [EQUIVALENT, 48 ms] 8.51/3.29 (32) QDP 8.51/3.29 (33) DependencyGraphProof [EQUIVALENT, 0 ms] 8.51/3.29 (34) QDP 8.51/3.29 (35) UsableRulesProof [EQUIVALENT, 0 ms] 8.51/3.29 (36) QDP 8.51/3.29 (37) QReductionProof [EQUIVALENT, 0 ms] 8.51/3.29 (38) QDP 8.51/3.29 (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] 8.51/3.29 (40) YES 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (0) 8.51/3.29 Obligation: 8.51/3.29 Q restricted rewrite system: 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(0, XS) -> nil 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(nil, XS) -> nil 8.51/3.29 a__zip(X, nil) -> nil 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__tail(cons(X, XS)) -> mark(XS) 8.51/3.29 a__repItems(nil) -> nil 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (1) QTRSRRRProof (EQUIVALENT) 8.51/3.29 Used ordering: 8.51/3.29 Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(a__incr(x_1)) = 2*x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 1 + 2*x_1 8.51/3.29 POL(a__tail(x_1)) = 2*x_1 8.51/3.29 POL(a__take(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = 2*x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 1 + 2*x_1 8.51/3.29 POL(s(x_1)) = x_1 8.51/3.29 POL(tail(x_1)) = 2*x_1 8.51/3.29 POL(take(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(zip(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.51/3.29 8.51/3.29 a__repItems(nil) -> nil 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (2) 8.51/3.29 Obligation: 8.51/3.29 Q restricted rewrite system: 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(0, XS) -> nil 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(nil, XS) -> nil 8.51/3.29 a__zip(X, nil) -> nil 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__tail(cons(X, XS)) -> mark(XS) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (3) QTRSRRRProof (EQUIVALENT) 8.51/3.29 Used ordering: 8.51/3.29 Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(a__incr(x_1)) = x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2*x_1 8.51/3.29 POL(a__tail(x_1)) = 1 + x_1 8.51/3.29 POL(a__take(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2*x_1 8.51/3.29 POL(s(x_1)) = x_1 8.51/3.29 POL(tail(x_1)) = 1 + x_1 8.51/3.29 POL(take(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(zip(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.51/3.29 8.51/3.29 a__tail(cons(X, XS)) -> mark(XS) 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (4) 8.51/3.29 Obligation: 8.51/3.29 Q restricted rewrite system: 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(0, XS) -> nil 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(nil, XS) -> nil 8.51/3.29 a__zip(X, nil) -> nil 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (5) QTRSRRRProof (EQUIVALENT) 8.51/3.29 Used ordering: 8.51/3.29 Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(a__incr(x_1)) = 2*x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2*x_1 8.51/3.29 POL(a__tail(x_1)) = x_1 8.51/3.29 POL(a__take(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = 2 + 2*x_1 + x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = 2*x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2*x_1 8.51/3.29 POL(s(x_1)) = 2*x_1 8.51/3.29 POL(tail(x_1)) = x_1 8.51/3.29 POL(take(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(zip(x_1, x_2)) = 2 + 2*x_1 + x_2 8.51/3.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.51/3.29 8.51/3.29 a__zip(nil, XS) -> nil 8.51/3.29 a__zip(X, nil) -> nil 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (6) 8.51/3.29 Obligation: 8.51/3.29 Q restricted rewrite system: 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(0, XS) -> nil 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (7) QTRSRRRProof (EQUIVALENT) 8.51/3.29 Used ordering: 8.51/3.29 Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(a__incr(x_1)) = x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2*x_1 8.51/3.29 POL(a__tail(x_1)) = x_1 8.51/3.29 POL(a__take(x_1, x_2)) = 1 + x_1 + x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2*x_1 8.51/3.29 POL(s(x_1)) = x_1 8.51/3.29 POL(tail(x_1)) = x_1 8.51/3.29 POL(take(x_1, x_2)) = 1 + x_1 + x_2 8.51/3.29 POL(zip(x_1, x_2)) = x_1 + 2*x_2 8.51/3.29 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 8.51/3.29 8.51/3.29 a__take(0, XS) -> nil 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (8) 8.51/3.29 Obligation: 8.51/3.29 Q restricted rewrite system: 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (9) DependencyPairsProof (EQUIVALENT) 8.51/3.29 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (10) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 A__ODDNS -> A__PAIRNS 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 A__ZIP(cons(X, XS), cons(Y, YS)) -> MARK(X) 8.51/3.29 A__ZIP(cons(X, XS), cons(Y, YS)) -> MARK(Y) 8.51/3.29 A__REPITEMS(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(pairNs) -> A__PAIRNS 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(zip(X1, X2)) -> A__ZIP(mark(X1), mark(X2)) 8.51/3.29 MARK(zip(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(zip(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(tail(X)) -> A__TAIL(mark(X)) 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> A__REPITEMS(mark(X)) 8.51/3.29 MARK(repItems(X)) -> MARK(X) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (11) DependencyGraphProof (EQUIVALENT) 8.51/3.29 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (12) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(zip(X1, X2)) -> A__ZIP(mark(X1), mark(X2)) 8.51/3.29 A__ZIP(cons(X, XS), cons(Y, YS)) -> MARK(X) 8.51/3.29 MARK(zip(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(zip(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> A__REPITEMS(mark(X)) 8.51/3.29 A__REPITEMS(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> MARK(X) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 A__ZIP(cons(X, XS), cons(Y, YS)) -> MARK(Y) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (13) MRRProof (EQUIVALENT) 8.51/3.29 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. 8.51/3.29 8.51/3.29 Strictly oriented dependency pairs: 8.51/3.29 8.51/3.29 MARK(zip(X1, X2)) -> A__ZIP(mark(X1), mark(X2)) 8.51/3.29 MARK(zip(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(zip(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 8.51/3.29 Used ordering: Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(A__INCR(x_1)) = x_1 8.51/3.29 POL(A__ODDNS) = 0 8.51/3.29 POL(A__REPITEMS(x_1)) = 2*x_1 8.51/3.29 POL(A__TAKE(x_1, x_2)) = 2*x_1 + 2*x_2 8.51/3.29 POL(A__ZIP(x_1, x_2)) = 2*x_1 + 2*x_2 8.51/3.29 POL(MARK(x_1)) = x_1 8.51/3.29 POL(a__incr(x_1)) = 2*x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2*x_1 8.51/3.29 POL(a__tail(x_1)) = x_1 8.51/3.29 POL(a__take(x_1, x_2)) = 2*x_1 + 2*x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = 2*x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2*x_1 8.51/3.29 POL(s(x_1)) = 2*x_1 8.51/3.29 POL(tail(x_1)) = x_1 8.51/3.29 POL(take(x_1, x_2)) = 2*x_1 + 2*x_2 8.51/3.29 POL(zip(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (14) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 A__ZIP(cons(X, XS), cons(Y, YS)) -> MARK(X) 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> A__REPITEMS(mark(X)) 8.51/3.29 A__REPITEMS(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> MARK(X) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 A__ZIP(cons(X, XS), cons(Y, YS)) -> MARK(Y) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (15) DependencyGraphProof (EQUIVALENT) 8.51/3.29 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (16) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> A__REPITEMS(mark(X)) 8.51/3.29 A__REPITEMS(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(repItems(X)) -> MARK(X) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (17) MRRProof (EQUIVALENT) 8.51/3.29 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. 8.51/3.29 8.51/3.29 Strictly oriented dependency pairs: 8.51/3.29 8.51/3.29 MARK(repItems(X)) -> A__REPITEMS(mark(X)) 8.51/3.29 MARK(repItems(X)) -> MARK(X) 8.51/3.29 8.51/3.29 8.51/3.29 Used ordering: Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(A__INCR(x_1)) = x_1 8.51/3.29 POL(A__ODDNS) = 0 8.51/3.29 POL(A__REPITEMS(x_1)) = 2*x_1 8.51/3.29 POL(A__TAKE(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(MARK(x_1)) = x_1 8.51/3.29 POL(a__incr(x_1)) = 2*x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2 + 2*x_1 8.51/3.29 POL(a__tail(x_1)) = 2*x_1 8.51/3.29 POL(a__take(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(cons(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(incr(x_1)) = 2*x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2 + 2*x_1 8.51/3.29 POL(s(x_1)) = x_1 8.51/3.29 POL(tail(x_1)) = 2*x_1 8.51/3.29 POL(take(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(zip(x_1, x_2)) = x_1 + x_2 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (18) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 A__REPITEMS(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (19) DependencyGraphProof (EQUIVALENT) 8.51/3.29 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (20) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (21) MRRProof (EQUIVALENT) 8.51/3.29 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. 8.51/3.29 8.51/3.29 Strictly oriented dependency pairs: 8.51/3.29 8.51/3.29 MARK(tail(X)) -> MARK(X) 8.51/3.29 8.51/3.29 8.51/3.29 Used ordering: Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(A__INCR(x_1)) = x_1 8.51/3.29 POL(A__ODDNS) = 0 8.51/3.29 POL(A__TAKE(x_1, x_2)) = 2*x_1 + x_2 8.51/3.29 POL(MARK(x_1)) = x_1 8.51/3.29 POL(a__incr(x_1)) = x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2*x_1 8.51/3.29 POL(a__tail(x_1)) = 1 + 2*x_1 8.51/3.29 POL(a__take(x_1, x_2)) = 2*x_1 + 2*x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2*x_1 8.51/3.29 POL(s(x_1)) = x_1 8.51/3.29 POL(tail(x_1)) = 1 + 2*x_1 8.51/3.29 POL(take(x_1, x_2)) = 2*x_1 + 2*x_2 8.51/3.29 POL(zip(x_1, x_2)) = x_1 + x_2 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (22) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.51/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.51/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.51/3.29 mark(0) -> 0 8.51/3.29 mark(s(X)) -> s(mark(X)) 8.51/3.29 mark(nil) -> nil 8.51/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.51/3.29 a__pairNs -> pairNs 8.51/3.29 a__incr(X) -> incr(X) 8.51/3.29 a__oddNs -> oddNs 8.51/3.29 a__take(X1, X2) -> take(X1, X2) 8.51/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.51/3.29 a__tail(X) -> tail(X) 8.51/3.29 a__repItems(X) -> repItems(X) 8.51/3.29 8.51/3.29 The set Q consists of the following terms: 8.51/3.29 8.51/3.29 a__pairNs 8.51/3.29 a__oddNs 8.51/3.29 mark(pairNs) 8.51/3.29 mark(incr(x0)) 8.51/3.29 mark(oddNs) 8.51/3.29 mark(take(x0, x1)) 8.51/3.29 mark(zip(x0, x1)) 8.51/3.29 mark(tail(x0)) 8.51/3.29 mark(repItems(x0)) 8.51/3.29 mark(cons(x0, x1)) 8.51/3.29 mark(0) 8.51/3.29 mark(s(x0)) 8.51/3.29 mark(nil) 8.51/3.29 mark(pair(x0, x1)) 8.51/3.29 a__incr(x0) 8.51/3.29 a__take(x0, x1) 8.51/3.29 a__zip(x0, x1) 8.51/3.29 a__tail(x0) 8.51/3.29 a__repItems(x0) 8.51/3.29 8.51/3.29 We have to consider all minimal (P,Q,R)-chains. 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (23) MRRProof (EQUIVALENT) 8.51/3.29 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. 8.51/3.29 8.51/3.29 Strictly oriented dependency pairs: 8.51/3.29 8.51/3.29 A__TAKE(s(N), cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(take(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 8.51/3.29 Used ordering: Polynomial interpretation [POLO]: 8.51/3.29 8.51/3.29 POL(0) = 0 8.51/3.29 POL(A__INCR(x_1)) = 2*x_1 8.51/3.29 POL(A__ODDNS) = 0 8.51/3.29 POL(A__TAKE(x_1, x_2)) = 1 + x_1 + 2*x_2 8.51/3.29 POL(MARK(x_1)) = x_1 8.51/3.29 POL(a__incr(x_1)) = 2*x_1 8.51/3.29 POL(a__oddNs) = 0 8.51/3.29 POL(a__pairNs) = 0 8.51/3.29 POL(a__repItems(x_1)) = 2*x_1 8.51/3.29 POL(a__tail(x_1)) = 2*x_1 8.51/3.29 POL(a__take(x_1, x_2)) = 1 + x_1 + 2*x_2 8.51/3.29 POL(a__zip(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(cons(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(incr(x_1)) = 2*x_1 8.51/3.29 POL(mark(x_1)) = x_1 8.51/3.29 POL(nil) = 0 8.51/3.29 POL(oddNs) = 0 8.51/3.29 POL(pair(x_1, x_2)) = x_1 + x_2 8.51/3.29 POL(pairNs) = 0 8.51/3.29 POL(repItems(x_1)) = 2*x_1 8.51/3.29 POL(s(x_1)) = 2*x_1 8.51/3.29 POL(tail(x_1)) = 2*x_1 8.51/3.29 POL(take(x_1, x_2)) = 1 + x_1 + 2*x_2 8.51/3.29 POL(zip(x_1, x_2)) = x_1 + x_2 8.51/3.29 8.51/3.29 8.51/3.29 ---------------------------------------- 8.51/3.29 8.51/3.29 (24) 8.51/3.29 Obligation: 8.51/3.29 Q DP problem: 8.51/3.29 The TRS P consists of the following rules: 8.51/3.29 8.51/3.29 A__INCR(cons(X, XS)) -> MARK(X) 8.51/3.29 MARK(incr(X)) -> A__INCR(mark(X)) 8.51/3.29 MARK(incr(X)) -> MARK(X) 8.51/3.29 MARK(oddNs) -> A__ODDNS 8.51/3.29 A__ODDNS -> A__INCR(a__pairNs) 8.51/3.29 MARK(take(X1, X2)) -> A__TAKE(mark(X1), mark(X2)) 8.51/3.29 MARK(cons(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(s(X)) -> MARK(X) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X1) 8.51/3.29 MARK(pair(X1, X2)) -> MARK(X2) 8.51/3.29 8.51/3.29 The TRS R consists of the following rules: 8.51/3.29 8.51/3.29 a__pairNs -> cons(0, incr(oddNs)) 8.51/3.29 a__oddNs -> a__incr(a__pairNs) 8.51/3.29 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.51/3.29 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.51/3.29 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.51/3.29 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.51/3.29 mark(pairNs) -> a__pairNs 8.51/3.29 mark(incr(X)) -> a__incr(mark(X)) 8.51/3.29 mark(oddNs) -> a__oddNs 8.51/3.29 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.51/3.29 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.51/3.29 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.29 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.29 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.29 mark(0) -> 0 8.80/3.29 mark(s(X)) -> s(mark(X)) 8.80/3.29 mark(nil) -> nil 8.80/3.29 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.29 a__pairNs -> pairNs 8.80/3.29 a__incr(X) -> incr(X) 8.80/3.29 a__oddNs -> oddNs 8.80/3.29 a__take(X1, X2) -> take(X1, X2) 8.80/3.29 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.29 a__tail(X) -> tail(X) 8.80/3.29 a__repItems(X) -> repItems(X) 8.80/3.29 8.80/3.29 The set Q consists of the following terms: 8.80/3.29 8.80/3.29 a__pairNs 8.80/3.29 a__oddNs 8.80/3.29 mark(pairNs) 8.80/3.29 mark(incr(x0)) 8.80/3.29 mark(oddNs) 8.80/3.29 mark(take(x0, x1)) 8.80/3.29 mark(zip(x0, x1)) 8.80/3.29 mark(tail(x0)) 8.80/3.29 mark(repItems(x0)) 8.80/3.29 mark(cons(x0, x1)) 8.80/3.29 mark(0) 8.80/3.29 mark(s(x0)) 8.80/3.29 mark(nil) 8.80/3.29 mark(pair(x0, x1)) 8.80/3.29 a__incr(x0) 8.80/3.29 a__take(x0, x1) 8.80/3.29 a__zip(x0, x1) 8.80/3.29 a__tail(x0) 8.80/3.29 a__repItems(x0) 8.80/3.29 8.80/3.29 We have to consider all minimal (P,Q,R)-chains. 8.80/3.29 ---------------------------------------- 8.80/3.29 8.80/3.29 (25) DependencyGraphProof (EQUIVALENT) 8.80/3.29 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 8.80/3.29 ---------------------------------------- 8.80/3.30 8.80/3.30 (26) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 MARK(incr(X)) -> A__INCR(mark(X)) 8.80/3.30 A__INCR(cons(X, XS)) -> MARK(X) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 MARK(oddNs) -> A__ODDNS 8.80/3.30 A__ODDNS -> A__INCR(a__pairNs) 8.80/3.30 MARK(cons(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X2) 8.80/3.30 8.80/3.30 The TRS R consists of the following rules: 8.80/3.30 8.80/3.30 a__pairNs -> cons(0, incr(oddNs)) 8.80/3.30 a__oddNs -> a__incr(a__pairNs) 8.80/3.30 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.80/3.30 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.80/3.30 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.80/3.30 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.80/3.30 mark(pairNs) -> a__pairNs 8.80/3.30 mark(incr(X)) -> a__incr(mark(X)) 8.80/3.30 mark(oddNs) -> a__oddNs 8.80/3.30 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.80/3.30 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.80/3.30 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.30 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.30 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.30 mark(0) -> 0 8.80/3.30 mark(s(X)) -> s(mark(X)) 8.80/3.30 mark(nil) -> nil 8.80/3.30 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.30 a__pairNs -> pairNs 8.80/3.30 a__incr(X) -> incr(X) 8.80/3.30 a__oddNs -> oddNs 8.80/3.30 a__take(X1, X2) -> take(X1, X2) 8.80/3.30 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.30 a__tail(X) -> tail(X) 8.80/3.30 a__repItems(X) -> repItems(X) 8.80/3.30 8.80/3.30 The set Q consists of the following terms: 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (27) MRRProof (EQUIVALENT) 8.80/3.30 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. 8.80/3.30 8.80/3.30 Strictly oriented dependency pairs: 8.80/3.30 8.80/3.30 MARK(oddNs) -> A__ODDNS 8.80/3.30 8.80/3.30 8.80/3.30 Used ordering: Polynomial interpretation [POLO]: 8.80/3.30 8.80/3.30 POL(0) = 0 8.80/3.30 POL(A__INCR(x_1)) = x_1 8.80/3.30 POL(A__ODDNS) = 2 8.80/3.30 POL(MARK(x_1)) = 2*x_1 8.80/3.30 POL(a__incr(x_1)) = x_1 8.80/3.30 POL(a__oddNs) = 2 8.80/3.30 POL(a__pairNs) = 2 8.80/3.30 POL(a__repItems(x_1)) = 2*x_1 8.80/3.30 POL(a__tail(x_1)) = 2*x_1 8.80/3.30 POL(a__take(x_1, x_2)) = x_1 + x_2 8.80/3.30 POL(a__zip(x_1, x_2)) = x_1 + x_2 8.80/3.30 POL(cons(x_1, x_2)) = 2*x_1 + x_2 8.80/3.30 POL(incr(x_1)) = x_1 8.80/3.30 POL(mark(x_1)) = x_1 8.80/3.30 POL(nil) = 0 8.80/3.30 POL(oddNs) = 2 8.80/3.30 POL(pair(x_1, x_2)) = x_1 + x_2 8.80/3.30 POL(pairNs) = 2 8.80/3.30 POL(repItems(x_1)) = 2*x_1 8.80/3.30 POL(s(x_1)) = x_1 8.80/3.30 POL(tail(x_1)) = 2*x_1 8.80/3.30 POL(take(x_1, x_2)) = x_1 + x_2 8.80/3.30 POL(zip(x_1, x_2)) = x_1 + x_2 8.80/3.30 8.80/3.30 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (28) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 MARK(incr(X)) -> A__INCR(mark(X)) 8.80/3.30 A__INCR(cons(X, XS)) -> MARK(X) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 A__ODDNS -> A__INCR(a__pairNs) 8.80/3.30 MARK(cons(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X2) 8.80/3.30 8.80/3.30 The TRS R consists of the following rules: 8.80/3.30 8.80/3.30 a__pairNs -> cons(0, incr(oddNs)) 8.80/3.30 a__oddNs -> a__incr(a__pairNs) 8.80/3.30 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.80/3.30 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.80/3.30 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.80/3.30 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.80/3.30 mark(pairNs) -> a__pairNs 8.80/3.30 mark(incr(X)) -> a__incr(mark(X)) 8.80/3.30 mark(oddNs) -> a__oddNs 8.80/3.30 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.80/3.30 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.80/3.30 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.30 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.30 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.30 mark(0) -> 0 8.80/3.30 mark(s(X)) -> s(mark(X)) 8.80/3.30 mark(nil) -> nil 8.80/3.30 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.30 a__pairNs -> pairNs 8.80/3.30 a__incr(X) -> incr(X) 8.80/3.30 a__oddNs -> oddNs 8.80/3.30 a__take(X1, X2) -> take(X1, X2) 8.80/3.30 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.30 a__tail(X) -> tail(X) 8.80/3.30 a__repItems(X) -> repItems(X) 8.80/3.30 8.80/3.30 The set Q consists of the following terms: 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (29) DependencyGraphProof (EQUIVALENT) 8.80/3.30 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (30) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 A__INCR(cons(X, XS)) -> MARK(X) 8.80/3.30 MARK(incr(X)) -> A__INCR(mark(X)) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 MARK(cons(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X2) 8.80/3.30 8.80/3.30 The TRS R consists of the following rules: 8.80/3.30 8.80/3.30 a__pairNs -> cons(0, incr(oddNs)) 8.80/3.30 a__oddNs -> a__incr(a__pairNs) 8.80/3.30 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.80/3.30 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.80/3.30 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.80/3.30 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.80/3.30 mark(pairNs) -> a__pairNs 8.80/3.30 mark(incr(X)) -> a__incr(mark(X)) 8.80/3.30 mark(oddNs) -> a__oddNs 8.80/3.30 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.80/3.30 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.80/3.30 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.30 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.30 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.30 mark(0) -> 0 8.80/3.30 mark(s(X)) -> s(mark(X)) 8.80/3.30 mark(nil) -> nil 8.80/3.30 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.30 a__pairNs -> pairNs 8.80/3.30 a__incr(X) -> incr(X) 8.80/3.30 a__oddNs -> oddNs 8.80/3.30 a__take(X1, X2) -> take(X1, X2) 8.80/3.30 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.30 a__tail(X) -> tail(X) 8.80/3.30 a__repItems(X) -> repItems(X) 8.80/3.30 8.80/3.30 The set Q consists of the following terms: 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (31) QDPOrderProof (EQUIVALENT) 8.80/3.30 We use the reduction pair processor [LPAR04,JAR06]. 8.80/3.30 8.80/3.30 8.80/3.30 The following pairs can be oriented strictly and are deleted. 8.80/3.30 8.80/3.30 A__INCR(cons(X, XS)) -> MARK(X) 8.80/3.30 MARK(cons(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X1) 8.80/3.30 MARK(pair(X1, X2)) -> MARK(X2) 8.80/3.30 The remaining pairs can at least be oriented weakly. 8.80/3.30 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 8.80/3.30 8.80/3.30 POL( A__INCR_1(x_1) ) = 2x_1 + 2 8.80/3.30 POL( mark_1(x_1) ) = x_1 8.80/3.30 POL( pairNs ) = 1 8.80/3.30 POL( a__pairNs ) = 1 8.80/3.30 POL( incr_1(x_1) ) = 2x_1 8.80/3.30 POL( a__incr_1(x_1) ) = 2x_1 8.80/3.30 POL( oddNs ) = 2 8.80/3.30 POL( a__oddNs ) = 2 8.80/3.30 POL( take_2(x_1, x_2) ) = 2x_1 + x_2 + 2 8.80/3.30 POL( a__take_2(x_1, x_2) ) = 2x_1 + x_2 + 2 8.80/3.30 POL( zip_2(x_1, x_2) ) = x_1 + 2x_2 + 2 8.80/3.30 POL( a__zip_2(x_1, x_2) ) = x_1 + 2x_2 + 2 8.80/3.30 POL( tail_1(x_1) ) = 0 8.80/3.30 POL( a__tail_1(x_1) ) = max{0, -2} 8.80/3.30 POL( repItems_1(x_1) ) = x_1 + 2 8.80/3.30 POL( a__repItems_1(x_1) ) = x_1 + 2 8.80/3.30 POL( cons_2(x_1, x_2) ) = 2x_1 + 1 8.80/3.30 POL( 0 ) = 0 8.80/3.30 POL( s_1(x_1) ) = 2x_1 8.80/3.30 POL( nil ) = 2 8.80/3.30 POL( pair_2(x_1, x_2) ) = x_1 + x_2 + 1 8.80/3.30 POL( MARK_1(x_1) ) = x_1 + 2 8.80/3.30 8.80/3.30 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 8.80/3.30 8.80/3.30 mark(pairNs) -> a__pairNs 8.80/3.30 mark(incr(X)) -> a__incr(mark(X)) 8.80/3.30 mark(oddNs) -> a__oddNs 8.80/3.30 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.80/3.30 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.80/3.30 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.30 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.30 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.30 mark(0) -> 0 8.80/3.30 mark(s(X)) -> s(mark(X)) 8.80/3.30 mark(nil) -> nil 8.80/3.30 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.30 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.80/3.30 a__incr(X) -> incr(X) 8.80/3.30 a__oddNs -> oddNs 8.80/3.30 a__oddNs -> a__incr(a__pairNs) 8.80/3.30 a__pairNs -> cons(0, incr(oddNs)) 8.80/3.30 a__pairNs -> pairNs 8.80/3.30 a__take(X1, X2) -> take(X1, X2) 8.80/3.30 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.30 a__tail(X) -> tail(X) 8.80/3.30 a__repItems(X) -> repItems(X) 8.80/3.30 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.80/3.30 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.80/3.30 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.80/3.30 8.80/3.30 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (32) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 MARK(incr(X)) -> A__INCR(mark(X)) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 8.80/3.30 The TRS R consists of the following rules: 8.80/3.30 8.80/3.30 a__pairNs -> cons(0, incr(oddNs)) 8.80/3.30 a__oddNs -> a__incr(a__pairNs) 8.80/3.30 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.80/3.30 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.80/3.30 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.80/3.30 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.80/3.30 mark(pairNs) -> a__pairNs 8.80/3.30 mark(incr(X)) -> a__incr(mark(X)) 8.80/3.30 mark(oddNs) -> a__oddNs 8.80/3.30 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.80/3.30 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.80/3.30 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.30 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.30 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.30 mark(0) -> 0 8.80/3.30 mark(s(X)) -> s(mark(X)) 8.80/3.30 mark(nil) -> nil 8.80/3.30 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.30 a__pairNs -> pairNs 8.80/3.30 a__incr(X) -> incr(X) 8.80/3.30 a__oddNs -> oddNs 8.80/3.30 a__take(X1, X2) -> take(X1, X2) 8.80/3.30 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.30 a__tail(X) -> tail(X) 8.80/3.30 a__repItems(X) -> repItems(X) 8.80/3.30 8.80/3.30 The set Q consists of the following terms: 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (33) DependencyGraphProof (EQUIVALENT) 8.80/3.30 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (34) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 8.80/3.30 The TRS R consists of the following rules: 8.80/3.30 8.80/3.30 a__pairNs -> cons(0, incr(oddNs)) 8.80/3.30 a__oddNs -> a__incr(a__pairNs) 8.80/3.30 a__incr(cons(X, XS)) -> cons(s(mark(X)), incr(XS)) 8.80/3.30 a__take(s(N), cons(X, XS)) -> cons(mark(X), take(N, XS)) 8.80/3.30 a__zip(cons(X, XS), cons(Y, YS)) -> cons(pair(mark(X), mark(Y)), zip(XS, YS)) 8.80/3.30 a__repItems(cons(X, XS)) -> cons(mark(X), cons(X, repItems(XS))) 8.80/3.30 mark(pairNs) -> a__pairNs 8.80/3.30 mark(incr(X)) -> a__incr(mark(X)) 8.80/3.30 mark(oddNs) -> a__oddNs 8.80/3.30 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 8.80/3.30 mark(zip(X1, X2)) -> a__zip(mark(X1), mark(X2)) 8.80/3.30 mark(tail(X)) -> a__tail(mark(X)) 8.80/3.30 mark(repItems(X)) -> a__repItems(mark(X)) 8.80/3.30 mark(cons(X1, X2)) -> cons(mark(X1), X2) 8.80/3.30 mark(0) -> 0 8.80/3.30 mark(s(X)) -> s(mark(X)) 8.80/3.30 mark(nil) -> nil 8.80/3.30 mark(pair(X1, X2)) -> pair(mark(X1), mark(X2)) 8.80/3.30 a__pairNs -> pairNs 8.80/3.30 a__incr(X) -> incr(X) 8.80/3.30 a__oddNs -> oddNs 8.80/3.30 a__take(X1, X2) -> take(X1, X2) 8.80/3.30 a__zip(X1, X2) -> zip(X1, X2) 8.80/3.30 a__tail(X) -> tail(X) 8.80/3.30 a__repItems(X) -> repItems(X) 8.80/3.30 8.80/3.30 The set Q consists of the following terms: 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (35) UsableRulesProof (EQUIVALENT) 8.80/3.30 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. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (36) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 8.80/3.30 R is empty. 8.80/3.30 The set Q consists of the following terms: 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (37) QReductionProof (EQUIVALENT) 8.80/3.30 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 8.80/3.30 8.80/3.30 a__pairNs 8.80/3.30 a__oddNs 8.80/3.30 mark(pairNs) 8.80/3.30 mark(incr(x0)) 8.80/3.30 mark(oddNs) 8.80/3.30 mark(take(x0, x1)) 8.80/3.30 mark(zip(x0, x1)) 8.80/3.30 mark(tail(x0)) 8.80/3.30 mark(repItems(x0)) 8.80/3.30 mark(cons(x0, x1)) 8.80/3.30 mark(0) 8.80/3.30 mark(s(x0)) 8.80/3.30 mark(nil) 8.80/3.30 mark(pair(x0, x1)) 8.80/3.30 a__incr(x0) 8.80/3.30 a__take(x0, x1) 8.80/3.30 a__zip(x0, x1) 8.80/3.30 a__tail(x0) 8.80/3.30 a__repItems(x0) 8.80/3.30 8.80/3.30 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (38) 8.80/3.30 Obligation: 8.80/3.30 Q DP problem: 8.80/3.30 The TRS P consists of the following rules: 8.80/3.30 8.80/3.30 MARK(s(X)) -> MARK(X) 8.80/3.30 MARK(incr(X)) -> MARK(X) 8.80/3.30 8.80/3.30 R is empty. 8.80/3.30 Q is empty. 8.80/3.30 We have to consider all minimal (P,Q,R)-chains. 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (39) QDPSizeChangeProof (EQUIVALENT) 8.80/3.30 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. 8.80/3.30 8.80/3.30 From the DPs we obtained the following set of size-change graphs: 8.80/3.30 *MARK(s(X)) -> MARK(X) 8.80/3.30 The graph contains the following edges 1 > 1 8.80/3.30 8.80/3.30 8.80/3.30 *MARK(incr(X)) -> MARK(X) 8.80/3.30 The graph contains the following edges 1 > 1 8.80/3.30 8.80/3.30 8.80/3.30 ---------------------------------------- 8.80/3.30 8.80/3.30 (40) 8.80/3.30 YES 8.80/3.36 EOF