1110.80/291.69 WORST_CASE(Omega(n^1), O(n^1)) 1110.80/291.70 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 1110.80/291.70 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 1110.80/291.70 1110.80/291.70 1110.80/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1110.80/291.70 1110.80/291.70 (0) CpxTRS 1110.80/291.70 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 1110.80/291.70 (2) CpxTRS 1110.80/291.70 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 1110.80/291.70 (4) CpxTRS 1110.80/291.70 (5) CpxTrsMatchBoundsTAProof [FINISHED, 882 ms] 1110.80/291.70 (6) BOUNDS(1, n^1) 1110.80/291.70 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 1110.80/291.70 (8) TRS for Loop Detection 1110.80/291.70 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 1110.80/291.70 (10) BEST 1110.80/291.70 (11) proven lower bound 1110.80/291.70 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 1110.80/291.70 (13) BOUNDS(n^1, INF) 1110.80/291.70 (14) TRS for Loop Detection 1110.80/291.70 1110.80/291.70 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (0) 1110.80/291.70 Obligation: 1110.80/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1110.80/291.70 1110.80/291.70 1110.80/291.70 The TRS R consists of the following rules: 1110.80/291.70 1110.80/291.70 active(zeros) -> mark(cons(0, zeros)) 1110.80/291.70 active(U11(tt, L)) -> mark(s(length(L))) 1110.80/291.70 active(and(tt, X)) -> mark(X) 1110.80/291.70 active(isNat(0)) -> mark(tt) 1110.80/291.70 active(isNat(length(V1))) -> mark(isNatList(V1)) 1110.80/291.70 active(isNat(s(V1))) -> mark(isNat(V1)) 1110.80/291.70 active(isNatIList(V)) -> mark(isNatList(V)) 1110.80/291.70 active(isNatIList(zeros)) -> mark(tt) 1110.80/291.70 active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2))) 1110.80/291.70 active(isNatList(nil)) -> mark(tt) 1110.80/291.70 active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2))) 1110.80/291.70 active(length(nil)) -> mark(0) 1110.80/291.70 active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L)) 1110.80/291.70 active(cons(X1, X2)) -> cons(active(X1), X2) 1110.80/291.70 active(U11(X1, X2)) -> U11(active(X1), X2) 1110.80/291.70 active(s(X)) -> s(active(X)) 1110.80/291.70 active(length(X)) -> length(active(X)) 1110.80/291.70 active(and(X1, X2)) -> and(active(X1), X2) 1110.80/291.70 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1110.80/291.70 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1110.80/291.70 s(mark(X)) -> mark(s(X)) 1110.80/291.70 length(mark(X)) -> mark(length(X)) 1110.80/291.70 and(mark(X1), X2) -> mark(and(X1, X2)) 1110.80/291.70 proper(zeros) -> ok(zeros) 1110.80/291.70 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1110.80/291.70 proper(0) -> ok(0) 1110.80/291.70 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1110.80/291.70 proper(tt) -> ok(tt) 1110.80/291.70 proper(s(X)) -> s(proper(X)) 1110.80/291.70 proper(length(X)) -> length(proper(X)) 1110.80/291.70 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1110.80/291.70 proper(isNat(X)) -> isNat(proper(X)) 1110.80/291.70 proper(isNatList(X)) -> isNatList(proper(X)) 1110.80/291.70 proper(isNatIList(X)) -> isNatIList(proper(X)) 1110.80/291.70 proper(nil) -> ok(nil) 1110.80/291.70 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1110.80/291.70 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1110.80/291.70 s(ok(X)) -> ok(s(X)) 1110.80/291.70 length(ok(X)) -> ok(length(X)) 1110.80/291.70 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1110.80/291.70 isNat(ok(X)) -> ok(isNat(X)) 1110.80/291.70 isNatList(ok(X)) -> ok(isNatList(X)) 1110.80/291.70 isNatIList(ok(X)) -> ok(isNatIList(X)) 1110.80/291.70 top(mark(X)) -> top(proper(X)) 1110.80/291.70 top(ok(X)) -> top(active(X)) 1110.80/291.70 1110.80/291.70 S is empty. 1110.80/291.70 Rewrite Strategy: FULL 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 1110.80/291.70 The following defined symbols can occur below the 0th argument of cons: active, proper, cons 1110.80/291.70 The following defined symbols can occur below the 1th argument of cons: active, proper, cons 1110.80/291.70 The following defined symbols can occur below the 0th argument of top: active, proper, cons 1110.80/291.70 The following defined symbols can occur below the 0th argument of proper: active, proper, cons 1110.80/291.70 The following defined symbols can occur below the 0th argument of active: active, proper, cons 1110.80/291.70 1110.80/291.70 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 1110.80/291.70 active(U11(tt, L)) -> mark(s(length(L))) 1110.80/291.70 active(and(tt, X)) -> mark(X) 1110.80/291.70 active(isNat(0)) -> mark(tt) 1110.80/291.70 active(isNat(length(V1))) -> mark(isNatList(V1)) 1110.80/291.70 active(isNat(s(V1))) -> mark(isNat(V1)) 1110.80/291.70 active(isNatIList(V)) -> mark(isNatList(V)) 1110.80/291.70 active(isNatIList(zeros)) -> mark(tt) 1110.80/291.70 active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2))) 1110.80/291.70 active(isNatList(nil)) -> mark(tt) 1110.80/291.70 active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2))) 1110.80/291.70 active(length(nil)) -> mark(0) 1110.80/291.70 active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L)) 1110.80/291.70 active(U11(X1, X2)) -> U11(active(X1), X2) 1110.80/291.70 active(s(X)) -> s(active(X)) 1110.80/291.70 active(length(X)) -> length(active(X)) 1110.80/291.70 active(and(X1, X2)) -> and(active(X1), X2) 1110.80/291.70 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1110.80/291.70 proper(s(X)) -> s(proper(X)) 1110.80/291.70 proper(length(X)) -> length(proper(X)) 1110.80/291.70 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1110.80/291.70 proper(isNat(X)) -> isNat(proper(X)) 1110.80/291.70 proper(isNatList(X)) -> isNatList(proper(X)) 1110.80/291.70 proper(isNatIList(X)) -> isNatIList(proper(X)) 1110.80/291.70 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (2) 1110.80/291.70 Obligation: 1110.80/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 1110.80/291.70 1110.80/291.70 1110.80/291.70 The TRS R consists of the following rules: 1110.80/291.70 1110.80/291.70 active(zeros) -> mark(cons(0, zeros)) 1110.80/291.70 active(cons(X1, X2)) -> cons(active(X1), X2) 1110.80/291.70 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1110.80/291.70 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1110.80/291.70 s(mark(X)) -> mark(s(X)) 1110.80/291.70 length(mark(X)) -> mark(length(X)) 1110.80/291.70 and(mark(X1), X2) -> mark(and(X1, X2)) 1110.80/291.70 proper(zeros) -> ok(zeros) 1110.80/291.70 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1110.80/291.70 proper(0) -> ok(0) 1110.80/291.70 proper(tt) -> ok(tt) 1110.80/291.70 proper(nil) -> ok(nil) 1110.80/291.70 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1110.80/291.70 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1110.80/291.70 s(ok(X)) -> ok(s(X)) 1110.80/291.70 length(ok(X)) -> ok(length(X)) 1110.80/291.70 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1110.80/291.70 isNat(ok(X)) -> ok(isNat(X)) 1110.80/291.70 isNatList(ok(X)) -> ok(isNatList(X)) 1110.80/291.70 isNatIList(ok(X)) -> ok(isNatIList(X)) 1110.80/291.70 top(mark(X)) -> top(proper(X)) 1110.80/291.70 top(ok(X)) -> top(active(X)) 1110.80/291.70 1110.80/291.70 S is empty. 1110.80/291.70 Rewrite Strategy: FULL 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 1110.80/291.70 transformed relative TRS to TRS 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (4) 1110.80/291.70 Obligation: 1110.80/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 1110.80/291.70 1110.80/291.70 1110.80/291.70 The TRS R consists of the following rules: 1110.80/291.70 1110.80/291.70 active(zeros) -> mark(cons(0, zeros)) 1110.80/291.70 active(cons(X1, X2)) -> cons(active(X1), X2) 1110.80/291.70 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1110.80/291.70 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1110.80/291.70 s(mark(X)) -> mark(s(X)) 1110.80/291.70 length(mark(X)) -> mark(length(X)) 1110.80/291.70 and(mark(X1), X2) -> mark(and(X1, X2)) 1110.80/291.70 proper(zeros) -> ok(zeros) 1110.80/291.70 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1110.80/291.70 proper(0) -> ok(0) 1110.80/291.70 proper(tt) -> ok(tt) 1110.80/291.70 proper(nil) -> ok(nil) 1110.80/291.70 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1110.80/291.70 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1110.80/291.70 s(ok(X)) -> ok(s(X)) 1110.80/291.70 length(ok(X)) -> ok(length(X)) 1110.80/291.70 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1110.80/291.70 isNat(ok(X)) -> ok(isNat(X)) 1110.80/291.70 isNatList(ok(X)) -> ok(isNatList(X)) 1110.80/291.70 isNatIList(ok(X)) -> ok(isNatIList(X)) 1110.80/291.70 top(mark(X)) -> top(proper(X)) 1110.80/291.70 top(ok(X)) -> top(active(X)) 1110.80/291.70 1110.80/291.70 S is empty. 1110.80/291.70 Rewrite Strategy: FULL 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (5) CpxTrsMatchBoundsTAProof (FINISHED) 1110.80/291.70 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 5. 1110.80/291.70 1110.80/291.70 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 1110.80/291.70 final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] 1110.80/291.70 transitions: 1110.80/291.70 zeros0() -> 0 1110.80/291.70 mark0(0) -> 0 1110.80/291.70 00() -> 0 1110.80/291.70 ok0(0) -> 0 1110.80/291.70 tt0() -> 0 1110.80/291.70 nil0() -> 0 1110.80/291.70 active0(0) -> 1 1110.80/291.70 cons0(0, 0) -> 2 1110.80/291.70 U110(0, 0) -> 3 1110.80/291.70 s0(0) -> 4 1110.80/291.70 length0(0) -> 5 1110.80/291.70 and0(0, 0) -> 6 1110.80/291.70 proper0(0) -> 7 1110.80/291.70 isNat0(0) -> 8 1110.80/291.70 isNatList0(0) -> 9 1110.80/291.70 isNatIList0(0) -> 10 1110.80/291.70 top0(0) -> 11 1110.80/291.70 01() -> 13 1110.80/291.70 zeros1() -> 14 1110.80/291.70 cons1(13, 14) -> 12 1110.80/291.70 mark1(12) -> 1 1110.80/291.70 cons1(0, 0) -> 15 1110.80/291.70 mark1(15) -> 2 1110.80/291.70 U111(0, 0) -> 16 1110.80/291.70 mark1(16) -> 3 1110.80/291.70 s1(0) -> 17 1110.80/291.70 mark1(17) -> 4 1110.80/291.70 length1(0) -> 18 1110.80/291.70 mark1(18) -> 5 1110.80/291.70 and1(0, 0) -> 19 1110.80/291.70 mark1(19) -> 6 1110.80/291.70 zeros1() -> 20 1110.80/291.70 ok1(20) -> 7 1110.80/291.70 01() -> 21 1110.80/291.70 ok1(21) -> 7 1110.80/291.70 tt1() -> 22 1110.80/291.70 ok1(22) -> 7 1110.80/291.70 nil1() -> 23 1110.80/291.70 ok1(23) -> 7 1110.80/291.70 cons1(0, 0) -> 24 1110.80/291.70 ok1(24) -> 2 1110.80/291.70 U111(0, 0) -> 25 1110.80/291.70 ok1(25) -> 3 1110.80/291.70 s1(0) -> 26 1110.80/291.70 ok1(26) -> 4 1110.80/291.70 length1(0) -> 27 1110.80/291.70 ok1(27) -> 5 1110.80/291.70 and1(0, 0) -> 28 1110.80/291.70 ok1(28) -> 6 1110.80/291.70 isNat1(0) -> 29 1110.80/291.70 ok1(29) -> 8 1110.80/291.70 isNatList1(0) -> 30 1110.80/291.70 ok1(30) -> 9 1110.80/291.70 isNatIList1(0) -> 31 1110.80/291.70 ok1(31) -> 10 1110.80/291.70 proper1(0) -> 32 1110.80/291.70 top1(32) -> 11 1110.80/291.70 active1(0) -> 33 1110.80/291.70 top1(33) -> 11 1110.80/291.70 mark1(12) -> 33 1110.80/291.70 mark1(15) -> 15 1110.80/291.70 mark1(15) -> 24 1110.80/291.70 mark1(16) -> 16 1110.80/291.70 mark1(16) -> 25 1110.80/291.70 mark1(17) -> 17 1110.80/291.70 mark1(17) -> 26 1110.80/291.70 mark1(18) -> 18 1110.80/291.70 mark1(18) -> 27 1110.80/291.70 mark1(19) -> 19 1110.80/291.70 mark1(19) -> 28 1110.80/291.70 ok1(20) -> 32 1110.80/291.70 ok1(21) -> 32 1110.80/291.70 ok1(22) -> 32 1110.80/291.70 ok1(23) -> 32 1110.80/291.70 ok1(24) -> 15 1110.80/291.70 ok1(24) -> 24 1110.80/291.70 ok1(25) -> 16 1110.80/291.70 ok1(25) -> 25 1110.80/291.70 ok1(26) -> 17 1110.80/291.70 ok1(26) -> 26 1110.80/291.70 ok1(27) -> 18 1110.80/291.70 ok1(27) -> 27 1110.80/291.70 ok1(28) -> 19 1110.80/291.70 ok1(28) -> 28 1110.80/291.70 ok1(29) -> 29 1110.80/291.70 ok1(30) -> 30 1110.80/291.70 ok1(31) -> 31 1110.80/291.70 proper2(12) -> 34 1110.80/291.70 top2(34) -> 11 1110.80/291.70 active2(20) -> 35 1110.80/291.70 top2(35) -> 11 1110.80/291.70 active2(21) -> 35 1110.80/291.70 active2(22) -> 35 1110.80/291.70 active2(23) -> 35 1110.80/291.70 02() -> 37 1110.80/291.70 zeros2() -> 38 1110.80/291.70 cons2(37, 38) -> 36 1110.80/291.70 mark2(36) -> 35 1110.80/291.70 proper2(13) -> 39 1110.80/291.70 proper2(14) -> 40 1110.80/291.70 cons2(39, 40) -> 34 1110.80/291.70 zeros2() -> 41 1110.80/291.70 ok2(41) -> 40 1110.80/291.70 02() -> 42 1110.80/291.70 ok2(42) -> 39 1110.80/291.70 proper3(36) -> 43 1110.80/291.70 top3(43) -> 11 1110.80/291.70 proper3(37) -> 44 1110.80/291.70 proper3(38) -> 45 1110.80/291.70 cons3(44, 45) -> 43 1110.80/291.70 cons3(42, 41) -> 46 1110.80/291.70 ok3(46) -> 34 1110.80/291.70 zeros3() -> 47 1110.80/291.70 ok3(47) -> 45 1110.80/291.70 03() -> 48 1110.80/291.70 ok3(48) -> 44 1110.80/291.70 active3(46) -> 49 1110.80/291.70 top3(49) -> 11 1110.80/291.70 cons4(48, 47) -> 50 1110.80/291.70 ok4(50) -> 43 1110.80/291.70 active4(42) -> 51 1110.80/291.70 cons4(51, 41) -> 49 1110.80/291.70 active4(50) -> 52 1110.80/291.70 top4(52) -> 11 1110.80/291.70 active5(48) -> 53 1110.80/291.70 cons5(53, 47) -> 52 1110.80/291.70 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (6) 1110.80/291.70 BOUNDS(1, n^1) 1110.80/291.70 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 1110.80/291.70 Transformed a relative TRS into a decreasing-loop problem. 1110.80/291.70 ---------------------------------------- 1110.80/291.70 1110.80/291.70 (8) 1110.80/291.70 Obligation: 1110.80/291.70 Analyzing the following TRS for decreasing loops: 1110.80/291.70 1110.80/291.70 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1110.80/291.70 1110.80/291.70 1110.80/291.70 The TRS R consists of the following rules: 1110.80/291.70 1110.80/291.70 active(zeros) -> mark(cons(0, zeros)) 1110.80/291.70 active(U11(tt, L)) -> mark(s(length(L))) 1110.80/291.70 active(and(tt, X)) -> mark(X) 1110.80/291.70 active(isNat(0)) -> mark(tt) 1110.80/291.70 active(isNat(length(V1))) -> mark(isNatList(V1)) 1110.80/291.70 active(isNat(s(V1))) -> mark(isNat(V1)) 1110.80/291.70 active(isNatIList(V)) -> mark(isNatList(V)) 1110.80/291.70 active(isNatIList(zeros)) -> mark(tt) 1110.80/291.70 active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2))) 1110.80/291.70 active(isNatList(nil)) -> mark(tt) 1110.80/291.70 active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2))) 1110.80/291.70 active(length(nil)) -> mark(0) 1110.80/291.70 active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L)) 1110.80/291.70 active(cons(X1, X2)) -> cons(active(X1), X2) 1110.80/291.70 active(U11(X1, X2)) -> U11(active(X1), X2) 1110.80/291.70 active(s(X)) -> s(active(X)) 1110.80/291.70 active(length(X)) -> length(active(X)) 1110.80/291.70 active(and(X1, X2)) -> and(active(X1), X2) 1110.80/291.70 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1110.80/291.70 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1110.80/291.70 s(mark(X)) -> mark(s(X)) 1110.80/291.70 length(mark(X)) -> mark(length(X)) 1110.80/291.70 and(mark(X1), X2) -> mark(and(X1, X2)) 1110.80/291.70 proper(zeros) -> ok(zeros) 1110.80/291.70 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1110.80/291.70 proper(0) -> ok(0) 1110.80/291.70 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1110.80/291.70 proper(tt) -> ok(tt) 1110.80/291.70 proper(s(X)) -> s(proper(X)) 1110.80/291.70 proper(length(X)) -> length(proper(X)) 1110.80/291.70 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1110.80/291.70 proper(isNat(X)) -> isNat(proper(X)) 1110.80/291.70 proper(isNatList(X)) -> isNatList(proper(X)) 1110.80/291.70 proper(isNatIList(X)) -> isNatIList(proper(X)) 1110.80/291.70 proper(nil) -> ok(nil) 1110.80/291.70 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1110.80/291.70 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1110.80/291.70 s(ok(X)) -> ok(s(X)) 1110.80/291.70 length(ok(X)) -> ok(length(X)) 1110.80/291.70 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1110.80/291.71 isNat(ok(X)) -> ok(isNat(X)) 1110.80/291.71 isNatList(ok(X)) -> ok(isNatList(X)) 1110.80/291.71 isNatIList(ok(X)) -> ok(isNatIList(X)) 1110.80/291.71 top(mark(X)) -> top(proper(X)) 1110.80/291.71 top(ok(X)) -> top(active(X)) 1110.80/291.71 1110.80/291.71 S is empty. 1110.80/291.71 Rewrite Strategy: FULL 1110.80/291.71 ---------------------------------------- 1110.80/291.71 1110.80/291.71 (9) DecreasingLoopProof (LOWER BOUND(ID)) 1110.80/291.71 The following loop(s) give(s) rise to the lower bound Omega(n^1): 1110.80/291.71 1110.80/291.71 The rewrite sequence 1110.80/291.71 1110.80/291.71 isNatIList(ok(X)) ->^+ ok(isNatIList(X)) 1110.80/291.71 1110.80/291.71 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 1110.80/291.71 1110.80/291.71 The pumping substitution is [X / ok(X)]. 1110.80/291.71 1110.80/291.71 The result substitution is [ ]. 1110.80/291.71 1110.80/291.71 1110.80/291.71 1110.80/291.71 1110.80/291.71 ---------------------------------------- 1110.80/291.71 1110.80/291.71 (10) 1110.80/291.71 Complex Obligation (BEST) 1110.80/291.71 1110.80/291.71 ---------------------------------------- 1110.80/291.71 1110.80/291.71 (11) 1110.80/291.71 Obligation: 1110.80/291.71 Proved the lower bound n^1 for the following obligation: 1110.80/291.71 1110.80/291.71 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1110.80/291.71 1110.80/291.71 1110.80/291.71 The TRS R consists of the following rules: 1110.80/291.71 1110.80/291.71 active(zeros) -> mark(cons(0, zeros)) 1110.80/291.71 active(U11(tt, L)) -> mark(s(length(L))) 1110.80/291.71 active(and(tt, X)) -> mark(X) 1110.80/291.71 active(isNat(0)) -> mark(tt) 1110.80/291.71 active(isNat(length(V1))) -> mark(isNatList(V1)) 1110.80/291.71 active(isNat(s(V1))) -> mark(isNat(V1)) 1110.80/291.71 active(isNatIList(V)) -> mark(isNatList(V)) 1110.80/291.71 active(isNatIList(zeros)) -> mark(tt) 1110.80/291.71 active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2))) 1110.80/291.71 active(isNatList(nil)) -> mark(tt) 1110.80/291.71 active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2))) 1110.80/291.71 active(length(nil)) -> mark(0) 1110.80/291.71 active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L)) 1110.80/291.71 active(cons(X1, X2)) -> cons(active(X1), X2) 1110.80/291.71 active(U11(X1, X2)) -> U11(active(X1), X2) 1110.80/291.71 active(s(X)) -> s(active(X)) 1110.80/291.71 active(length(X)) -> length(active(X)) 1110.80/291.71 active(and(X1, X2)) -> and(active(X1), X2) 1110.80/291.71 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1110.80/291.71 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1110.80/291.71 s(mark(X)) -> mark(s(X)) 1110.80/291.71 length(mark(X)) -> mark(length(X)) 1110.80/291.71 and(mark(X1), X2) -> mark(and(X1, X2)) 1110.80/291.71 proper(zeros) -> ok(zeros) 1110.80/291.71 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1110.80/291.71 proper(0) -> ok(0) 1110.80/291.71 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1110.80/291.71 proper(tt) -> ok(tt) 1110.80/291.71 proper(s(X)) -> s(proper(X)) 1110.80/291.71 proper(length(X)) -> length(proper(X)) 1110.80/291.71 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1110.80/291.71 proper(isNat(X)) -> isNat(proper(X)) 1110.80/291.71 proper(isNatList(X)) -> isNatList(proper(X)) 1110.80/291.71 proper(isNatIList(X)) -> isNatIList(proper(X)) 1110.80/291.71 proper(nil) -> ok(nil) 1110.80/291.71 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1110.80/291.71 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1110.80/291.71 s(ok(X)) -> ok(s(X)) 1110.80/291.71 length(ok(X)) -> ok(length(X)) 1110.80/291.71 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1110.80/291.71 isNat(ok(X)) -> ok(isNat(X)) 1110.80/291.71 isNatList(ok(X)) -> ok(isNatList(X)) 1110.80/291.71 isNatIList(ok(X)) -> ok(isNatIList(X)) 1110.80/291.71 top(mark(X)) -> top(proper(X)) 1110.80/291.71 top(ok(X)) -> top(active(X)) 1110.80/291.71 1110.80/291.71 S is empty. 1110.80/291.71 Rewrite Strategy: FULL 1110.80/291.71 ---------------------------------------- 1110.80/291.71 1110.80/291.71 (12) LowerBoundPropagationProof (FINISHED) 1110.80/291.71 Propagated lower bound. 1110.80/291.71 ---------------------------------------- 1110.80/291.71 1110.80/291.71 (13) 1110.80/291.71 BOUNDS(n^1, INF) 1110.80/291.71 1110.80/291.71 ---------------------------------------- 1110.80/291.71 1110.80/291.71 (14) 1110.80/291.71 Obligation: 1110.80/291.71 Analyzing the following TRS for decreasing loops: 1110.80/291.71 1110.80/291.71 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 1110.80/291.71 1110.80/291.71 1110.80/291.71 The TRS R consists of the following rules: 1110.80/291.71 1110.80/291.71 active(zeros) -> mark(cons(0, zeros)) 1110.80/291.71 active(U11(tt, L)) -> mark(s(length(L))) 1110.80/291.71 active(and(tt, X)) -> mark(X) 1110.80/291.71 active(isNat(0)) -> mark(tt) 1110.80/291.71 active(isNat(length(V1))) -> mark(isNatList(V1)) 1110.80/291.71 active(isNat(s(V1))) -> mark(isNat(V1)) 1110.80/291.71 active(isNatIList(V)) -> mark(isNatList(V)) 1110.80/291.71 active(isNatIList(zeros)) -> mark(tt) 1110.80/291.71 active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2))) 1110.80/291.71 active(isNatList(nil)) -> mark(tt) 1110.80/291.71 active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2))) 1110.80/291.71 active(length(nil)) -> mark(0) 1110.80/291.71 active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L)) 1110.80/291.71 active(cons(X1, X2)) -> cons(active(X1), X2) 1110.80/291.71 active(U11(X1, X2)) -> U11(active(X1), X2) 1110.80/291.71 active(s(X)) -> s(active(X)) 1110.80/291.71 active(length(X)) -> length(active(X)) 1110.80/291.71 active(and(X1, X2)) -> and(active(X1), X2) 1110.80/291.71 cons(mark(X1), X2) -> mark(cons(X1, X2)) 1110.80/291.71 U11(mark(X1), X2) -> mark(U11(X1, X2)) 1110.80/291.71 s(mark(X)) -> mark(s(X)) 1110.80/291.71 length(mark(X)) -> mark(length(X)) 1110.80/291.71 and(mark(X1), X2) -> mark(and(X1, X2)) 1110.80/291.71 proper(zeros) -> ok(zeros) 1110.80/291.71 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 1110.80/291.71 proper(0) -> ok(0) 1110.80/291.71 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 1110.80/291.71 proper(tt) -> ok(tt) 1110.80/291.71 proper(s(X)) -> s(proper(X)) 1110.80/291.71 proper(length(X)) -> length(proper(X)) 1110.80/291.71 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 1110.80/291.71 proper(isNat(X)) -> isNat(proper(X)) 1110.80/291.71 proper(isNatList(X)) -> isNatList(proper(X)) 1110.80/291.71 proper(isNatIList(X)) -> isNatIList(proper(X)) 1110.80/291.71 proper(nil) -> ok(nil) 1110.80/291.71 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 1110.80/291.71 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 1110.80/291.71 s(ok(X)) -> ok(s(X)) 1110.80/291.71 length(ok(X)) -> ok(length(X)) 1110.80/291.71 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 1110.80/291.71 isNat(ok(X)) -> ok(isNat(X)) 1110.80/291.71 isNatList(ok(X)) -> ok(isNatList(X)) 1110.80/291.71 isNatIList(ok(X)) -> ok(isNatIList(X)) 1110.80/291.71 top(mark(X)) -> top(proper(X)) 1110.80/291.71 top(ok(X)) -> top(active(X)) 1110.80/291.71 1110.80/291.71 S is empty. 1110.80/291.71 Rewrite Strategy: FULL 1111.10/291.79 EOF