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