27.96/8.12 WORST_CASE(Omega(n^1), O(n^1)) 28.34/8.13 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 28.34/8.13 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 28.34/8.13 28.34/8.13 28.34/8.13 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 28.34/8.13 28.34/8.13 (0) CpxTRS 28.34/8.13 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 8 ms] 28.34/8.13 (2) CpxTRS 28.34/8.13 (3) RelTrsToTrsProof [UPPER BOUND(ID), 0 ms] 28.34/8.13 (4) CpxTRS 28.34/8.13 (5) CpxTrsMatchBoundsTAProof [FINISHED, 339 ms] 28.34/8.13 (6) BOUNDS(1, n^1) 28.34/8.13 (7) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 28.34/8.13 (8) TRS for Loop Detection 28.34/8.13 (9) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 28.34/8.13 (10) BEST 28.34/8.13 (11) proven lower bound 28.34/8.13 (12) LowerBoundPropagationProof [FINISHED, 0 ms] 28.34/8.13 (13) BOUNDS(n^1, INF) 28.34/8.13 (14) TRS for Loop Detection 28.34/8.13 28.34/8.13 28.34/8.13 ---------------------------------------- 28.34/8.13 28.34/8.13 (0) 28.34/8.13 Obligation: 28.34/8.13 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 28.34/8.13 28.34/8.13 28.34/8.13 The TRS R consists of the following rules: 28.34/8.13 28.34/8.13 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 28.34/8.13 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 28.34/8.13 active(U13(tt)) -> mark(tt) 28.34/8.13 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 28.34/8.13 active(U22(tt)) -> mark(tt) 28.34/8.13 active(U31(tt, N)) -> mark(N) 28.34/8.13 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 28.34/8.13 active(and(tt, X)) -> mark(X) 28.34/8.13 active(isNat(0)) -> mark(tt) 28.34/8.13 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 28.34/8.13 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 28.34/8.13 active(isNatKind(0)) -> mark(tt) 28.34/8.13 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 28.34/8.13 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 28.34/8.13 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 28.34/8.13 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 28.34/8.13 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 28.34/8.13 active(U12(X1, X2)) -> U12(active(X1), X2) 28.34/8.13 active(U13(X)) -> U13(active(X)) 28.34/8.13 active(U21(X1, X2)) -> U21(active(X1), X2) 28.34/8.13 active(U22(X)) -> U22(active(X)) 28.34/8.13 active(U31(X1, X2)) -> U31(active(X1), X2) 28.34/8.13 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 28.34/8.13 active(s(X)) -> s(active(X)) 28.34/8.13 active(plus(X1, X2)) -> plus(active(X1), X2) 28.34/8.13 active(plus(X1, X2)) -> plus(X1, active(X2)) 28.34/8.13 active(and(X1, X2)) -> and(active(X1), X2) 28.34/8.13 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 28.34/8.13 U12(mark(X1), X2) -> mark(U12(X1, X2)) 28.34/8.13 U13(mark(X)) -> mark(U13(X)) 28.34/8.13 U21(mark(X1), X2) -> mark(U21(X1, X2)) 28.34/8.13 U22(mark(X)) -> mark(U22(X)) 28.34/8.13 U31(mark(X1), X2) -> mark(U31(X1, X2)) 28.34/8.13 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 28.34/8.13 s(mark(X)) -> mark(s(X)) 28.34/8.13 plus(mark(X1), X2) -> mark(plus(X1, X2)) 28.34/8.13 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 28.34/8.13 and(mark(X1), X2) -> mark(and(X1, X2)) 28.34/8.13 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 28.34/8.13 proper(tt) -> ok(tt) 28.34/8.13 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 28.34/8.13 proper(isNat(X)) -> isNat(proper(X)) 28.34/8.13 proper(U13(X)) -> U13(proper(X)) 28.34/8.13 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 28.34/8.13 proper(U22(X)) -> U22(proper(X)) 28.34/8.13 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 28.34/8.13 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 28.34/8.13 proper(s(X)) -> s(proper(X)) 28.34/8.13 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 28.34/8.13 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 28.34/8.13 proper(0) -> ok(0) 28.34/8.13 proper(isNatKind(X)) -> isNatKind(proper(X)) 28.34/8.13 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 28.34/8.13 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 28.34/8.13 isNat(ok(X)) -> ok(isNat(X)) 28.34/8.13 U13(ok(X)) -> ok(U13(X)) 28.34/8.13 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 28.34/8.13 U22(ok(X)) -> ok(U22(X)) 28.34/8.13 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 28.34/8.13 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 28.34/8.13 s(ok(X)) -> ok(s(X)) 28.34/8.13 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 28.34/8.13 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 28.34/8.13 isNatKind(ok(X)) -> ok(isNatKind(X)) 28.34/8.13 top(mark(X)) -> top(proper(X)) 28.34/8.13 top(ok(X)) -> top(active(X)) 28.34/8.13 28.34/8.13 S is empty. 28.34/8.13 Rewrite Strategy: FULL 28.34/8.13 ---------------------------------------- 28.34/8.13 28.34/8.13 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 28.34/8.13 The following defined symbols can occur below the 0th argument of top: proper, active 28.34/8.14 The following defined symbols can occur below the 0th argument of proper: proper, active 28.34/8.14 The following defined symbols can occur below the 0th argument of active: proper, active 28.34/8.14 28.34/8.14 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 28.34/8.14 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 28.34/8.14 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 28.34/8.14 active(U13(tt)) -> mark(tt) 28.34/8.14 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 28.34/8.14 active(U22(tt)) -> mark(tt) 28.34/8.14 active(U31(tt, N)) -> mark(N) 28.34/8.14 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 28.34/8.14 active(and(tt, X)) -> mark(X) 28.34/8.14 active(isNat(0)) -> mark(tt) 28.34/8.14 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 28.34/8.14 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 28.34/8.14 active(isNatKind(0)) -> mark(tt) 28.34/8.14 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 28.34/8.14 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 28.34/8.14 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 28.34/8.14 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 28.34/8.14 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 28.34/8.14 active(U12(X1, X2)) -> U12(active(X1), X2) 28.34/8.14 active(U13(X)) -> U13(active(X)) 28.34/8.14 active(U21(X1, X2)) -> U21(active(X1), X2) 28.34/8.14 active(U22(X)) -> U22(active(X)) 28.34/8.14 active(U31(X1, X2)) -> U31(active(X1), X2) 28.34/8.14 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 28.34/8.14 active(s(X)) -> s(active(X)) 28.34/8.14 active(plus(X1, X2)) -> plus(active(X1), X2) 28.34/8.14 active(plus(X1, X2)) -> plus(X1, active(X2)) 28.34/8.14 active(and(X1, X2)) -> and(active(X1), X2) 28.34/8.14 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 28.34/8.14 proper(isNat(X)) -> isNat(proper(X)) 28.34/8.14 proper(U13(X)) -> U13(proper(X)) 28.34/8.14 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 28.34/8.14 proper(U22(X)) -> U22(proper(X)) 28.34/8.14 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 28.34/8.14 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(s(X)) -> s(proper(X)) 28.34/8.14 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 28.34/8.14 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 28.34/8.14 proper(isNatKind(X)) -> isNatKind(proper(X)) 28.34/8.14 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (2) 28.34/8.14 Obligation: 28.34/8.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 28.34/8.14 28.34/8.14 28.34/8.14 The TRS R consists of the following rules: 28.34/8.14 28.34/8.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 28.34/8.14 U12(mark(X1), X2) -> mark(U12(X1, X2)) 28.34/8.14 U13(mark(X)) -> mark(U13(X)) 28.34/8.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 28.34/8.14 U22(mark(X)) -> mark(U22(X)) 28.34/8.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 28.34/8.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 28.34/8.14 s(mark(X)) -> mark(s(X)) 28.34/8.14 plus(mark(X1), X2) -> mark(plus(X1, X2)) 28.34/8.14 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 28.34/8.14 and(mark(X1), X2) -> mark(and(X1, X2)) 28.34/8.14 proper(tt) -> ok(tt) 28.34/8.14 proper(0) -> ok(0) 28.34/8.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 28.34/8.14 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 28.34/8.14 isNat(ok(X)) -> ok(isNat(X)) 28.34/8.14 U13(ok(X)) -> ok(U13(X)) 28.34/8.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 28.34/8.14 U22(ok(X)) -> ok(U22(X)) 28.34/8.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 28.34/8.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 28.34/8.14 s(ok(X)) -> ok(s(X)) 28.34/8.14 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 28.34/8.14 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 28.34/8.14 isNatKind(ok(X)) -> ok(isNatKind(X)) 28.34/8.14 top(mark(X)) -> top(proper(X)) 28.34/8.14 top(ok(X)) -> top(active(X)) 28.34/8.14 28.34/8.14 S is empty. 28.34/8.14 Rewrite Strategy: FULL 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (3) RelTrsToTrsProof (UPPER BOUND(ID)) 28.34/8.14 transformed relative TRS to TRS 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (4) 28.34/8.14 Obligation: 28.34/8.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 28.34/8.14 28.34/8.14 28.34/8.14 The TRS R consists of the following rules: 28.34/8.14 28.34/8.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 28.34/8.14 U12(mark(X1), X2) -> mark(U12(X1, X2)) 28.34/8.14 U13(mark(X)) -> mark(U13(X)) 28.34/8.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 28.34/8.14 U22(mark(X)) -> mark(U22(X)) 28.34/8.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 28.34/8.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 28.34/8.14 s(mark(X)) -> mark(s(X)) 28.34/8.14 plus(mark(X1), X2) -> mark(plus(X1, X2)) 28.34/8.14 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 28.34/8.14 and(mark(X1), X2) -> mark(and(X1, X2)) 28.34/8.14 proper(tt) -> ok(tt) 28.34/8.14 proper(0) -> ok(0) 28.34/8.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 28.34/8.14 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 28.34/8.14 isNat(ok(X)) -> ok(isNat(X)) 28.34/8.14 U13(ok(X)) -> ok(U13(X)) 28.34/8.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 28.34/8.14 U22(ok(X)) -> ok(U22(X)) 28.34/8.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 28.34/8.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 28.34/8.14 s(ok(X)) -> ok(s(X)) 28.34/8.14 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 28.34/8.14 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 28.34/8.14 isNatKind(ok(X)) -> ok(isNatKind(X)) 28.34/8.14 top(mark(X)) -> top(proper(X)) 28.34/8.14 top(ok(X)) -> top(active(X)) 28.34/8.14 28.34/8.14 S is empty. 28.34/8.14 Rewrite Strategy: FULL 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (5) CpxTrsMatchBoundsTAProof (FINISHED) 28.34/8.14 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. 28.34/8.14 28.34/8.14 The compatible tree automaton used to show the Match-Boundedness (for constructor-based start-terms) is represented by: 28.34/8.14 final states : [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] 28.34/8.14 transitions: 28.34/8.14 mark0(0) -> 0 28.34/8.14 tt0() -> 0 28.34/8.14 ok0(0) -> 0 28.34/8.14 00() -> 0 28.34/8.14 active0(0) -> 0 28.34/8.14 U110(0, 0, 0) -> 1 28.34/8.14 U120(0, 0) -> 2 28.34/8.14 U130(0) -> 3 28.34/8.14 U210(0, 0) -> 4 28.34/8.14 U220(0) -> 5 28.34/8.14 U310(0, 0) -> 6 28.34/8.14 U410(0, 0, 0) -> 7 28.34/8.14 s0(0) -> 8 28.34/8.14 plus0(0, 0) -> 9 28.34/8.14 and0(0, 0) -> 10 28.34/8.14 proper0(0) -> 11 28.34/8.14 isNat0(0) -> 12 28.34/8.14 isNatKind0(0) -> 13 28.34/8.14 top0(0) -> 14 28.34/8.14 U111(0, 0, 0) -> 15 28.34/8.14 mark1(15) -> 1 28.34/8.14 U121(0, 0) -> 16 28.34/8.14 mark1(16) -> 2 28.34/8.14 U131(0) -> 17 28.34/8.14 mark1(17) -> 3 28.34/8.14 U211(0, 0) -> 18 28.34/8.14 mark1(18) -> 4 28.34/8.14 U221(0) -> 19 28.34/8.14 mark1(19) -> 5 28.34/8.14 U311(0, 0) -> 20 28.34/8.14 mark1(20) -> 6 28.34/8.14 U411(0, 0, 0) -> 21 28.34/8.14 mark1(21) -> 7 28.34/8.14 s1(0) -> 22 28.34/8.14 mark1(22) -> 8 28.34/8.14 plus1(0, 0) -> 23 28.34/8.14 mark1(23) -> 9 28.34/8.14 and1(0, 0) -> 24 28.34/8.14 mark1(24) -> 10 28.34/8.14 tt1() -> 25 28.34/8.14 ok1(25) -> 11 28.34/8.14 01() -> 26 28.34/8.14 ok1(26) -> 11 28.34/8.14 U111(0, 0, 0) -> 27 28.34/8.14 ok1(27) -> 1 28.34/8.14 U121(0, 0) -> 28 28.34/8.14 ok1(28) -> 2 28.34/8.14 isNat1(0) -> 29 28.34/8.14 ok1(29) -> 12 28.34/8.14 U131(0) -> 30 28.34/8.14 ok1(30) -> 3 28.34/8.14 U211(0, 0) -> 31 28.34/8.14 ok1(31) -> 4 28.34/8.14 U221(0) -> 32 28.34/8.14 ok1(32) -> 5 28.34/8.14 U311(0, 0) -> 33 28.34/8.14 ok1(33) -> 6 28.34/8.14 U411(0, 0, 0) -> 34 28.34/8.14 ok1(34) -> 7 28.34/8.14 s1(0) -> 35 28.34/8.14 ok1(35) -> 8 28.34/8.14 plus1(0, 0) -> 36 28.34/8.14 ok1(36) -> 9 28.34/8.14 and1(0, 0) -> 37 28.34/8.14 ok1(37) -> 10 28.34/8.14 isNatKind1(0) -> 38 28.34/8.14 ok1(38) -> 13 28.34/8.14 proper1(0) -> 39 28.34/8.14 top1(39) -> 14 28.34/8.14 active1(0) -> 40 28.34/8.14 top1(40) -> 14 28.34/8.14 mark1(15) -> 15 28.34/8.14 mark1(15) -> 27 28.34/8.14 mark1(16) -> 16 28.34/8.14 mark1(16) -> 28 28.34/8.14 mark1(17) -> 17 28.34/8.14 mark1(17) -> 30 28.34/8.14 mark1(18) -> 18 28.34/8.14 mark1(18) -> 31 28.34/8.14 mark1(19) -> 19 28.34/8.14 mark1(19) -> 32 28.34/8.14 mark1(20) -> 20 28.34/8.14 mark1(20) -> 33 28.34/8.14 mark1(21) -> 21 28.34/8.14 mark1(21) -> 34 28.34/8.14 mark1(22) -> 22 28.34/8.14 mark1(22) -> 35 28.34/8.14 mark1(23) -> 23 28.34/8.14 mark1(23) -> 36 28.34/8.14 mark1(24) -> 24 28.34/8.14 mark1(24) -> 37 28.34/8.14 ok1(25) -> 39 28.34/8.14 ok1(26) -> 39 28.34/8.14 ok1(27) -> 15 28.34/8.14 ok1(27) -> 27 28.34/8.14 ok1(28) -> 16 28.34/8.14 ok1(28) -> 28 28.34/8.14 ok1(29) -> 29 28.34/8.14 ok1(30) -> 17 28.34/8.14 ok1(30) -> 30 28.34/8.14 ok1(31) -> 18 28.34/8.14 ok1(31) -> 31 28.34/8.14 ok1(32) -> 19 28.34/8.14 ok1(32) -> 32 28.34/8.14 ok1(33) -> 20 28.34/8.14 ok1(33) -> 33 28.34/8.14 ok1(34) -> 21 28.34/8.14 ok1(34) -> 34 28.34/8.14 ok1(35) -> 22 28.34/8.14 ok1(35) -> 35 28.34/8.14 ok1(36) -> 23 28.34/8.14 ok1(36) -> 36 28.34/8.14 ok1(37) -> 24 28.34/8.14 ok1(37) -> 37 28.34/8.14 ok1(38) -> 38 28.34/8.14 active2(25) -> 41 28.34/8.14 top2(41) -> 14 28.34/8.14 active2(26) -> 41 28.34/8.14 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (6) 28.34/8.14 BOUNDS(1, n^1) 28.34/8.14 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (7) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 28.34/8.14 Transformed a relative TRS into a decreasing-loop problem. 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (8) 28.34/8.14 Obligation: 28.34/8.14 Analyzing the following TRS for decreasing loops: 28.34/8.14 28.34/8.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 28.34/8.14 28.34/8.14 28.34/8.14 The TRS R consists of the following rules: 28.34/8.14 28.34/8.14 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 28.34/8.14 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 28.34/8.14 active(U13(tt)) -> mark(tt) 28.34/8.14 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 28.34/8.14 active(U22(tt)) -> mark(tt) 28.34/8.14 active(U31(tt, N)) -> mark(N) 28.34/8.14 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 28.34/8.14 active(and(tt, X)) -> mark(X) 28.34/8.14 active(isNat(0)) -> mark(tt) 28.34/8.14 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 28.34/8.14 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 28.34/8.14 active(isNatKind(0)) -> mark(tt) 28.34/8.14 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 28.34/8.14 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 28.34/8.14 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 28.34/8.14 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 28.34/8.14 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 28.34/8.14 active(U12(X1, X2)) -> U12(active(X1), X2) 28.34/8.14 active(U13(X)) -> U13(active(X)) 28.34/8.14 active(U21(X1, X2)) -> U21(active(X1), X2) 28.34/8.14 active(U22(X)) -> U22(active(X)) 28.34/8.14 active(U31(X1, X2)) -> U31(active(X1), X2) 28.34/8.14 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 28.34/8.14 active(s(X)) -> s(active(X)) 28.34/8.14 active(plus(X1, X2)) -> plus(active(X1), X2) 28.34/8.14 active(plus(X1, X2)) -> plus(X1, active(X2)) 28.34/8.14 active(and(X1, X2)) -> and(active(X1), X2) 28.34/8.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 28.34/8.14 U12(mark(X1), X2) -> mark(U12(X1, X2)) 28.34/8.14 U13(mark(X)) -> mark(U13(X)) 28.34/8.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 28.34/8.14 U22(mark(X)) -> mark(U22(X)) 28.34/8.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 28.34/8.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 28.34/8.14 s(mark(X)) -> mark(s(X)) 28.34/8.14 plus(mark(X1), X2) -> mark(plus(X1, X2)) 28.34/8.14 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 28.34/8.14 and(mark(X1), X2) -> mark(and(X1, X2)) 28.34/8.14 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(tt) -> ok(tt) 28.34/8.14 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 28.34/8.14 proper(isNat(X)) -> isNat(proper(X)) 28.34/8.14 proper(U13(X)) -> U13(proper(X)) 28.34/8.14 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 28.34/8.14 proper(U22(X)) -> U22(proper(X)) 28.34/8.14 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 28.34/8.14 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(s(X)) -> s(proper(X)) 28.34/8.14 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 28.34/8.14 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 28.34/8.14 proper(0) -> ok(0) 28.34/8.14 proper(isNatKind(X)) -> isNatKind(proper(X)) 28.34/8.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 28.34/8.14 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 28.34/8.14 isNat(ok(X)) -> ok(isNat(X)) 28.34/8.14 U13(ok(X)) -> ok(U13(X)) 28.34/8.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 28.34/8.14 U22(ok(X)) -> ok(U22(X)) 28.34/8.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 28.34/8.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 28.34/8.14 s(ok(X)) -> ok(s(X)) 28.34/8.14 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 28.34/8.14 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 28.34/8.14 isNatKind(ok(X)) -> ok(isNatKind(X)) 28.34/8.14 top(mark(X)) -> top(proper(X)) 28.34/8.14 top(ok(X)) -> top(active(X)) 28.34/8.14 28.34/8.14 S is empty. 28.34/8.14 Rewrite Strategy: FULL 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (9) DecreasingLoopProof (LOWER BOUND(ID)) 28.34/8.14 The following loop(s) give(s) rise to the lower bound Omega(n^1): 28.34/8.14 28.34/8.14 The rewrite sequence 28.34/8.14 28.34/8.14 U13(mark(X)) ->^+ mark(U13(X)) 28.34/8.14 28.34/8.14 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 28.34/8.14 28.34/8.14 The pumping substitution is [X / mark(X)]. 28.34/8.14 28.34/8.14 The result substitution is [ ]. 28.34/8.14 28.34/8.14 28.34/8.14 28.34/8.14 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (10) 28.34/8.14 Complex Obligation (BEST) 28.34/8.14 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (11) 28.34/8.14 Obligation: 28.34/8.14 Proved the lower bound n^1 for the following obligation: 28.34/8.14 28.34/8.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 28.34/8.14 28.34/8.14 28.34/8.14 The TRS R consists of the following rules: 28.34/8.14 28.34/8.14 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 28.34/8.14 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 28.34/8.14 active(U13(tt)) -> mark(tt) 28.34/8.14 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 28.34/8.14 active(U22(tt)) -> mark(tt) 28.34/8.14 active(U31(tt, N)) -> mark(N) 28.34/8.14 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 28.34/8.14 active(and(tt, X)) -> mark(X) 28.34/8.14 active(isNat(0)) -> mark(tt) 28.34/8.14 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 28.34/8.14 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 28.34/8.14 active(isNatKind(0)) -> mark(tt) 28.34/8.14 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 28.34/8.14 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 28.34/8.14 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 28.34/8.14 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 28.34/8.14 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 28.34/8.14 active(U12(X1, X2)) -> U12(active(X1), X2) 28.34/8.14 active(U13(X)) -> U13(active(X)) 28.34/8.14 active(U21(X1, X2)) -> U21(active(X1), X2) 28.34/8.14 active(U22(X)) -> U22(active(X)) 28.34/8.14 active(U31(X1, X2)) -> U31(active(X1), X2) 28.34/8.14 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 28.34/8.14 active(s(X)) -> s(active(X)) 28.34/8.14 active(plus(X1, X2)) -> plus(active(X1), X2) 28.34/8.14 active(plus(X1, X2)) -> plus(X1, active(X2)) 28.34/8.14 active(and(X1, X2)) -> and(active(X1), X2) 28.34/8.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 28.34/8.14 U12(mark(X1), X2) -> mark(U12(X1, X2)) 28.34/8.14 U13(mark(X)) -> mark(U13(X)) 28.34/8.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 28.34/8.14 U22(mark(X)) -> mark(U22(X)) 28.34/8.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 28.34/8.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 28.34/8.14 s(mark(X)) -> mark(s(X)) 28.34/8.14 plus(mark(X1), X2) -> mark(plus(X1, X2)) 28.34/8.14 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 28.34/8.14 and(mark(X1), X2) -> mark(and(X1, X2)) 28.34/8.14 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(tt) -> ok(tt) 28.34/8.14 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 28.34/8.14 proper(isNat(X)) -> isNat(proper(X)) 28.34/8.14 proper(U13(X)) -> U13(proper(X)) 28.34/8.14 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 28.34/8.14 proper(U22(X)) -> U22(proper(X)) 28.34/8.14 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 28.34/8.14 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(s(X)) -> s(proper(X)) 28.34/8.14 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 28.34/8.14 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 28.34/8.14 proper(0) -> ok(0) 28.34/8.14 proper(isNatKind(X)) -> isNatKind(proper(X)) 28.34/8.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 28.34/8.14 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 28.34/8.14 isNat(ok(X)) -> ok(isNat(X)) 28.34/8.14 U13(ok(X)) -> ok(U13(X)) 28.34/8.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 28.34/8.14 U22(ok(X)) -> ok(U22(X)) 28.34/8.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 28.34/8.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 28.34/8.14 s(ok(X)) -> ok(s(X)) 28.34/8.14 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 28.34/8.14 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 28.34/8.14 isNatKind(ok(X)) -> ok(isNatKind(X)) 28.34/8.14 top(mark(X)) -> top(proper(X)) 28.34/8.14 top(ok(X)) -> top(active(X)) 28.34/8.14 28.34/8.14 S is empty. 28.34/8.14 Rewrite Strategy: FULL 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (12) LowerBoundPropagationProof (FINISHED) 28.34/8.14 Propagated lower bound. 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (13) 28.34/8.14 BOUNDS(n^1, INF) 28.34/8.14 28.34/8.14 ---------------------------------------- 28.34/8.14 28.34/8.14 (14) 28.34/8.14 Obligation: 28.34/8.14 Analyzing the following TRS for decreasing loops: 28.34/8.14 28.34/8.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 28.34/8.14 28.34/8.14 28.34/8.14 The TRS R consists of the following rules: 28.34/8.14 28.34/8.14 active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2)) 28.34/8.14 active(U12(tt, V2)) -> mark(U13(isNat(V2))) 28.34/8.14 active(U13(tt)) -> mark(tt) 28.34/8.14 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 28.34/8.14 active(U22(tt)) -> mark(tt) 28.34/8.14 active(U31(tt, N)) -> mark(N) 28.34/8.14 active(U41(tt, M, N)) -> mark(s(plus(N, M))) 28.34/8.14 active(and(tt, X)) -> mark(X) 28.34/8.14 active(isNat(0)) -> mark(tt) 28.34/8.14 active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2)) 28.34/8.14 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 28.34/8.14 active(isNatKind(0)) -> mark(tt) 28.34/8.14 active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2))) 28.34/8.14 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 28.34/8.14 active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N)) 28.34/8.14 active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N)) 28.34/8.14 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 28.34/8.14 active(U12(X1, X2)) -> U12(active(X1), X2) 28.34/8.14 active(U13(X)) -> U13(active(X)) 28.34/8.14 active(U21(X1, X2)) -> U21(active(X1), X2) 28.34/8.14 active(U22(X)) -> U22(active(X)) 28.34/8.14 active(U31(X1, X2)) -> U31(active(X1), X2) 28.34/8.14 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 28.34/8.14 active(s(X)) -> s(active(X)) 28.34/8.14 active(plus(X1, X2)) -> plus(active(X1), X2) 28.34/8.14 active(plus(X1, X2)) -> plus(X1, active(X2)) 28.34/8.14 active(and(X1, X2)) -> and(active(X1), X2) 28.34/8.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 28.34/8.14 U12(mark(X1), X2) -> mark(U12(X1, X2)) 28.34/8.14 U13(mark(X)) -> mark(U13(X)) 28.34/8.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 28.34/8.14 U22(mark(X)) -> mark(U22(X)) 28.34/8.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 28.34/8.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 28.34/8.14 s(mark(X)) -> mark(s(X)) 28.34/8.14 plus(mark(X1), X2) -> mark(plus(X1, X2)) 28.34/8.14 plus(X1, mark(X2)) -> mark(plus(X1, X2)) 28.34/8.14 and(mark(X1), X2) -> mark(and(X1, X2)) 28.34/8.14 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(tt) -> ok(tt) 28.34/8.14 proper(U12(X1, X2)) -> U12(proper(X1), proper(X2)) 28.34/8.14 proper(isNat(X)) -> isNat(proper(X)) 28.34/8.14 proper(U13(X)) -> U13(proper(X)) 28.34/8.14 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 28.34/8.14 proper(U22(X)) -> U22(proper(X)) 28.34/8.14 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 28.34/8.14 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 28.34/8.14 proper(s(X)) -> s(proper(X)) 28.34/8.14 proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) 28.34/8.14 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 28.34/8.14 proper(0) -> ok(0) 28.34/8.14 proper(isNatKind(X)) -> isNatKind(proper(X)) 28.34/8.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 28.34/8.14 U12(ok(X1), ok(X2)) -> ok(U12(X1, X2)) 28.34/8.14 isNat(ok(X)) -> ok(isNat(X)) 28.34/8.14 U13(ok(X)) -> ok(U13(X)) 28.34/8.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 28.34/8.14 U22(ok(X)) -> ok(U22(X)) 28.34/8.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 28.34/8.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 28.34/8.14 s(ok(X)) -> ok(s(X)) 28.34/8.14 plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) 28.34/8.14 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 28.34/8.14 isNatKind(ok(X)) -> ok(isNatKind(X)) 28.34/8.14 top(mark(X)) -> top(proper(X)) 28.34/8.14 top(ok(X)) -> top(active(X)) 28.34/8.14 28.34/8.14 S is empty. 28.34/8.14 Rewrite Strategy: FULL 28.41/8.18 EOF