14.65/4.70 WORST_CASE(Omega(n^1), O(n^1)) 14.65/4.71 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 14.65/4.71 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 14.65/4.71 14.65/4.71 14.65/4.71 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.65/4.71 14.65/4.71 (0) CpxTRS 14.65/4.71 (1) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 14.65/4.71 (2) CdtProblem 14.65/4.71 (3) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 14.65/4.71 (4) CdtProblem 14.65/4.71 (5) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 14.65/4.71 (6) CdtProblem 14.65/4.71 (7) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 14.65/4.71 (8) CdtProblem 14.65/4.71 (9) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 54 ms] 14.65/4.71 (10) CdtProblem 14.65/4.71 (11) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 9 ms] 14.65/4.71 (12) CdtProblem 14.65/4.71 (13) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 14.65/4.71 (14) BOUNDS(1, 1) 14.65/4.71 (15) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 14.65/4.71 (16) CpxTRS 14.65/4.71 (17) SlicingProof [LOWER BOUND(ID), 0 ms] 14.65/4.71 (18) CpxTRS 14.65/4.71 (19) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 14.65/4.71 (20) typed CpxTrs 14.65/4.71 (21) OrderProof [LOWER BOUND(ID), 0 ms] 14.65/4.71 (22) typed CpxTrs 14.65/4.71 (23) RewriteLemmaProof [LOWER BOUND(ID), 289 ms] 14.65/4.71 (24) BEST 14.65/4.71 (25) proven lower bound 14.65/4.71 (26) LowerBoundPropagationProof [FINISHED, 0 ms] 14.65/4.71 (27) BOUNDS(n^1, INF) 14.65/4.71 (28) typed CpxTrs 14.65/4.71 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (0) 14.65/4.71 Obligation: 14.65/4.71 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 14.65/4.71 14.65/4.71 14.65/4.71 The TRS R consists of the following rules: 14.65/4.71 14.65/4.71 a__eq(0, 0) -> true 14.65/4.71 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.71 a__eq(X, Y) -> false 14.65/4.71 a__inf(X) -> cons(X, inf(s(X))) 14.65/4.71 a__take(0, X) -> nil 14.65/4.71 a__take(s(X), cons(Y, L)) -> cons(Y, take(X, L)) 14.65/4.71 a__length(nil) -> 0 14.65/4.71 a__length(cons(X, L)) -> s(length(L)) 14.65/4.71 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.71 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.71 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.71 mark(length(X)) -> a__length(mark(X)) 14.65/4.71 mark(0) -> 0 14.65/4.71 mark(true) -> true 14.65/4.71 mark(s(X)) -> s(X) 14.65/4.71 mark(false) -> false 14.65/4.71 mark(cons(X1, X2)) -> cons(X1, X2) 14.65/4.71 mark(nil) -> nil 14.65/4.71 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.71 a__inf(X) -> inf(X) 14.65/4.71 a__take(X1, X2) -> take(X1, X2) 14.65/4.71 a__length(X) -> length(X) 14.65/4.71 14.65/4.71 S is empty. 14.65/4.71 Rewrite Strategy: INNERMOST 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (1) CpxTrsToCdtProof (UPPER BOUND(ID)) 14.65/4.71 Converted Cpx (relative) TRS to CDT 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (2) 14.65/4.71 Obligation: 14.65/4.71 Complexity Dependency Tuples Problem 14.65/4.71 14.65/4.71 Rules: 14.65/4.71 a__eq(0, 0) -> true 14.65/4.71 a__eq(s(z0), s(z1)) -> a__eq(z0, z1) 14.65/4.71 a__eq(z0, z1) -> false 14.65/4.71 a__eq(z0, z1) -> eq(z0, z1) 14.65/4.71 a__inf(z0) -> cons(z0, inf(s(z0))) 14.65/4.71 a__inf(z0) -> inf(z0) 14.65/4.71 a__take(0, z0) -> nil 14.65/4.71 a__take(s(z0), cons(z1, z2)) -> cons(z1, take(z0, z2)) 14.65/4.71 a__take(z0, z1) -> take(z0, z1) 14.65/4.71 a__length(nil) -> 0 14.65/4.71 a__length(cons(z0, z1)) -> s(length(z1)) 14.65/4.71 a__length(z0) -> length(z0) 14.65/4.71 mark(eq(z0, z1)) -> a__eq(z0, z1) 14.65/4.71 mark(inf(z0)) -> a__inf(mark(z0)) 14.65/4.71 mark(take(z0, z1)) -> a__take(mark(z0), mark(z1)) 14.65/4.71 mark(length(z0)) -> a__length(mark(z0)) 14.65/4.71 mark(0) -> 0 14.65/4.71 mark(true) -> true 14.65/4.71 mark(s(z0)) -> s(z0) 14.65/4.71 mark(false) -> false 14.65/4.71 mark(cons(z0, z1)) -> cons(z0, z1) 14.65/4.71 mark(nil) -> nil 14.65/4.71 Tuples: 14.65/4.71 A__EQ(0, 0) -> c 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 A__EQ(z0, z1) -> c2 14.65/4.71 A__EQ(z0, z1) -> c3 14.65/4.71 A__INF(z0) -> c4 14.65/4.71 A__INF(z0) -> c5 14.65/4.71 A__TAKE(0, z0) -> c6 14.65/4.71 A__TAKE(s(z0), cons(z1, z2)) -> c7 14.65/4.71 A__TAKE(z0, z1) -> c8 14.65/4.71 A__LENGTH(nil) -> c9 14.65/4.71 A__LENGTH(cons(z0, z1)) -> c10 14.65/4.71 A__LENGTH(z0) -> c11 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(A__INF(mark(z0)), MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(A__TAKE(mark(z0), mark(z1)), MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(A__LENGTH(mark(z0)), MARK(z0)) 14.65/4.71 MARK(0) -> c16 14.65/4.71 MARK(true) -> c17 14.65/4.71 MARK(s(z0)) -> c18 14.65/4.71 MARK(false) -> c19 14.65/4.71 MARK(cons(z0, z1)) -> c20 14.65/4.71 MARK(nil) -> c21 14.65/4.71 S tuples: 14.65/4.71 A__EQ(0, 0) -> c 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 A__EQ(z0, z1) -> c2 14.65/4.71 A__EQ(z0, z1) -> c3 14.65/4.71 A__INF(z0) -> c4 14.65/4.71 A__INF(z0) -> c5 14.65/4.71 A__TAKE(0, z0) -> c6 14.65/4.71 A__TAKE(s(z0), cons(z1, z2)) -> c7 14.65/4.71 A__TAKE(z0, z1) -> c8 14.65/4.71 A__LENGTH(nil) -> c9 14.65/4.71 A__LENGTH(cons(z0, z1)) -> c10 14.65/4.71 A__LENGTH(z0) -> c11 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(A__INF(mark(z0)), MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(A__TAKE(mark(z0), mark(z1)), MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(A__LENGTH(mark(z0)), MARK(z0)) 14.65/4.71 MARK(0) -> c16 14.65/4.71 MARK(true) -> c17 14.65/4.71 MARK(s(z0)) -> c18 14.65/4.71 MARK(false) -> c19 14.65/4.71 MARK(cons(z0, z1)) -> c20 14.65/4.71 MARK(nil) -> c21 14.65/4.71 K tuples:none 14.65/4.71 Defined Rule Symbols: a__eq_2, a__inf_1, a__take_2, a__length_1, mark_1 14.65/4.71 14.65/4.71 Defined Pair Symbols: A__EQ_2, A__INF_1, A__TAKE_2, A__LENGTH_1, MARK_1 14.65/4.71 14.65/4.71 Compound Symbols: c, c1_1, c2, c3, c4, c5, c6, c7, c8, c9, c10, c11, c12_1, c13_2, c14_3, c15_2, c16, c17, c18, c19, c20, c21 14.65/4.71 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 14.65/4.71 Removed 17 trailing nodes: 14.65/4.71 MARK(true) -> c17 14.65/4.71 MARK(cons(z0, z1)) -> c20 14.65/4.71 A__EQ(z0, z1) -> c2 14.65/4.71 A__TAKE(s(z0), cons(z1, z2)) -> c7 14.65/4.71 A__EQ(0, 0) -> c 14.65/4.71 A__LENGTH(nil) -> c9 14.65/4.71 MARK(0) -> c16 14.65/4.71 MARK(nil) -> c21 14.65/4.71 A__LENGTH(cons(z0, z1)) -> c10 14.65/4.71 A__INF(z0) -> c4 14.65/4.71 A__EQ(z0, z1) -> c3 14.65/4.71 MARK(false) -> c19 14.65/4.71 A__LENGTH(z0) -> c11 14.65/4.71 MARK(s(z0)) -> c18 14.65/4.71 A__TAKE(0, z0) -> c6 14.65/4.71 A__INF(z0) -> c5 14.65/4.71 A__TAKE(z0, z1) -> c8 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (4) 14.65/4.71 Obligation: 14.65/4.71 Complexity Dependency Tuples Problem 14.65/4.71 14.65/4.71 Rules: 14.65/4.71 a__eq(0, 0) -> true 14.65/4.71 a__eq(s(z0), s(z1)) -> a__eq(z0, z1) 14.65/4.71 a__eq(z0, z1) -> false 14.65/4.71 a__eq(z0, z1) -> eq(z0, z1) 14.65/4.71 a__inf(z0) -> cons(z0, inf(s(z0))) 14.65/4.71 a__inf(z0) -> inf(z0) 14.65/4.71 a__take(0, z0) -> nil 14.65/4.71 a__take(s(z0), cons(z1, z2)) -> cons(z1, take(z0, z2)) 14.65/4.71 a__take(z0, z1) -> take(z0, z1) 14.65/4.71 a__length(nil) -> 0 14.65/4.71 a__length(cons(z0, z1)) -> s(length(z1)) 14.65/4.71 a__length(z0) -> length(z0) 14.65/4.71 mark(eq(z0, z1)) -> a__eq(z0, z1) 14.65/4.71 mark(inf(z0)) -> a__inf(mark(z0)) 14.65/4.71 mark(take(z0, z1)) -> a__take(mark(z0), mark(z1)) 14.65/4.71 mark(length(z0)) -> a__length(mark(z0)) 14.65/4.71 mark(0) -> 0 14.65/4.71 mark(true) -> true 14.65/4.71 mark(s(z0)) -> s(z0) 14.65/4.71 mark(false) -> false 14.65/4.71 mark(cons(z0, z1)) -> cons(z0, z1) 14.65/4.71 mark(nil) -> nil 14.65/4.71 Tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(A__INF(mark(z0)), MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(A__TAKE(mark(z0), mark(z1)), MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(A__LENGTH(mark(z0)), MARK(z0)) 14.65/4.71 S tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(A__INF(mark(z0)), MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(A__TAKE(mark(z0), mark(z1)), MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(A__LENGTH(mark(z0)), MARK(z0)) 14.65/4.71 K tuples:none 14.65/4.71 Defined Rule Symbols: a__eq_2, a__inf_1, a__take_2, a__length_1, mark_1 14.65/4.71 14.65/4.71 Defined Pair Symbols: A__EQ_2, MARK_1 14.65/4.71 14.65/4.71 Compound Symbols: c1_1, c12_1, c13_2, c14_3, c15_2 14.65/4.71 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (5) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 14.65/4.71 Removed 3 trailing tuple parts 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (6) 14.65/4.71 Obligation: 14.65/4.71 Complexity Dependency Tuples Problem 14.65/4.71 14.65/4.71 Rules: 14.65/4.71 a__eq(0, 0) -> true 14.65/4.71 a__eq(s(z0), s(z1)) -> a__eq(z0, z1) 14.65/4.71 a__eq(z0, z1) -> false 14.65/4.71 a__eq(z0, z1) -> eq(z0, z1) 14.65/4.71 a__inf(z0) -> cons(z0, inf(s(z0))) 14.65/4.71 a__inf(z0) -> inf(z0) 14.65/4.71 a__take(0, z0) -> nil 14.65/4.71 a__take(s(z0), cons(z1, z2)) -> cons(z1, take(z0, z2)) 14.65/4.71 a__take(z0, z1) -> take(z0, z1) 14.65/4.71 a__length(nil) -> 0 14.65/4.71 a__length(cons(z0, z1)) -> s(length(z1)) 14.65/4.71 a__length(z0) -> length(z0) 14.65/4.71 mark(eq(z0, z1)) -> a__eq(z0, z1) 14.65/4.71 mark(inf(z0)) -> a__inf(mark(z0)) 14.65/4.71 mark(take(z0, z1)) -> a__take(mark(z0), mark(z1)) 14.65/4.71 mark(length(z0)) -> a__length(mark(z0)) 14.65/4.71 mark(0) -> 0 14.65/4.71 mark(true) -> true 14.65/4.71 mark(s(z0)) -> s(z0) 14.65/4.71 mark(false) -> false 14.65/4.71 mark(cons(z0, z1)) -> cons(z0, z1) 14.65/4.71 mark(nil) -> nil 14.65/4.71 Tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.71 S tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.71 K tuples:none 14.65/4.71 Defined Rule Symbols: a__eq_2, a__inf_1, a__take_2, a__length_1, mark_1 14.65/4.71 14.65/4.71 Defined Pair Symbols: A__EQ_2, MARK_1 14.65/4.71 14.65/4.71 Compound Symbols: c1_1, c12_1, c13_1, c14_2, c15_1 14.65/4.71 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (7) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 14.65/4.71 The following rules are not usable and were removed: 14.65/4.71 a__eq(0, 0) -> true 14.65/4.71 a__eq(s(z0), s(z1)) -> a__eq(z0, z1) 14.65/4.71 a__eq(z0, z1) -> false 14.65/4.71 a__eq(z0, z1) -> eq(z0, z1) 14.65/4.71 a__inf(z0) -> cons(z0, inf(s(z0))) 14.65/4.71 a__inf(z0) -> inf(z0) 14.65/4.71 a__take(0, z0) -> nil 14.65/4.71 a__take(s(z0), cons(z1, z2)) -> cons(z1, take(z0, z2)) 14.65/4.71 a__take(z0, z1) -> take(z0, z1) 14.65/4.71 a__length(nil) -> 0 14.65/4.71 a__length(cons(z0, z1)) -> s(length(z1)) 14.65/4.71 a__length(z0) -> length(z0) 14.65/4.71 mark(eq(z0, z1)) -> a__eq(z0, z1) 14.65/4.71 mark(inf(z0)) -> a__inf(mark(z0)) 14.65/4.71 mark(take(z0, z1)) -> a__take(mark(z0), mark(z1)) 14.65/4.71 mark(length(z0)) -> a__length(mark(z0)) 14.65/4.71 mark(0) -> 0 14.65/4.71 mark(true) -> true 14.65/4.71 mark(s(z0)) -> s(z0) 14.65/4.71 mark(false) -> false 14.65/4.71 mark(cons(z0, z1)) -> cons(z0, z1) 14.65/4.71 mark(nil) -> nil 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (8) 14.65/4.71 Obligation: 14.65/4.71 Complexity Dependency Tuples Problem 14.65/4.71 14.65/4.71 Rules:none 14.65/4.71 Tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.71 S tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.71 K tuples:none 14.65/4.71 Defined Rule Symbols:none 14.65/4.71 14.65/4.71 Defined Pair Symbols: A__EQ_2, MARK_1 14.65/4.71 14.65/4.71 Compound Symbols: c1_1, c12_1, c13_1, c14_2, c15_1 14.65/4.71 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (9) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 14.65/4.71 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.71 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.71 We considered the (Usable) Rules:none 14.65/4.71 And the Tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.71 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.71 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.71 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.71 The order we found is given by the following interpretation: 14.65/4.71 14.65/4.71 Polynomial interpretation : 14.65/4.71 14.65/4.71 POL(A__EQ(x_1, x_2)) = [1] + x_1 + x_2 14.65/4.71 POL(MARK(x_1)) = [1] + x_1 14.65/4.71 POL(c1(x_1)) = x_1 14.65/4.71 POL(c12(x_1)) = x_1 14.65/4.71 POL(c13(x_1)) = x_1 14.65/4.71 POL(c14(x_1, x_2)) = x_1 + x_2 14.65/4.71 POL(c15(x_1)) = x_1 14.65/4.71 POL(eq(x_1, x_2)) = [1] + x_1 + x_2 14.65/4.71 POL(inf(x_1)) = [1] + x_1 14.65/4.71 POL(length(x_1)) = [1] + x_1 14.65/4.71 POL(s(x_1)) = [1] + x_1 14.65/4.71 POL(take(x_1, x_2)) = [1] + x_1 + x_2 14.65/4.71 14.65/4.71 ---------------------------------------- 14.65/4.71 14.65/4.71 (10) 14.65/4.71 Obligation: 14.65/4.71 Complexity Dependency Tuples Problem 14.65/4.71 14.65/4.71 Rules:none 14.65/4.71 Tuples: 14.65/4.71 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.71 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.72 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.72 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.72 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.72 S tuples: 14.65/4.72 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.72 K tuples: 14.65/4.72 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.72 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.72 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.72 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.72 Defined Rule Symbols:none 14.65/4.72 14.65/4.72 Defined Pair Symbols: A__EQ_2, MARK_1 14.65/4.72 14.65/4.72 Compound Symbols: c1_1, c12_1, c13_1, c14_2, c15_1 14.65/4.72 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (11) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 14.65/4.72 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 14.65/4.72 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.72 We considered the (Usable) Rules:none 14.65/4.72 And the Tuples: 14.65/4.72 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.72 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.72 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.72 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.72 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.72 The order we found is given by the following interpretation: 14.65/4.72 14.65/4.72 Polynomial interpretation : 14.65/4.72 14.65/4.72 POL(A__EQ(x_1, x_2)) = [1] + x_1 + x_2 14.65/4.72 POL(MARK(x_1)) = x_1 14.65/4.72 POL(c1(x_1)) = x_1 14.65/4.72 POL(c12(x_1)) = x_1 14.65/4.72 POL(c13(x_1)) = x_1 14.65/4.72 POL(c14(x_1, x_2)) = x_1 + x_2 14.65/4.72 POL(c15(x_1)) = x_1 14.65/4.72 POL(eq(x_1, x_2)) = [1] + x_1 + x_2 14.65/4.72 POL(inf(x_1)) = x_1 14.65/4.72 POL(length(x_1)) = x_1 14.65/4.72 POL(s(x_1)) = x_1 14.65/4.72 POL(take(x_1, x_2)) = [1] + x_1 + x_2 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (12) 14.65/4.72 Obligation: 14.65/4.72 Complexity Dependency Tuples Problem 14.65/4.72 14.65/4.72 Rules:none 14.65/4.72 Tuples: 14.65/4.72 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.72 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.72 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.72 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.72 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.72 S tuples:none 14.65/4.72 K tuples: 14.65/4.72 A__EQ(s(z0), s(z1)) -> c1(A__EQ(z0, z1)) 14.65/4.72 MARK(eq(z0, z1)) -> c12(A__EQ(z0, z1)) 14.65/4.72 MARK(inf(z0)) -> c13(MARK(z0)) 14.65/4.72 MARK(length(z0)) -> c15(MARK(z0)) 14.65/4.72 MARK(take(z0, z1)) -> c14(MARK(z0), MARK(z1)) 14.65/4.72 Defined Rule Symbols:none 14.65/4.72 14.65/4.72 Defined Pair Symbols: A__EQ_2, MARK_1 14.65/4.72 14.65/4.72 Compound Symbols: c1_1, c12_1, c13_1, c14_2, c15_1 14.65/4.72 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (13) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 14.65/4.72 The set S is empty 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (14) 14.65/4.72 BOUNDS(1, 1) 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (15) RenamingProof (BOTH BOUNDS(ID, ID)) 14.65/4.72 Renamed function symbols to avoid clashes with predefined symbol. 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (16) 14.65/4.72 Obligation: 14.65/4.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 14.65/4.72 14.65/4.72 14.65/4.72 The TRS R consists of the following rules: 14.65/4.72 14.65/4.72 a__eq(0', 0') -> true 14.65/4.72 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.72 a__eq(X, Y) -> false 14.65/4.72 a__inf(X) -> cons(X, inf(s(X))) 14.65/4.72 a__take(0', X) -> nil 14.65/4.72 a__take(s(X), cons(Y, L)) -> cons(Y, take(X, L)) 14.65/4.72 a__length(nil) -> 0' 14.65/4.72 a__length(cons(X, L)) -> s(length(L)) 14.65/4.72 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.72 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.72 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.72 mark(length(X)) -> a__length(mark(X)) 14.65/4.72 mark(0') -> 0' 14.65/4.72 mark(true) -> true 14.65/4.72 mark(s(X)) -> s(X) 14.65/4.72 mark(false) -> false 14.65/4.72 mark(cons(X1, X2)) -> cons(X1, X2) 14.65/4.72 mark(nil) -> nil 14.65/4.72 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.72 a__inf(X) -> inf(X) 14.65/4.72 a__take(X1, X2) -> take(X1, X2) 14.65/4.72 a__length(X) -> length(X) 14.65/4.72 14.65/4.72 S is empty. 14.65/4.72 Rewrite Strategy: INNERMOST 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (17) SlicingProof (LOWER BOUND(ID)) 14.65/4.72 Sliced the following arguments: 14.65/4.72 cons/0 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (18) 14.65/4.72 Obligation: 14.65/4.72 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 14.65/4.72 14.65/4.72 14.65/4.72 The TRS R consists of the following rules: 14.65/4.72 14.65/4.72 a__eq(0', 0') -> true 14.65/4.72 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.72 a__eq(X, Y) -> false 14.65/4.72 a__inf(X) -> cons(inf(s(X))) 14.65/4.72 a__take(0', X) -> nil 14.65/4.72 a__take(s(X), cons(L)) -> cons(take(X, L)) 14.65/4.72 a__length(nil) -> 0' 14.65/4.72 a__length(cons(L)) -> s(length(L)) 14.65/4.72 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.72 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.72 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.72 mark(length(X)) -> a__length(mark(X)) 14.65/4.72 mark(0') -> 0' 14.65/4.72 mark(true) -> true 14.65/4.72 mark(s(X)) -> s(X) 14.65/4.72 mark(false) -> false 14.65/4.72 mark(cons(X2)) -> cons(X2) 14.65/4.72 mark(nil) -> nil 14.65/4.72 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.72 a__inf(X) -> inf(X) 14.65/4.72 a__take(X1, X2) -> take(X1, X2) 14.65/4.72 a__length(X) -> length(X) 14.65/4.72 14.65/4.72 S is empty. 14.65/4.72 Rewrite Strategy: INNERMOST 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (19) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 14.65/4.72 Infered types. 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (20) 14.65/4.72 Obligation: 14.65/4.72 Innermost TRS: 14.65/4.72 Rules: 14.65/4.72 a__eq(0', 0') -> true 14.65/4.72 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.72 a__eq(X, Y) -> false 14.65/4.72 a__inf(X) -> cons(inf(s(X))) 14.65/4.72 a__take(0', X) -> nil 14.65/4.72 a__take(s(X), cons(L)) -> cons(take(X, L)) 14.65/4.72 a__length(nil) -> 0' 14.65/4.72 a__length(cons(L)) -> s(length(L)) 14.65/4.72 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.72 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.72 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.72 mark(length(X)) -> a__length(mark(X)) 14.65/4.72 mark(0') -> 0' 14.65/4.72 mark(true) -> true 14.65/4.72 mark(s(X)) -> s(X) 14.65/4.72 mark(false) -> false 14.65/4.72 mark(cons(X2)) -> cons(X2) 14.65/4.72 mark(nil) -> nil 14.65/4.72 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.72 a__inf(X) -> inf(X) 14.65/4.72 a__take(X1, X2) -> take(X1, X2) 14.65/4.72 a__length(X) -> length(X) 14.65/4.72 14.65/4.72 Types: 14.65/4.72 a__eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 0' :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 true :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 s :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 false :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 cons :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 nil :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 mark :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 hole_0':true:s:false:inf:cons:nil:take:length:eq1_0 :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0 :: Nat -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (21) OrderProof (LOWER BOUND(ID)) 14.65/4.72 Heuristically decided to analyse the following defined symbols: 14.65/4.72 a__eq, mark 14.65/4.72 14.65/4.72 They will be analysed ascendingly in the following order: 14.65/4.72 a__eq < mark 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (22) 14.65/4.72 Obligation: 14.65/4.72 Innermost TRS: 14.65/4.72 Rules: 14.65/4.72 a__eq(0', 0') -> true 14.65/4.72 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.72 a__eq(X, Y) -> false 14.65/4.72 a__inf(X) -> cons(inf(s(X))) 14.65/4.72 a__take(0', X) -> nil 14.65/4.72 a__take(s(X), cons(L)) -> cons(take(X, L)) 14.65/4.72 a__length(nil) -> 0' 14.65/4.72 a__length(cons(L)) -> s(length(L)) 14.65/4.72 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.72 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.72 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.72 mark(length(X)) -> a__length(mark(X)) 14.65/4.72 mark(0') -> 0' 14.65/4.72 mark(true) -> true 14.65/4.72 mark(s(X)) -> s(X) 14.65/4.72 mark(false) -> false 14.65/4.72 mark(cons(X2)) -> cons(X2) 14.65/4.72 mark(nil) -> nil 14.65/4.72 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.72 a__inf(X) -> inf(X) 14.65/4.72 a__take(X1, X2) -> take(X1, X2) 14.65/4.72 a__length(X) -> length(X) 14.65/4.72 14.65/4.72 Types: 14.65/4.72 a__eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 0' :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 true :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 s :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 false :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 cons :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 nil :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 mark :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 hole_0':true:s:false:inf:cons:nil:take:length:eq1_0 :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0 :: Nat -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 14.65/4.72 14.65/4.72 Generator Equations: 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(0) <=> 0' 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(+(x, 1)) <=> s(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(x)) 14.65/4.72 14.65/4.72 14.65/4.72 The following defined symbols remain to be analysed: 14.65/4.72 a__eq, mark 14.65/4.72 14.65/4.72 They will be analysed ascendingly in the following order: 14.65/4.72 a__eq < mark 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (23) RewriteLemmaProof (LOWER BOUND(ID)) 14.65/4.72 Proved the following rewrite lemma: 14.65/4.72 a__eq(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(n4_0), gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(n4_0)) -> true, rt in Omega(1 + n4_0) 14.65/4.72 14.65/4.72 Induction Base: 14.65/4.72 a__eq(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(0), gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(0)) ->_R^Omega(1) 14.65/4.72 true 14.65/4.72 14.65/4.72 Induction Step: 14.65/4.72 a__eq(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(+(n4_0, 1)), gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(+(n4_0, 1))) ->_R^Omega(1) 14.65/4.72 a__eq(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(n4_0), gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(n4_0)) ->_IH 14.65/4.72 true 14.65/4.72 14.65/4.72 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (24) 14.65/4.72 Complex Obligation (BEST) 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (25) 14.65/4.72 Obligation: 14.65/4.72 Proved the lower bound n^1 for the following obligation: 14.65/4.72 14.65/4.72 Innermost TRS: 14.65/4.72 Rules: 14.65/4.72 a__eq(0', 0') -> true 14.65/4.72 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.72 a__eq(X, Y) -> false 14.65/4.72 a__inf(X) -> cons(inf(s(X))) 14.65/4.72 a__take(0', X) -> nil 14.65/4.72 a__take(s(X), cons(L)) -> cons(take(X, L)) 14.65/4.72 a__length(nil) -> 0' 14.65/4.72 a__length(cons(L)) -> s(length(L)) 14.65/4.72 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.72 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.72 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.72 mark(length(X)) -> a__length(mark(X)) 14.65/4.72 mark(0') -> 0' 14.65/4.72 mark(true) -> true 14.65/4.72 mark(s(X)) -> s(X) 14.65/4.72 mark(false) -> false 14.65/4.72 mark(cons(X2)) -> cons(X2) 14.65/4.72 mark(nil) -> nil 14.65/4.72 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.72 a__inf(X) -> inf(X) 14.65/4.72 a__take(X1, X2) -> take(X1, X2) 14.65/4.72 a__length(X) -> length(X) 14.65/4.72 14.65/4.72 Types: 14.65/4.72 a__eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 0' :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 true :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 s :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 false :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 cons :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 nil :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 mark :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 hole_0':true:s:false:inf:cons:nil:take:length:eq1_0 :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0 :: Nat -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 14.65/4.72 14.65/4.72 Generator Equations: 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(0) <=> 0' 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(+(x, 1)) <=> s(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(x)) 14.65/4.72 14.65/4.72 14.65/4.72 The following defined symbols remain to be analysed: 14.65/4.72 a__eq, mark 14.65/4.72 14.65/4.72 They will be analysed ascendingly in the following order: 14.65/4.72 a__eq < mark 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (26) LowerBoundPropagationProof (FINISHED) 14.65/4.72 Propagated lower bound. 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (27) 14.65/4.72 BOUNDS(n^1, INF) 14.65/4.72 14.65/4.72 ---------------------------------------- 14.65/4.72 14.65/4.72 (28) 14.65/4.72 Obligation: 14.65/4.72 Innermost TRS: 14.65/4.72 Rules: 14.65/4.72 a__eq(0', 0') -> true 14.65/4.72 a__eq(s(X), s(Y)) -> a__eq(X, Y) 14.65/4.72 a__eq(X, Y) -> false 14.65/4.72 a__inf(X) -> cons(inf(s(X))) 14.65/4.72 a__take(0', X) -> nil 14.65/4.72 a__take(s(X), cons(L)) -> cons(take(X, L)) 14.65/4.72 a__length(nil) -> 0' 14.65/4.72 a__length(cons(L)) -> s(length(L)) 14.65/4.72 mark(eq(X1, X2)) -> a__eq(X1, X2) 14.65/4.72 mark(inf(X)) -> a__inf(mark(X)) 14.65/4.72 mark(take(X1, X2)) -> a__take(mark(X1), mark(X2)) 14.65/4.72 mark(length(X)) -> a__length(mark(X)) 14.65/4.72 mark(0') -> 0' 14.65/4.72 mark(true) -> true 14.65/4.72 mark(s(X)) -> s(X) 14.65/4.72 mark(false) -> false 14.65/4.72 mark(cons(X2)) -> cons(X2) 14.65/4.72 mark(nil) -> nil 14.65/4.72 a__eq(X1, X2) -> eq(X1, X2) 14.65/4.72 a__inf(X) -> inf(X) 14.65/4.72 a__take(X1, X2) -> take(X1, X2) 14.65/4.72 a__length(X) -> length(X) 14.65/4.72 14.65/4.72 Types: 14.65/4.72 a__eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 0' :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 true :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 s :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 false :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 cons :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 inf :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 nil :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 take :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 a__length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 length :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 mark :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 eq :: 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 hole_0':true:s:false:inf:cons:nil:take:length:eq1_0 :: 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0 :: Nat -> 0':true:s:false:inf:cons:nil:take:length:eq 14.65/4.72 14.65/4.72 14.65/4.72 Lemmas: 14.65/4.72 a__eq(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(n4_0), gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(n4_0)) -> true, rt in Omega(1 + n4_0) 14.65/4.72 14.65/4.72 14.65/4.72 Generator Equations: 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(0) <=> 0' 14.65/4.72 gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(+(x, 1)) <=> s(gen_0':true:s:false:inf:cons:nil:take:length:eq2_0(x)) 14.65/4.72 14.65/4.72 14.65/4.72 The following defined symbols remain to be analysed: 14.65/4.72 mark 14.78/4.75 EOF