29.83/9.22 WORST_CASE(Omega(n^1), O(n^1)) 30.07/9.23 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 30.07/9.23 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 30.07/9.23 30.07/9.23 30.07/9.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 30.07/9.23 30.07/9.23 (0) CpxTRS 30.07/9.23 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 2 ms] 30.07/9.23 (2) CpxTRS 30.07/9.23 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 30.07/9.23 (4) CpxTRS 30.07/9.23 (5) CpxTrsMatchBoundsTAProof [FINISHED, 86 ms] 30.07/9.23 (6) BOUNDS(1, n^1) 30.07/9.23 (7) RenamingProof [BOTH BOUNDS(ID, ID), 0 ms] 30.07/9.23 (8) CpxTRS 30.07/9.23 (9) TypeInferenceProof [BOTH BOUNDS(ID, ID), 0 ms] 30.07/9.23 (10) typed CpxTrs 30.07/9.23 (11) OrderProof [LOWER BOUND(ID), 0 ms] 30.07/9.23 (12) typed CpxTrs 30.07/9.23 (13) RewriteLemmaProof [LOWER BOUND(ID), 448 ms] 30.07/9.23 (14) BEST 30.07/9.23 (15) proven lower bound 30.07/9.23 (16) LowerBoundPropagationProof [FINISHED, 0 ms] 30.07/9.23 (17) BOUNDS(n^1, INF) 30.07/9.23 (18) typed CpxTrs 30.07/9.23 (19) RewriteLemmaProof [LOWER BOUND(ID), 96 ms] 30.07/9.23 (20) typed CpxTrs 30.07/9.23 30.07/9.23 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (0) 30.07/9.23 Obligation: 30.07/9.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 30.07/9.23 30.07/9.23 30.07/9.23 The TRS R consists of the following rules: 30.07/9.23 30.07/9.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.23 active(__(X, nil)) -> mark(X) 30.07/9.23 active(__(nil, X)) -> mark(X) 30.07/9.23 active(and(tt, X)) -> mark(X) 30.07/9.23 active(isList(V)) -> mark(isNeList(V)) 30.07/9.23 active(isList(nil)) -> mark(tt) 30.07/9.23 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.23 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.23 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.23 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.23 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.23 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.23 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.23 active(isPal(nil)) -> mark(tt) 30.07/9.23 active(isQid(a)) -> mark(tt) 30.07/9.23 active(isQid(e)) -> mark(tt) 30.07/9.23 active(isQid(i)) -> mark(tt) 30.07/9.23 active(isQid(o)) -> mark(tt) 30.07/9.23 active(isQid(u)) -> mark(tt) 30.07/9.23 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.23 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.23 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.23 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.23 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.23 proper(nil) -> ok(nil) 30.07/9.23 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.23 proper(tt) -> ok(tt) 30.07/9.23 proper(isList(X)) -> isList(proper(X)) 30.07/9.23 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.23 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.23 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.23 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.23 proper(a) -> ok(a) 30.07/9.23 proper(e) -> ok(e) 30.07/9.23 proper(i) -> ok(i) 30.07/9.23 proper(o) -> ok(o) 30.07/9.23 proper(u) -> ok(u) 30.07/9.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.23 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.23 isList(ok(X)) -> ok(isList(X)) 30.07/9.23 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.23 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.23 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.23 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.23 top(mark(X)) -> top(proper(X)) 30.07/9.23 top(ok(X)) -> top(active(X)) 30.07/9.23 30.07/9.23 S is empty. 30.07/9.23 Rewrite Strategy: FULL 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 30.07/9.23 The following defined symbols can occur below the 0th argument of top: proper, active 30.07/9.23 The following defined symbols can occur below the 0th argument of proper: proper, active 30.07/9.23 The following defined symbols can occur below the 0th argument of active: proper, active 30.07/9.23 30.07/9.23 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 30.07/9.23 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.23 active(__(X, nil)) -> mark(X) 30.07/9.23 active(__(nil, X)) -> mark(X) 30.07/9.23 active(and(tt, X)) -> mark(X) 30.07/9.23 active(isList(V)) -> mark(isNeList(V)) 30.07/9.23 active(isList(nil)) -> mark(tt) 30.07/9.23 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.23 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.23 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.23 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.23 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.23 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.23 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.23 active(isPal(nil)) -> mark(tt) 30.07/9.23 active(isQid(a)) -> mark(tt) 30.07/9.23 active(isQid(e)) -> mark(tt) 30.07/9.23 active(isQid(i)) -> mark(tt) 30.07/9.23 active(isQid(o)) -> mark(tt) 30.07/9.23 active(isQid(u)) -> mark(tt) 30.07/9.23 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.23 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.23 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.23 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.23 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.23 proper(isList(X)) -> isList(proper(X)) 30.07/9.23 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.23 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.23 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.23 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.23 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (2) 30.07/9.23 Obligation: 30.07/9.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 30.07/9.23 30.07/9.23 30.07/9.23 The TRS R consists of the following rules: 30.07/9.23 30.07/9.23 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.23 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.23 proper(nil) -> ok(nil) 30.07/9.23 proper(tt) -> ok(tt) 30.07/9.23 proper(a) -> ok(a) 30.07/9.23 proper(e) -> ok(e) 30.07/9.23 proper(i) -> ok(i) 30.07/9.23 proper(o) -> ok(o) 30.07/9.23 proper(u) -> ok(u) 30.07/9.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.23 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.23 isList(ok(X)) -> ok(isList(X)) 30.07/9.23 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.23 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.23 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.23 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.23 top(mark(X)) -> top(proper(X)) 30.07/9.23 top(ok(X)) -> top(active(X)) 30.07/9.23 30.07/9.23 S is empty. 30.07/9.23 Rewrite Strategy: FULL 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 30.07/9.23 transformed relative TRS to TRS 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (4) 30.07/9.23 Obligation: 30.07/9.23 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 30.07/9.23 30.07/9.23 30.07/9.23 The TRS R consists of the following rules: 30.07/9.23 30.07/9.23 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.23 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.23 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.23 proper(nil) -> ok(nil) 30.07/9.23 proper(tt) -> ok(tt) 30.07/9.23 proper(a) -> ok(a) 30.07/9.23 proper(e) -> ok(e) 30.07/9.23 proper(i) -> ok(i) 30.07/9.23 proper(o) -> ok(o) 30.07/9.23 proper(u) -> ok(u) 30.07/9.23 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.23 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.23 isList(ok(X)) -> ok(isList(X)) 30.07/9.23 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.23 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.23 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.23 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.23 top(mark(X)) -> top(proper(X)) 30.07/9.23 top(ok(X)) -> top(active(X)) 30.07/9.23 30.07/9.23 S is empty. 30.07/9.23 Rewrite Strategy: FULL 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (5) CpxTrsMatchBoundsTAProof (FINISHED) 30.07/9.23 A linear upper bound on the runtime complexity of the TRS R could be shown with a Match-Bound[TAB_LEFTLINEAR,TAB_NONLEFTLINEAR] (for contructor-based start-terms) of 2. 30.07/9.23 30.07/9.23 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 30.07/9.23 final states : [1, 2, 3, 4, 5, 6, 7, 8, 9] 30.07/9.23 transitions: 30.07/9.23 mark0(0) -> 0 30.07/9.23 nil0() -> 0 30.07/9.23 ok0(0) -> 0 30.07/9.23 tt0() -> 0 30.07/9.23 a0() -> 0 30.07/9.23 e0() -> 0 30.07/9.23 i0() -> 0 30.07/9.23 o0() -> 0 30.07/9.23 u0() -> 0 30.07/9.23 active0(0) -> 0 30.07/9.23 __0(0, 0) -> 1 30.07/9.23 and0(0, 0) -> 2 30.07/9.23 proper0(0) -> 3 30.07/9.23 isList0(0) -> 4 30.07/9.23 isNeList0(0) -> 5 30.07/9.23 isQid0(0) -> 6 30.07/9.23 isNePal0(0) -> 7 30.07/9.23 isPal0(0) -> 8 30.07/9.23 top0(0) -> 9 30.07/9.23 __1(0, 0) -> 10 30.07/9.23 mark1(10) -> 1 30.07/9.23 and1(0, 0) -> 11 30.07/9.23 mark1(11) -> 2 30.07/9.23 nil1() -> 12 30.07/9.23 ok1(12) -> 3 30.07/9.23 tt1() -> 13 30.07/9.23 ok1(13) -> 3 30.07/9.23 a1() -> 14 30.07/9.23 ok1(14) -> 3 30.07/9.23 e1() -> 15 30.07/9.23 ok1(15) -> 3 30.07/9.23 i1() -> 16 30.07/9.23 ok1(16) -> 3 30.07/9.23 o1() -> 17 30.07/9.23 ok1(17) -> 3 30.07/9.23 u1() -> 18 30.07/9.23 ok1(18) -> 3 30.07/9.23 __1(0, 0) -> 19 30.07/9.23 ok1(19) -> 1 30.07/9.23 and1(0, 0) -> 20 30.07/9.23 ok1(20) -> 2 30.07/9.23 isList1(0) -> 21 30.07/9.23 ok1(21) -> 4 30.07/9.23 isNeList1(0) -> 22 30.07/9.23 ok1(22) -> 5 30.07/9.23 isQid1(0) -> 23 30.07/9.23 ok1(23) -> 6 30.07/9.23 isNePal1(0) -> 24 30.07/9.23 ok1(24) -> 7 30.07/9.23 isPal1(0) -> 25 30.07/9.23 ok1(25) -> 8 30.07/9.23 proper1(0) -> 26 30.07/9.23 top1(26) -> 9 30.07/9.23 active1(0) -> 27 30.07/9.23 top1(27) -> 9 30.07/9.23 mark1(10) -> 10 30.07/9.23 mark1(10) -> 19 30.07/9.23 mark1(11) -> 11 30.07/9.23 mark1(11) -> 20 30.07/9.23 ok1(12) -> 26 30.07/9.23 ok1(13) -> 26 30.07/9.23 ok1(14) -> 26 30.07/9.23 ok1(15) -> 26 30.07/9.23 ok1(16) -> 26 30.07/9.23 ok1(17) -> 26 30.07/9.23 ok1(18) -> 26 30.07/9.23 ok1(19) -> 10 30.07/9.23 ok1(19) -> 19 30.07/9.23 ok1(20) -> 11 30.07/9.23 ok1(20) -> 20 30.07/9.23 ok1(21) -> 21 30.07/9.23 ok1(22) -> 22 30.07/9.23 ok1(23) -> 23 30.07/9.23 ok1(24) -> 24 30.07/9.23 ok1(25) -> 25 30.07/9.23 active2(12) -> 28 30.07/9.23 top2(28) -> 9 30.07/9.23 active2(13) -> 28 30.07/9.23 active2(14) -> 28 30.07/9.23 active2(15) -> 28 30.07/9.23 active2(16) -> 28 30.07/9.23 active2(17) -> 28 30.07/9.23 active2(18) -> 28 30.07/9.23 30.07/9.23 ---------------------------------------- 30.07/9.23 30.07/9.23 (6) 30.07/9.23 BOUNDS(1, n^1) 30.07/9.23 30.07/9.23 ---------------------------------------- 30.07/9.24 30.07/9.24 (7) RenamingProof (BOTH BOUNDS(ID, ID)) 30.07/9.24 Renamed function symbols to avoid clashes with predefined symbol. 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (8) 30.07/9.24 Obligation: 30.07/9.24 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, INF). 30.07/9.24 30.07/9.24 30.07/9.24 The TRS R consists of the following rules: 30.07/9.24 30.07/9.24 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.24 active(__(X, nil)) -> mark(X) 30.07/9.24 active(__(nil, X)) -> mark(X) 30.07/9.24 active(and(tt, X)) -> mark(X) 30.07/9.24 active(isList(V)) -> mark(isNeList(V)) 30.07/9.24 active(isList(nil)) -> mark(tt) 30.07/9.24 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.24 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.24 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.24 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.24 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.24 active(isPal(nil)) -> mark(tt) 30.07/9.24 active(isQid(a)) -> mark(tt) 30.07/9.24 active(isQid(e)) -> mark(tt) 30.07/9.24 active(isQid(i)) -> mark(tt) 30.07/9.24 active(isQid(o)) -> mark(tt) 30.07/9.24 active(isQid(u)) -> mark(tt) 30.07/9.24 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.24 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.24 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.24 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.24 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.24 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.24 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.24 proper(nil) -> ok(nil) 30.07/9.24 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.24 proper(tt) -> ok(tt) 30.07/9.24 proper(isList(X)) -> isList(proper(X)) 30.07/9.24 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.24 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.24 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.24 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.24 proper(a) -> ok(a) 30.07/9.24 proper(e) -> ok(e) 30.07/9.24 proper(i) -> ok(i) 30.07/9.24 proper(o) -> ok(o) 30.07/9.24 proper(u) -> ok(u) 30.07/9.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.24 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.24 isList(ok(X)) -> ok(isList(X)) 30.07/9.24 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.24 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.24 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.24 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.24 top(mark(X)) -> top(proper(X)) 30.07/9.24 top(ok(X)) -> top(active(X)) 30.07/9.24 30.07/9.24 S is empty. 30.07/9.24 Rewrite Strategy: FULL 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (9) TypeInferenceProof (BOTH BOUNDS(ID, ID)) 30.07/9.24 Infered types. 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (10) 30.07/9.24 Obligation: 30.07/9.24 TRS: 30.07/9.24 Rules: 30.07/9.24 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.24 active(__(X, nil)) -> mark(X) 30.07/9.24 active(__(nil, X)) -> mark(X) 30.07/9.24 active(and(tt, X)) -> mark(X) 30.07/9.24 active(isList(V)) -> mark(isNeList(V)) 30.07/9.24 active(isList(nil)) -> mark(tt) 30.07/9.24 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.24 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.24 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.24 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.24 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.24 active(isPal(nil)) -> mark(tt) 30.07/9.24 active(isQid(a)) -> mark(tt) 30.07/9.24 active(isQid(e)) -> mark(tt) 30.07/9.24 active(isQid(i)) -> mark(tt) 30.07/9.24 active(isQid(o)) -> mark(tt) 30.07/9.24 active(isQid(u)) -> mark(tt) 30.07/9.24 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.24 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.24 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.24 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.24 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.24 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.24 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.24 proper(nil) -> ok(nil) 30.07/9.24 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.24 proper(tt) -> ok(tt) 30.07/9.24 proper(isList(X)) -> isList(proper(X)) 30.07/9.24 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.24 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.24 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.24 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.24 proper(a) -> ok(a) 30.07/9.24 proper(e) -> ok(e) 30.07/9.24 proper(i) -> ok(i) 30.07/9.24 proper(o) -> ok(o) 30.07/9.24 proper(u) -> ok(u) 30.07/9.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.24 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.24 isList(ok(X)) -> ok(isList(X)) 30.07/9.24 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.24 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.24 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.24 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.24 top(mark(X)) -> top(proper(X)) 30.07/9.24 top(ok(X)) -> top(active(X)) 30.07/9.24 30.07/9.24 Types: 30.07/9.24 active :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 __ :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 mark :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 nil :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 and :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 tt :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNeList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isQid :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNePal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isPal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 a :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 e :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 i :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 o :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 u :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 proper :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 ok :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 top :: mark:nil:tt:a:e:i:o:u:ok -> top 30.07/9.24 hole_mark:nil:tt:a:e:i:o:u:ok1_0 :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 hole_top2_0 :: top 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0 :: Nat -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (11) OrderProof (LOWER BOUND(ID)) 30.07/9.24 Heuristically decided to analyse the following defined symbols: 30.07/9.24 active, __, isNeList, and, isList, isQid, isPal, isNePal, proper, top 30.07/9.24 30.07/9.24 They will be analysed ascendingly in the following order: 30.07/9.24 __ < active 30.07/9.24 isNeList < active 30.07/9.24 and < active 30.07/9.24 isList < active 30.07/9.24 isQid < active 30.07/9.24 isPal < active 30.07/9.24 isNePal < active 30.07/9.24 active < top 30.07/9.24 __ < proper 30.07/9.24 isNeList < proper 30.07/9.24 and < proper 30.07/9.24 isList < proper 30.07/9.24 isQid < proper 30.07/9.24 isPal < proper 30.07/9.24 isNePal < proper 30.07/9.24 proper < top 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (12) 30.07/9.24 Obligation: 30.07/9.24 TRS: 30.07/9.24 Rules: 30.07/9.24 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.24 active(__(X, nil)) -> mark(X) 30.07/9.24 active(__(nil, X)) -> mark(X) 30.07/9.24 active(and(tt, X)) -> mark(X) 30.07/9.24 active(isList(V)) -> mark(isNeList(V)) 30.07/9.24 active(isList(nil)) -> mark(tt) 30.07/9.24 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.24 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.24 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.24 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.24 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.24 active(isPal(nil)) -> mark(tt) 30.07/9.24 active(isQid(a)) -> mark(tt) 30.07/9.24 active(isQid(e)) -> mark(tt) 30.07/9.24 active(isQid(i)) -> mark(tt) 30.07/9.24 active(isQid(o)) -> mark(tt) 30.07/9.24 active(isQid(u)) -> mark(tt) 30.07/9.24 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.24 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.24 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.24 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.24 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.24 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.24 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.24 proper(nil) -> ok(nil) 30.07/9.24 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.24 proper(tt) -> ok(tt) 30.07/9.24 proper(isList(X)) -> isList(proper(X)) 30.07/9.24 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.24 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.24 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.24 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.24 proper(a) -> ok(a) 30.07/9.24 proper(e) -> ok(e) 30.07/9.24 proper(i) -> ok(i) 30.07/9.24 proper(o) -> ok(o) 30.07/9.24 proper(u) -> ok(u) 30.07/9.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.24 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.24 isList(ok(X)) -> ok(isList(X)) 30.07/9.24 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.24 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.24 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.24 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.24 top(mark(X)) -> top(proper(X)) 30.07/9.24 top(ok(X)) -> top(active(X)) 30.07/9.24 30.07/9.24 Types: 30.07/9.24 active :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 __ :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 mark :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 nil :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 and :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 tt :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNeList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isQid :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNePal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isPal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 a :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 e :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 i :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 o :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 u :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 proper :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 ok :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 top :: mark:nil:tt:a:e:i:o:u:ok -> top 30.07/9.24 hole_mark:nil:tt:a:e:i:o:u:ok1_0 :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 hole_top2_0 :: top 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0 :: Nat -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 30.07/9.24 30.07/9.24 Generator Equations: 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(0) <=> nil 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(x, 1)) <=> mark(gen_mark:nil:tt:a:e:i:o:u:ok3_0(x)) 30.07/9.24 30.07/9.24 30.07/9.24 The following defined symbols remain to be analysed: 30.07/9.24 __, active, isNeList, and, isList, isQid, isPal, isNePal, proper, top 30.07/9.24 30.07/9.24 They will be analysed ascendingly in the following order: 30.07/9.24 __ < active 30.07/9.24 isNeList < active 30.07/9.24 and < active 30.07/9.24 isList < active 30.07/9.24 isQid < active 30.07/9.24 isPal < active 30.07/9.24 isNePal < active 30.07/9.24 active < top 30.07/9.24 __ < proper 30.07/9.24 isNeList < proper 30.07/9.24 and < proper 30.07/9.24 isList < proper 30.07/9.24 isQid < proper 30.07/9.24 isPal < proper 30.07/9.24 isNePal < proper 30.07/9.24 proper < top 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (13) RewriteLemmaProof (LOWER BOUND(ID)) 30.07/9.24 Proved the following rewrite lemma: 30.07/9.24 __(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n5_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 30.07/9.24 30.07/9.24 Induction Base: 30.07/9.24 __(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, 0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) 30.07/9.24 30.07/9.24 Induction Step: 30.07/9.24 __(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, +(n5_0, 1))), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) ->_R^Omega(1) 30.07/9.24 mark(__(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n5_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b))) ->_IH 30.07/9.24 mark(*4_0) 30.07/9.24 30.07/9.24 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (14) 30.07/9.24 Complex Obligation (BEST) 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (15) 30.07/9.24 Obligation: 30.07/9.24 Proved the lower bound n^1 for the following obligation: 30.07/9.24 30.07/9.24 TRS: 30.07/9.24 Rules: 30.07/9.24 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.24 active(__(X, nil)) -> mark(X) 30.07/9.24 active(__(nil, X)) -> mark(X) 30.07/9.24 active(and(tt, X)) -> mark(X) 30.07/9.24 active(isList(V)) -> mark(isNeList(V)) 30.07/9.24 active(isList(nil)) -> mark(tt) 30.07/9.24 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.24 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.24 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.24 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.24 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.24 active(isPal(nil)) -> mark(tt) 30.07/9.24 active(isQid(a)) -> mark(tt) 30.07/9.24 active(isQid(e)) -> mark(tt) 30.07/9.24 active(isQid(i)) -> mark(tt) 30.07/9.24 active(isQid(o)) -> mark(tt) 30.07/9.24 active(isQid(u)) -> mark(tt) 30.07/9.24 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.24 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.24 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.24 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.24 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.24 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.24 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.24 proper(nil) -> ok(nil) 30.07/9.24 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.24 proper(tt) -> ok(tt) 30.07/9.24 proper(isList(X)) -> isList(proper(X)) 30.07/9.24 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.24 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.24 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.24 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.24 proper(a) -> ok(a) 30.07/9.24 proper(e) -> ok(e) 30.07/9.24 proper(i) -> ok(i) 30.07/9.24 proper(o) -> ok(o) 30.07/9.24 proper(u) -> ok(u) 30.07/9.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.24 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.24 isList(ok(X)) -> ok(isList(X)) 30.07/9.24 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.24 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.24 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.24 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.24 top(mark(X)) -> top(proper(X)) 30.07/9.24 top(ok(X)) -> top(active(X)) 30.07/9.24 30.07/9.24 Types: 30.07/9.24 active :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 __ :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 mark :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 nil :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 and :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 tt :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNeList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isQid :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNePal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isPal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 a :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 e :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 i :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 o :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 u :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 proper :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 ok :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 top :: mark:nil:tt:a:e:i:o:u:ok -> top 30.07/9.24 hole_mark:nil:tt:a:e:i:o:u:ok1_0 :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 hole_top2_0 :: top 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0 :: Nat -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 30.07/9.24 30.07/9.24 Generator Equations: 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(0) <=> nil 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(x, 1)) <=> mark(gen_mark:nil:tt:a:e:i:o:u:ok3_0(x)) 30.07/9.24 30.07/9.24 30.07/9.24 The following defined symbols remain to be analysed: 30.07/9.24 __, active, isNeList, and, isList, isQid, isPal, isNePal, proper, top 30.07/9.24 30.07/9.24 They will be analysed ascendingly in the following order: 30.07/9.24 __ < active 30.07/9.24 isNeList < active 30.07/9.24 and < active 30.07/9.24 isList < active 30.07/9.24 isQid < active 30.07/9.24 isPal < active 30.07/9.24 isNePal < active 30.07/9.24 active < top 30.07/9.24 __ < proper 30.07/9.24 isNeList < proper 30.07/9.24 and < proper 30.07/9.24 isList < proper 30.07/9.24 isQid < proper 30.07/9.24 isPal < proper 30.07/9.24 isNePal < proper 30.07/9.24 proper < top 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (16) LowerBoundPropagationProof (FINISHED) 30.07/9.24 Propagated lower bound. 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (17) 30.07/9.24 BOUNDS(n^1, INF) 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (18) 30.07/9.24 Obligation: 30.07/9.24 TRS: 30.07/9.24 Rules: 30.07/9.24 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.24 active(__(X, nil)) -> mark(X) 30.07/9.24 active(__(nil, X)) -> mark(X) 30.07/9.24 active(and(tt, X)) -> mark(X) 30.07/9.24 active(isList(V)) -> mark(isNeList(V)) 30.07/9.24 active(isList(nil)) -> mark(tt) 30.07/9.24 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.24 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.24 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.24 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.24 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.24 active(isPal(nil)) -> mark(tt) 30.07/9.24 active(isQid(a)) -> mark(tt) 30.07/9.24 active(isQid(e)) -> mark(tt) 30.07/9.24 active(isQid(i)) -> mark(tt) 30.07/9.24 active(isQid(o)) -> mark(tt) 30.07/9.24 active(isQid(u)) -> mark(tt) 30.07/9.24 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.24 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.24 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.24 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.24 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.24 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.24 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.24 proper(nil) -> ok(nil) 30.07/9.24 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.24 proper(tt) -> ok(tt) 30.07/9.24 proper(isList(X)) -> isList(proper(X)) 30.07/9.24 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.24 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.24 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.24 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.24 proper(a) -> ok(a) 30.07/9.24 proper(e) -> ok(e) 30.07/9.24 proper(i) -> ok(i) 30.07/9.24 proper(o) -> ok(o) 30.07/9.24 proper(u) -> ok(u) 30.07/9.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.24 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.24 isList(ok(X)) -> ok(isList(X)) 30.07/9.24 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.24 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.24 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.24 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.24 top(mark(X)) -> top(proper(X)) 30.07/9.24 top(ok(X)) -> top(active(X)) 30.07/9.24 30.07/9.24 Types: 30.07/9.24 active :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 __ :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 mark :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 nil :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 and :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 tt :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNeList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isQid :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNePal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isPal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 a :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 e :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 i :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 o :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 u :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 proper :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 ok :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 top :: mark:nil:tt:a:e:i:o:u:ok -> top 30.07/9.24 hole_mark:nil:tt:a:e:i:o:u:ok1_0 :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 hole_top2_0 :: top 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0 :: Nat -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 30.07/9.24 30.07/9.24 Lemmas: 30.07/9.24 __(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n5_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 30.07/9.24 30.07/9.24 30.07/9.24 Generator Equations: 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(0) <=> nil 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(x, 1)) <=> mark(gen_mark:nil:tt:a:e:i:o:u:ok3_0(x)) 30.07/9.24 30.07/9.24 30.07/9.24 The following defined symbols remain to be analysed: 30.07/9.24 isNeList, active, and, isList, isQid, isPal, isNePal, proper, top 30.07/9.24 30.07/9.24 They will be analysed ascendingly in the following order: 30.07/9.24 isNeList < active 30.07/9.24 and < active 30.07/9.24 isList < active 30.07/9.24 isQid < active 30.07/9.24 isPal < active 30.07/9.24 isNePal < active 30.07/9.24 active < top 30.07/9.24 isNeList < proper 30.07/9.24 and < proper 30.07/9.24 isList < proper 30.07/9.24 isQid < proper 30.07/9.24 isPal < proper 30.07/9.24 isNePal < proper 30.07/9.24 proper < top 30.07/9.24 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (19) RewriteLemmaProof (LOWER BOUND(ID)) 30.07/9.24 Proved the following rewrite lemma: 30.07/9.24 and(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n1320_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) -> *4_0, rt in Omega(n1320_0) 30.07/9.24 30.07/9.24 Induction Base: 30.07/9.24 and(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, 0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) 30.07/9.24 30.07/9.24 Induction Step: 30.07/9.24 and(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, +(n1320_0, 1))), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) ->_R^Omega(1) 30.07/9.24 mark(and(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n1320_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b))) ->_IH 30.07/9.24 mark(*4_0) 30.07/9.24 30.07/9.24 We have rt in Omega(n^1) and sz in O(n). Thus, we have irc_R in Omega(n). 30.07/9.24 ---------------------------------------- 30.07/9.24 30.07/9.24 (20) 30.07/9.24 Obligation: 30.07/9.24 TRS: 30.07/9.24 Rules: 30.07/9.24 active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z))) 30.07/9.24 active(__(X, nil)) -> mark(X) 30.07/9.24 active(__(nil, X)) -> mark(X) 30.07/9.24 active(and(tt, X)) -> mark(X) 30.07/9.24 active(isList(V)) -> mark(isNeList(V)) 30.07/9.24 active(isList(nil)) -> mark(tt) 30.07/9.24 active(isList(__(V1, V2))) -> mark(and(isList(V1), isList(V2))) 30.07/9.24 active(isNeList(V)) -> mark(isQid(V)) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isList(V1), isNeList(V2))) 30.07/9.24 active(isNeList(__(V1, V2))) -> mark(and(isNeList(V1), isList(V2))) 30.07/9.24 active(isNePal(V)) -> mark(isQid(V)) 30.07/9.24 active(isNePal(__(I, __(P, I)))) -> mark(and(isQid(I), isPal(P))) 30.07/9.24 active(isPal(V)) -> mark(isNePal(V)) 30.07/9.24 active(isPal(nil)) -> mark(tt) 30.07/9.24 active(isQid(a)) -> mark(tt) 30.07/9.24 active(isQid(e)) -> mark(tt) 30.07/9.24 active(isQid(i)) -> mark(tt) 30.07/9.24 active(isQid(o)) -> mark(tt) 30.07/9.24 active(isQid(u)) -> mark(tt) 30.07/9.24 active(__(X1, X2)) -> __(active(X1), X2) 30.07/9.24 active(__(X1, X2)) -> __(X1, active(X2)) 30.07/9.24 active(and(X1, X2)) -> and(active(X1), X2) 30.07/9.24 __(mark(X1), X2) -> mark(__(X1, X2)) 30.07/9.24 __(X1, mark(X2)) -> mark(__(X1, X2)) 30.07/9.24 and(mark(X1), X2) -> mark(and(X1, X2)) 30.07/9.24 proper(__(X1, X2)) -> __(proper(X1), proper(X2)) 30.07/9.24 proper(nil) -> ok(nil) 30.07/9.24 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 30.07/9.24 proper(tt) -> ok(tt) 30.07/9.24 proper(isList(X)) -> isList(proper(X)) 30.07/9.24 proper(isNeList(X)) -> isNeList(proper(X)) 30.07/9.24 proper(isQid(X)) -> isQid(proper(X)) 30.07/9.24 proper(isNePal(X)) -> isNePal(proper(X)) 30.07/9.24 proper(isPal(X)) -> isPal(proper(X)) 30.07/9.24 proper(a) -> ok(a) 30.07/9.24 proper(e) -> ok(e) 30.07/9.24 proper(i) -> ok(i) 30.07/9.24 proper(o) -> ok(o) 30.07/9.24 proper(u) -> ok(u) 30.07/9.24 __(ok(X1), ok(X2)) -> ok(__(X1, X2)) 30.07/9.24 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 30.07/9.24 isList(ok(X)) -> ok(isList(X)) 30.07/9.24 isNeList(ok(X)) -> ok(isNeList(X)) 30.07/9.24 isQid(ok(X)) -> ok(isQid(X)) 30.07/9.24 isNePal(ok(X)) -> ok(isNePal(X)) 30.07/9.24 isPal(ok(X)) -> ok(isPal(X)) 30.07/9.24 top(mark(X)) -> top(proper(X)) 30.07/9.24 top(ok(X)) -> top(active(X)) 30.07/9.24 30.07/9.24 Types: 30.07/9.24 active :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 __ :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 mark :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 nil :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 and :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 tt :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNeList :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isQid :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isNePal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 isPal :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 a :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 e :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 i :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 o :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 u :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 proper :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 ok :: mark:nil:tt:a:e:i:o:u:ok -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 top :: mark:nil:tt:a:e:i:o:u:ok -> top 30.07/9.24 hole_mark:nil:tt:a:e:i:o:u:ok1_0 :: mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 hole_top2_0 :: top 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0 :: Nat -> mark:nil:tt:a:e:i:o:u:ok 30.07/9.24 30.07/9.24 30.07/9.24 Lemmas: 30.07/9.24 __(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n5_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) -> *4_0, rt in Omega(n5_0) 30.07/9.24 and(gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(1, n1320_0)), gen_mark:nil:tt:a:e:i:o:u:ok3_0(b)) -> *4_0, rt in Omega(n1320_0) 30.07/9.24 30.07/9.24 30.07/9.24 Generator Equations: 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(0) <=> nil 30.07/9.24 gen_mark:nil:tt:a:e:i:o:u:ok3_0(+(x, 1)) <=> mark(gen_mark:nil:tt:a:e:i:o:u:ok3_0(x)) 30.07/9.24 30.07/9.24 30.07/9.24 The following defined symbols remain to be analysed: 30.07/9.24 isList, active, isQid, isPal, isNePal, proper, top 30.07/9.24 30.07/9.24 They will be analysed ascendingly in the following order: 30.07/9.24 isList < active 30.07/9.24 isQid < active 30.07/9.24 isPal < active 30.07/9.24 isNePal < active 30.07/9.24 active < top 30.07/9.24 isList < proper 30.07/9.24 isQid < proper 30.07/9.24 isPal < proper 30.07/9.24 isNePal < proper 30.07/9.24 proper < top 30.46/11.94 EOF