/export/starexec/sandbox2/solver/bin/starexec_run_complexity /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- WORST_CASE(Omega(n^1), O(n^1)) proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). (0) CpxTRS (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] (2) CpxTRS (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 0 ms] (4) CpxTRS (5) CpxTrsToCdtProof [UPPER BOUND(ID), 15 ms] (6) CdtProblem (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] (8) CdtProblem (9) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] (10) CdtProblem (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] (12) CdtProblem (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 157 ms] (14) CdtProblem (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 49 ms] (16) CdtProblem (17) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] (18) BOUNDS(1, 1) (19) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] (20) TRS for Loop Detection (21) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] (22) BEST (23) proven lower bound (24) LowerBoundPropagationProof [FINISHED, 0 ms] (25) BOUNDS(n^1, INF) (26) TRS for Loop Detection ---------------------------------------- (0) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(tt) -> ok(tt) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) The following defined symbols can occur below the 0th argument of top: proper, active The following defined symbols can occur below the 0th argument of proper: proper, active The following defined symbols can occur below the 0th argument of active: proper, active Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) ---------------------------------------- (2) Obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(tt) -> ok(tt) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) Converted rc-obligation to irc-obligation. As the TRS is a non-duplicating overlay system, we have rc = irc. ---------------------------------------- (4) Obligation: The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). The TRS R consists of the following rules: U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(tt) -> ok(tt) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: INNERMOST ---------------------------------------- (5) CpxTrsToCdtProof (UPPER BOUND(ID)) Converted Cpx (relative) TRS to CDT ---------------------------------------- (6) Obligation: Complexity Dependency Tuples Problem Rules: U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) U13(mark(z0), z1, z2) -> mark(U13(z0, z1, z2)) U13(ok(z0), ok(z1), ok(z2)) -> ok(U13(z0, z1, z2)) U14(mark(z0), z1, z2) -> mark(U14(z0, z1, z2)) U14(ok(z0), ok(z1), ok(z2)) -> ok(U14(z0, z1, z2)) U15(mark(z0), z1) -> mark(U15(z0, z1)) U15(ok(z0), ok(z1)) -> ok(U15(z0, z1)) U16(mark(z0)) -> mark(U16(z0)) U16(ok(z0)) -> ok(U16(z0)) U21(mark(z0), z1) -> mark(U21(z0, z1)) U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) U22(mark(z0), z1) -> mark(U22(z0, z1)) U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) U23(mark(z0)) -> mark(U23(z0)) U23(ok(z0)) -> ok(U23(z0)) U31(mark(z0), z1) -> mark(U31(z0, z1)) U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) U32(mark(z0)) -> mark(U32(z0)) U32(ok(z0)) -> ok(U32(z0)) U41(mark(z0)) -> mark(U41(z0)) U41(ok(z0)) -> ok(U41(z0)) U51(mark(z0), z1) -> mark(U51(z0, z1)) U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) U52(mark(z0), z1) -> mark(U52(z0, z1)) U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) U61(mark(z0), z1, z2) -> mark(U61(z0, z1, z2)) U61(ok(z0), ok(z1), ok(z2)) -> ok(U61(z0, z1, z2)) U62(mark(z0), z1, z2) -> mark(U62(z0, z1, z2)) U62(ok(z0), ok(z1), ok(z2)) -> ok(U62(z0, z1, z2)) U63(mark(z0), z1, z2) -> mark(U63(z0, z1, z2)) U63(ok(z0), ok(z1), ok(z2)) -> ok(U63(z0, z1, z2)) U64(mark(z0), z1, z2) -> mark(U64(z0, z1, z2)) U64(ok(z0), ok(z1), ok(z2)) -> ok(U64(z0, z1, z2)) s(mark(z0)) -> mark(s(z0)) s(ok(z0)) -> ok(s(z0)) plus(mark(z0), z1) -> mark(plus(z0, z1)) plus(z0, mark(z1)) -> mark(plus(z0, z1)) plus(ok(z0), ok(z1)) -> ok(plus(z0, z1)) proper(tt) -> ok(tt) proper(0) -> ok(0) isNatKind(ok(z0)) -> ok(isNatKind(z0)) isNat(ok(z0)) -> ok(isNat(z0)) top(mark(z0)) -> top(proper(z0)) top(ok(z0)) -> top(active(z0)) Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) PROPER(tt) -> c41 PROPER(0) -> c42 ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0)), PROPER(z0)) TOP(ok(z0)) -> c46(TOP(active(z0))) S tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) PROPER(tt) -> c41 PROPER(0) -> c42 ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0)), PROPER(z0)) TOP(ok(z0)) -> c46(TOP(active(z0))) K tuples:none Defined Rule Symbols: U11_3, U12_3, U13_3, U14_3, U15_2, U16_1, U21_2, U22_2, U23_1, U31_2, U32_1, U41_1, U51_2, U52_2, U61_3, U62_3, U63_3, U64_3, s_1, plus_2, proper_1, isNatKind_1, isNat_1, top_1 Defined Pair Symbols: U11'_3, U12'_3, U13'_3, U14'_3, U15'_2, U16'_1, U21'_2, U22'_2, U23'_1, U31'_2, U32'_1, U41'_1, U51'_2, U52'_2, U61'_3, U62'_3, U63'_3, U64'_3, S_1, PLUS_2, PROPER_1, ISNATKIND_1, ISNAT_1, TOP_1 Compound Symbols: c_1, c1_1, c2_1, c3_1, c4_1, c5_1, c6_1, c7_1, c8_1, c9_1, c10_1, c11_1, c12_1, c13_1, c14_1, c15_1, c16_1, c17_1, c18_1, c19_1, c20_1, c21_1, c22_1, c23_1, c24_1, c25_1, c26_1, c27_1, c28_1, c29_1, c30_1, c31_1, c32_1, c33_1, c34_1, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c41, c42, c43_1, c44_1, c45_2, c46_1 ---------------------------------------- (7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) Removed 3 trailing nodes: TOP(ok(z0)) -> c46(TOP(active(z0))) PROPER(0) -> c42 PROPER(tt) -> c41 ---------------------------------------- (8) Obligation: Complexity Dependency Tuples Problem Rules: U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) U13(mark(z0), z1, z2) -> mark(U13(z0, z1, z2)) U13(ok(z0), ok(z1), ok(z2)) -> ok(U13(z0, z1, z2)) U14(mark(z0), z1, z2) -> mark(U14(z0, z1, z2)) U14(ok(z0), ok(z1), ok(z2)) -> ok(U14(z0, z1, z2)) U15(mark(z0), z1) -> mark(U15(z0, z1)) U15(ok(z0), ok(z1)) -> ok(U15(z0, z1)) U16(mark(z0)) -> mark(U16(z0)) U16(ok(z0)) -> ok(U16(z0)) U21(mark(z0), z1) -> mark(U21(z0, z1)) U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) U22(mark(z0), z1) -> mark(U22(z0, z1)) U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) U23(mark(z0)) -> mark(U23(z0)) U23(ok(z0)) -> ok(U23(z0)) U31(mark(z0), z1) -> mark(U31(z0, z1)) U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) U32(mark(z0)) -> mark(U32(z0)) U32(ok(z0)) -> ok(U32(z0)) U41(mark(z0)) -> mark(U41(z0)) U41(ok(z0)) -> ok(U41(z0)) U51(mark(z0), z1) -> mark(U51(z0, z1)) U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) U52(mark(z0), z1) -> mark(U52(z0, z1)) U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) U61(mark(z0), z1, z2) -> mark(U61(z0, z1, z2)) U61(ok(z0), ok(z1), ok(z2)) -> ok(U61(z0, z1, z2)) U62(mark(z0), z1, z2) -> mark(U62(z0, z1, z2)) U62(ok(z0), ok(z1), ok(z2)) -> ok(U62(z0, z1, z2)) U63(mark(z0), z1, z2) -> mark(U63(z0, z1, z2)) U63(ok(z0), ok(z1), ok(z2)) -> ok(U63(z0, z1, z2)) U64(mark(z0), z1, z2) -> mark(U64(z0, z1, z2)) U64(ok(z0), ok(z1), ok(z2)) -> ok(U64(z0, z1, z2)) s(mark(z0)) -> mark(s(z0)) s(ok(z0)) -> ok(s(z0)) plus(mark(z0), z1) -> mark(plus(z0, z1)) plus(z0, mark(z1)) -> mark(plus(z0, z1)) plus(ok(z0), ok(z1)) -> ok(plus(z0, z1)) proper(tt) -> ok(tt) proper(0) -> ok(0) isNatKind(ok(z0)) -> ok(isNatKind(z0)) isNat(ok(z0)) -> ok(isNat(z0)) top(mark(z0)) -> top(proper(z0)) top(ok(z0)) -> top(active(z0)) Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0)), PROPER(z0)) S tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0)), PROPER(z0)) K tuples:none Defined Rule Symbols: U11_3, U12_3, U13_3, U14_3, U15_2, U16_1, U21_2, U22_2, U23_1, U31_2, U32_1, U41_1, U51_2, U52_2, U61_3, U62_3, U63_3, U64_3, s_1, plus_2, proper_1, isNatKind_1, isNat_1, top_1 Defined Pair Symbols: U11'_3, U12'_3, U13'_3, U14'_3, U15'_2, U16'_1, U21'_2, U22'_2, U23'_1, U31'_2, U32'_1, U41'_1, U51'_2, U52'_2, U61'_3, U62'_3, U63'_3, U64'_3, S_1, PLUS_2, ISNATKIND_1, ISNAT_1, TOP_1 Compound Symbols: c_1, c1_1, c2_1, c3_1, c4_1, c5_1, c6_1, c7_1, c8_1, c9_1, c10_1, c11_1, c12_1, c13_1, c14_1, c15_1, c16_1, c17_1, c18_1, c19_1, c20_1, c21_1, c22_1, c23_1, c24_1, c25_1, c26_1, c27_1, c28_1, c29_1, c30_1, c31_1, c32_1, c33_1, c34_1, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c43_1, c44_1, c45_2 ---------------------------------------- (9) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) Removed 1 trailing tuple parts ---------------------------------------- (10) Obligation: Complexity Dependency Tuples Problem Rules: U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) U13(mark(z0), z1, z2) -> mark(U13(z0, z1, z2)) U13(ok(z0), ok(z1), ok(z2)) -> ok(U13(z0, z1, z2)) U14(mark(z0), z1, z2) -> mark(U14(z0, z1, z2)) U14(ok(z0), ok(z1), ok(z2)) -> ok(U14(z0, z1, z2)) U15(mark(z0), z1) -> mark(U15(z0, z1)) U15(ok(z0), ok(z1)) -> ok(U15(z0, z1)) U16(mark(z0)) -> mark(U16(z0)) U16(ok(z0)) -> ok(U16(z0)) U21(mark(z0), z1) -> mark(U21(z0, z1)) U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) U22(mark(z0), z1) -> mark(U22(z0, z1)) U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) U23(mark(z0)) -> mark(U23(z0)) U23(ok(z0)) -> ok(U23(z0)) U31(mark(z0), z1) -> mark(U31(z0, z1)) U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) U32(mark(z0)) -> mark(U32(z0)) U32(ok(z0)) -> ok(U32(z0)) U41(mark(z0)) -> mark(U41(z0)) U41(ok(z0)) -> ok(U41(z0)) U51(mark(z0), z1) -> mark(U51(z0, z1)) U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) U52(mark(z0), z1) -> mark(U52(z0, z1)) U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) U61(mark(z0), z1, z2) -> mark(U61(z0, z1, z2)) U61(ok(z0), ok(z1), ok(z2)) -> ok(U61(z0, z1, z2)) U62(mark(z0), z1, z2) -> mark(U62(z0, z1, z2)) U62(ok(z0), ok(z1), ok(z2)) -> ok(U62(z0, z1, z2)) U63(mark(z0), z1, z2) -> mark(U63(z0, z1, z2)) U63(ok(z0), ok(z1), ok(z2)) -> ok(U63(z0, z1, z2)) U64(mark(z0), z1, z2) -> mark(U64(z0, z1, z2)) U64(ok(z0), ok(z1), ok(z2)) -> ok(U64(z0, z1, z2)) s(mark(z0)) -> mark(s(z0)) s(ok(z0)) -> ok(s(z0)) plus(mark(z0), z1) -> mark(plus(z0, z1)) plus(z0, mark(z1)) -> mark(plus(z0, z1)) plus(ok(z0), ok(z1)) -> ok(plus(z0, z1)) proper(tt) -> ok(tt) proper(0) -> ok(0) isNatKind(ok(z0)) -> ok(isNatKind(z0)) isNat(ok(z0)) -> ok(isNat(z0)) top(mark(z0)) -> top(proper(z0)) top(ok(z0)) -> top(active(z0)) Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) S tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) K tuples:none Defined Rule Symbols: U11_3, U12_3, U13_3, U14_3, U15_2, U16_1, U21_2, U22_2, U23_1, U31_2, U32_1, U41_1, U51_2, U52_2, U61_3, U62_3, U63_3, U64_3, s_1, plus_2, proper_1, isNatKind_1, isNat_1, top_1 Defined Pair Symbols: U11'_3, U12'_3, U13'_3, U14'_3, U15'_2, U16'_1, U21'_2, U22'_2, U23'_1, U31'_2, U32'_1, U41'_1, U51'_2, U52'_2, U61'_3, U62'_3, U63'_3, U64'_3, S_1, PLUS_2, ISNATKIND_1, ISNAT_1, TOP_1 Compound Symbols: c_1, c1_1, c2_1, c3_1, c4_1, c5_1, c6_1, c7_1, c8_1, c9_1, c10_1, c11_1, c12_1, c13_1, c14_1, c15_1, c16_1, c17_1, c18_1, c19_1, c20_1, c21_1, c22_1, c23_1, c24_1, c25_1, c26_1, c27_1, c28_1, c29_1, c30_1, c31_1, c32_1, c33_1, c34_1, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c43_1, c44_1, c45_1 ---------------------------------------- (11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) The following rules are not usable and were removed: U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) U13(mark(z0), z1, z2) -> mark(U13(z0, z1, z2)) U13(ok(z0), ok(z1), ok(z2)) -> ok(U13(z0, z1, z2)) U14(mark(z0), z1, z2) -> mark(U14(z0, z1, z2)) U14(ok(z0), ok(z1), ok(z2)) -> ok(U14(z0, z1, z2)) U15(mark(z0), z1) -> mark(U15(z0, z1)) U15(ok(z0), ok(z1)) -> ok(U15(z0, z1)) U16(mark(z0)) -> mark(U16(z0)) U16(ok(z0)) -> ok(U16(z0)) U21(mark(z0), z1) -> mark(U21(z0, z1)) U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) U22(mark(z0), z1) -> mark(U22(z0, z1)) U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) U23(mark(z0)) -> mark(U23(z0)) U23(ok(z0)) -> ok(U23(z0)) U31(mark(z0), z1) -> mark(U31(z0, z1)) U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) U32(mark(z0)) -> mark(U32(z0)) U32(ok(z0)) -> ok(U32(z0)) U41(mark(z0)) -> mark(U41(z0)) U41(ok(z0)) -> ok(U41(z0)) U51(mark(z0), z1) -> mark(U51(z0, z1)) U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) U52(mark(z0), z1) -> mark(U52(z0, z1)) U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) U61(mark(z0), z1, z2) -> mark(U61(z0, z1, z2)) U61(ok(z0), ok(z1), ok(z2)) -> ok(U61(z0, z1, z2)) U62(mark(z0), z1, z2) -> mark(U62(z0, z1, z2)) U62(ok(z0), ok(z1), ok(z2)) -> ok(U62(z0, z1, z2)) U63(mark(z0), z1, z2) -> mark(U63(z0, z1, z2)) U63(ok(z0), ok(z1), ok(z2)) -> ok(U63(z0, z1, z2)) U64(mark(z0), z1, z2) -> mark(U64(z0, z1, z2)) U64(ok(z0), ok(z1), ok(z2)) -> ok(U64(z0, z1, z2)) s(mark(z0)) -> mark(s(z0)) s(ok(z0)) -> ok(s(z0)) plus(mark(z0), z1) -> mark(plus(z0, z1)) plus(z0, mark(z1)) -> mark(plus(z0, z1)) plus(ok(z0), ok(z1)) -> ok(plus(z0, z1)) isNatKind(ok(z0)) -> ok(isNatKind(z0)) isNat(ok(z0)) -> ok(isNat(z0)) top(mark(z0)) -> top(proper(z0)) top(ok(z0)) -> top(active(z0)) ---------------------------------------- (12) Obligation: Complexity Dependency Tuples Problem Rules: proper(tt) -> ok(tt) proper(0) -> ok(0) Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) S tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) K tuples:none Defined Rule Symbols: proper_1 Defined Pair Symbols: U11'_3, U12'_3, U13'_3, U14'_3, U15'_2, U16'_1, U21'_2, U22'_2, U23'_1, U31'_2, U32'_1, U41'_1, U51'_2, U52'_2, U61'_3, U62'_3, U63'_3, U64'_3, S_1, PLUS_2, ISNATKIND_1, ISNAT_1, TOP_1 Compound Symbols: c_1, c1_1, c2_1, c3_1, c4_1, c5_1, c6_1, c7_1, c8_1, c9_1, c10_1, c11_1, c12_1, c13_1, c14_1, c15_1, c16_1, c17_1, c18_1, c19_1, c20_1, c21_1, c22_1, c23_1, c24_1, c25_1, c26_1, c27_1, c28_1, c29_1, c30_1, c31_1, c32_1, c33_1, c34_1, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c43_1, c44_1, c45_1 ---------------------------------------- (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) We considered the (Usable) Rules: proper(tt) -> ok(tt) proper(0) -> ok(0) And the Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ISNAT(x_1)) = x_1 POL(ISNATKIND(x_1)) = x_1 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(S(x_1)) = x_1 POL(TOP(x_1)) = x_1 POL(U11'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U12'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U13'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U15'(x_1, x_2)) = x_1 + x_2 POL(U16'(x_1)) = x_1 POL(U21'(x_1, x_2)) = x_1 + x_2 POL(U22'(x_1, x_2)) = x_1 + x_2 POL(U23'(x_1)) = x_1 POL(U31'(x_1, x_2)) = x_1 + x_2 POL(U32'(x_1)) = x_1 POL(U41'(x_1)) = x_1 POL(U51'(x_1, x_2)) = x_1 + x_2 POL(U52'(x_1, x_2)) = x_1 + x_2 POL(U61'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U62'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U63'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U64'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c14(x_1)) = x_1 POL(c15(x_1)) = x_1 POL(c16(x_1)) = x_1 POL(c17(x_1)) = x_1 POL(c18(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20(x_1)) = x_1 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23(x_1)) = x_1 POL(c24(x_1)) = x_1 POL(c25(x_1)) = x_1 POL(c26(x_1)) = x_1 POL(c27(x_1)) = x_1 POL(c28(x_1)) = x_1 POL(c29(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(c30(x_1)) = x_1 POL(c31(x_1)) = x_1 POL(c32(x_1)) = x_1 POL(c33(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36(x_1)) = x_1 POL(c37(x_1)) = x_1 POL(c38(x_1)) = x_1 POL(c39(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c43(x_1)) = x_1 POL(c44(x_1)) = x_1 POL(c45(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1)) = x_1 POL(c7(x_1)) = x_1 POL(c8(x_1)) = x_1 POL(c9(x_1)) = x_1 POL(mark(x_1)) = [1] + x_1 POL(ok(x_1)) = [1] + x_1 POL(proper(x_1)) = [1] + x_1 POL(tt) = [1] ---------------------------------------- (14) Obligation: Complexity Dependency Tuples Problem Rules: proper(tt) -> ok(tt) proper(0) -> ok(0) Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) S tuples: TOP(mark(z0)) -> c45(TOP(proper(z0))) K tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) Defined Rule Symbols: proper_1 Defined Pair Symbols: U11'_3, U12'_3, U13'_3, U14'_3, U15'_2, U16'_1, U21'_2, U22'_2, U23'_1, U31'_2, U32'_1, U41'_1, U51'_2, U52'_2, U61'_3, U62'_3, U63'_3, U64'_3, S_1, PLUS_2, ISNATKIND_1, ISNAT_1, TOP_1 Compound Symbols: c_1, c1_1, c2_1, c3_1, c4_1, c5_1, c6_1, c7_1, c8_1, c9_1, c10_1, c11_1, c12_1, c13_1, c14_1, c15_1, c16_1, c17_1, c18_1, c19_1, c20_1, c21_1, c22_1, c23_1, c24_1, c25_1, c26_1, c27_1, c28_1, c29_1, c30_1, c31_1, c32_1, c33_1, c34_1, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c43_1, c44_1, c45_1 ---------------------------------------- (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. TOP(mark(z0)) -> c45(TOP(proper(z0))) We considered the (Usable) Rules: proper(tt) -> ok(tt) proper(0) -> ok(0) And the Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) The order we found is given by the following interpretation: Polynomial interpretation : POL(0) = [1] POL(ISNAT(x_1)) = x_1 POL(ISNATKIND(x_1)) = x_1 POL(PLUS(x_1, x_2)) = x_1 + x_2 POL(S(x_1)) = x_1 POL(TOP(x_1)) = x_1 POL(U11'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U12'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U13'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U14'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U15'(x_1, x_2)) = x_1 + x_2 POL(U16'(x_1)) = x_1 POL(U21'(x_1, x_2)) = x_1 + x_2 POL(U22'(x_1, x_2)) = x_1 + x_2 POL(U23'(x_1)) = x_1 POL(U31'(x_1, x_2)) = x_1 + x_2 POL(U32'(x_1)) = x_1 POL(U41'(x_1)) = x_1 POL(U51'(x_1, x_2)) = x_1 + x_2 POL(U52'(x_1, x_2)) = x_1 + x_2 POL(U61'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U62'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U63'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(U64'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 POL(c(x_1)) = x_1 POL(c1(x_1)) = x_1 POL(c10(x_1)) = x_1 POL(c11(x_1)) = x_1 POL(c12(x_1)) = x_1 POL(c13(x_1)) = x_1 POL(c14(x_1)) = x_1 POL(c15(x_1)) = x_1 POL(c16(x_1)) = x_1 POL(c17(x_1)) = x_1 POL(c18(x_1)) = x_1 POL(c19(x_1)) = x_1 POL(c2(x_1)) = x_1 POL(c20(x_1)) = x_1 POL(c21(x_1)) = x_1 POL(c22(x_1)) = x_1 POL(c23(x_1)) = x_1 POL(c24(x_1)) = x_1 POL(c25(x_1)) = x_1 POL(c26(x_1)) = x_1 POL(c27(x_1)) = x_1 POL(c28(x_1)) = x_1 POL(c29(x_1)) = x_1 POL(c3(x_1)) = x_1 POL(c30(x_1)) = x_1 POL(c31(x_1)) = x_1 POL(c32(x_1)) = x_1 POL(c33(x_1)) = x_1 POL(c34(x_1)) = x_1 POL(c35(x_1)) = x_1 POL(c36(x_1)) = x_1 POL(c37(x_1)) = x_1 POL(c38(x_1)) = x_1 POL(c39(x_1)) = x_1 POL(c4(x_1)) = x_1 POL(c40(x_1)) = x_1 POL(c43(x_1)) = x_1 POL(c44(x_1)) = x_1 POL(c45(x_1)) = x_1 POL(c5(x_1)) = x_1 POL(c6(x_1)) = x_1 POL(c7(x_1)) = x_1 POL(c8(x_1)) = x_1 POL(c9(x_1)) = x_1 POL(mark(x_1)) = [1] + x_1 POL(ok(x_1)) = x_1 POL(proper(x_1)) = x_1 POL(tt) = [1] ---------------------------------------- (16) Obligation: Complexity Dependency Tuples Problem Rules: proper(tt) -> ok(tt) proper(0) -> ok(0) Tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) S tuples:none K tuples: U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) U13'(mark(z0), z1, z2) -> c4(U13'(z0, z1, z2)) U13'(ok(z0), ok(z1), ok(z2)) -> c5(U13'(z0, z1, z2)) U14'(mark(z0), z1, z2) -> c6(U14'(z0, z1, z2)) U14'(ok(z0), ok(z1), ok(z2)) -> c7(U14'(z0, z1, z2)) U15'(mark(z0), z1) -> c8(U15'(z0, z1)) U15'(ok(z0), ok(z1)) -> c9(U15'(z0, z1)) U16'(mark(z0)) -> c10(U16'(z0)) U16'(ok(z0)) -> c11(U16'(z0)) U21'(mark(z0), z1) -> c12(U21'(z0, z1)) U21'(ok(z0), ok(z1)) -> c13(U21'(z0, z1)) U22'(mark(z0), z1) -> c14(U22'(z0, z1)) U22'(ok(z0), ok(z1)) -> c15(U22'(z0, z1)) U23'(mark(z0)) -> c16(U23'(z0)) U23'(ok(z0)) -> c17(U23'(z0)) U31'(mark(z0), z1) -> c18(U31'(z0, z1)) U31'(ok(z0), ok(z1)) -> c19(U31'(z0, z1)) U32'(mark(z0)) -> c20(U32'(z0)) U32'(ok(z0)) -> c21(U32'(z0)) U41'(mark(z0)) -> c22(U41'(z0)) U41'(ok(z0)) -> c23(U41'(z0)) U51'(mark(z0), z1) -> c24(U51'(z0, z1)) U51'(ok(z0), ok(z1)) -> c25(U51'(z0, z1)) U52'(mark(z0), z1) -> c26(U52'(z0, z1)) U52'(ok(z0), ok(z1)) -> c27(U52'(z0, z1)) U61'(mark(z0), z1, z2) -> c28(U61'(z0, z1, z2)) U61'(ok(z0), ok(z1), ok(z2)) -> c29(U61'(z0, z1, z2)) U62'(mark(z0), z1, z2) -> c30(U62'(z0, z1, z2)) U62'(ok(z0), ok(z1), ok(z2)) -> c31(U62'(z0, z1, z2)) U63'(mark(z0), z1, z2) -> c32(U63'(z0, z1, z2)) U63'(ok(z0), ok(z1), ok(z2)) -> c33(U63'(z0, z1, z2)) U64'(mark(z0), z1, z2) -> c34(U64'(z0, z1, z2)) U64'(ok(z0), ok(z1), ok(z2)) -> c35(U64'(z0, z1, z2)) S(mark(z0)) -> c36(S(z0)) S(ok(z0)) -> c37(S(z0)) PLUS(mark(z0), z1) -> c38(PLUS(z0, z1)) PLUS(z0, mark(z1)) -> c39(PLUS(z0, z1)) PLUS(ok(z0), ok(z1)) -> c40(PLUS(z0, z1)) ISNATKIND(ok(z0)) -> c43(ISNATKIND(z0)) ISNAT(ok(z0)) -> c44(ISNAT(z0)) TOP(mark(z0)) -> c45(TOP(proper(z0))) Defined Rule Symbols: proper_1 Defined Pair Symbols: U11'_3, U12'_3, U13'_3, U14'_3, U15'_2, U16'_1, U21'_2, U22'_2, U23'_1, U31'_2, U32'_1, U41'_1, U51'_2, U52'_2, U61'_3, U62'_3, U63'_3, U64'_3, S_1, PLUS_2, ISNATKIND_1, ISNAT_1, TOP_1 Compound Symbols: c_1, c1_1, c2_1, c3_1, c4_1, c5_1, c6_1, c7_1, c8_1, c9_1, c10_1, c11_1, c12_1, c13_1, c14_1, c15_1, c16_1, c17_1, c18_1, c19_1, c20_1, c21_1, c22_1, c23_1, c24_1, c25_1, c26_1, c27_1, c28_1, c29_1, c30_1, c31_1, c32_1, c33_1, c34_1, c35_1, c36_1, c37_1, c38_1, c39_1, c40_1, c43_1, c44_1, c45_1 ---------------------------------------- (17) SIsEmptyProof (BOTH BOUNDS(ID, ID)) The set S is empty ---------------------------------------- (18) BOUNDS(1, 1) ---------------------------------------- (19) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) Transformed a relative TRS into a decreasing-loop problem. ---------------------------------------- (20) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(tt) -> ok(tt) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (21) DecreasingLoopProof (LOWER BOUND(ID)) The following loop(s) give(s) rise to the lower bound Omega(n^1): The rewrite sequence U52(ok(X1), ok(X2)) ->^+ ok(U52(X1, X2)) gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. The pumping substitution is [X1 / ok(X1), X2 / ok(X2)]. The result substitution is [ ]. ---------------------------------------- (22) Complex Obligation (BEST) ---------------------------------------- (23) Obligation: Proved the lower bound n^1 for the following obligation: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(tt) -> ok(tt) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL ---------------------------------------- (24) LowerBoundPropagationProof (FINISHED) Propagated lower bound. ---------------------------------------- (25) BOUNDS(n^1, INF) ---------------------------------------- (26) Obligation: Analyzing the following TRS for decreasing loops: The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). The TRS R consists of the following rules: active(U11(tt, V1, V2)) -> mark(U12(isNatKind(V1), V1, V2)) active(U12(tt, V1, V2)) -> mark(U13(isNatKind(V2), V1, V2)) active(U13(tt, V1, V2)) -> mark(U14(isNatKind(V2), V1, V2)) active(U14(tt, V1, V2)) -> mark(U15(isNat(V1), V2)) active(U15(tt, V2)) -> mark(U16(isNat(V2))) active(U16(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNatKind(V1), V1)) active(U22(tt, V1)) -> mark(U23(isNat(V1))) active(U23(tt)) -> mark(tt) active(U31(tt, V2)) -> mark(U32(isNatKind(V2))) active(U32(tt)) -> mark(tt) active(U41(tt)) -> mark(tt) active(U51(tt, N)) -> mark(U52(isNatKind(N), N)) active(U52(tt, N)) -> mark(N) active(U61(tt, M, N)) -> mark(U62(isNatKind(M), M, N)) active(U62(tt, M, N)) -> mark(U63(isNat(N), M, N)) active(U63(tt, M, N)) -> mark(U64(isNatKind(N), M, N)) active(U64(tt, M, N)) -> mark(s(plus(N, M))) active(isNat(0)) -> mark(tt) active(isNat(plus(V1, V2))) -> mark(U11(isNatKind(V1), V1, V2)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatKind(0)) -> mark(tt) active(isNatKind(plus(V1, V2))) -> mark(U31(isNatKind(V1), V2)) active(isNatKind(s(V1))) -> mark(U41(isNatKind(V1))) active(plus(N, 0)) -> mark(U51(isNat(N), N)) active(plus(N, s(M))) -> mark(U61(isNat(M), M, N)) active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) active(U13(X1, X2, X3)) -> U13(active(X1), X2, X3) active(U14(X1, X2, X3)) -> U14(active(X1), X2, X3) active(U15(X1, X2)) -> U15(active(X1), X2) active(U16(X)) -> U16(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X1, X2)) -> U22(active(X1), X2) active(U23(X)) -> U23(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X)) -> U41(active(X)) active(U51(X1, X2)) -> U51(active(X1), X2) active(U52(X1, X2)) -> U52(active(X1), X2) active(U61(X1, X2, X3)) -> U61(active(X1), X2, X3) active(U62(X1, X2, X3)) -> U62(active(X1), X2, X3) active(U63(X1, X2, X3)) -> U63(active(X1), X2, X3) active(U64(X1, X2, X3)) -> U64(active(X1), X2, X3) active(s(X)) -> s(active(X)) active(plus(X1, X2)) -> plus(active(X1), X2) active(plus(X1, X2)) -> plus(X1, active(X2)) U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) U13(mark(X1), X2, X3) -> mark(U13(X1, X2, X3)) U14(mark(X1), X2, X3) -> mark(U14(X1, X2, X3)) U15(mark(X1), X2) -> mark(U15(X1, X2)) U16(mark(X)) -> mark(U16(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X1), X2) -> mark(U22(X1, X2)) U23(mark(X)) -> mark(U23(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X)) -> mark(U41(X)) U51(mark(X1), X2) -> mark(U51(X1, X2)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U61(mark(X1), X2, X3) -> mark(U61(X1, X2, X3)) U62(mark(X1), X2, X3) -> mark(U62(X1, X2, X3)) U63(mark(X1), X2, X3) -> mark(U63(X1, X2, X3)) U64(mark(X1), X2, X3) -> mark(U64(X1, X2, X3)) s(mark(X)) -> mark(s(X)) plus(mark(X1), X2) -> mark(plus(X1, X2)) plus(X1, mark(X2)) -> mark(plus(X1, X2)) proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) proper(tt) -> ok(tt) proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(U13(X1, X2, X3)) -> U13(proper(X1), proper(X2), proper(X3)) proper(U14(X1, X2, X3)) -> U14(proper(X1), proper(X2), proper(X3)) proper(U15(X1, X2)) -> U15(proper(X1), proper(X2)) proper(isNat(X)) -> isNat(proper(X)) proper(U16(X)) -> U16(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) proper(U23(X)) -> U23(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X)) -> U41(proper(X)) proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U61(X1, X2, X3)) -> U61(proper(X1), proper(X2), proper(X3)) proper(U62(X1, X2, X3)) -> U62(proper(X1), proper(X2), proper(X3)) proper(U63(X1, X2, X3)) -> U63(proper(X1), proper(X2), proper(X3)) proper(U64(X1, X2, X3)) -> U64(proper(X1), proper(X2), proper(X3)) proper(s(X)) -> s(proper(X)) proper(plus(X1, X2)) -> plus(proper(X1), proper(X2)) proper(0) -> ok(0) U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) isNatKind(ok(X)) -> ok(isNatKind(X)) U13(ok(X1), ok(X2), ok(X3)) -> ok(U13(X1, X2, X3)) U14(ok(X1), ok(X2), ok(X3)) -> ok(U14(X1, X2, X3)) U15(ok(X1), ok(X2)) -> ok(U15(X1, X2)) isNat(ok(X)) -> ok(isNat(X)) U16(ok(X)) -> ok(U16(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) U23(ok(X)) -> ok(U23(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X)) -> ok(U41(X)) U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U61(ok(X1), ok(X2), ok(X3)) -> ok(U61(X1, X2, X3)) U62(ok(X1), ok(X2), ok(X3)) -> ok(U62(X1, X2, X3)) U63(ok(X1), ok(X2), ok(X3)) -> ok(U63(X1, X2, X3)) U64(ok(X1), ok(X2), ok(X3)) -> ok(U64(X1, X2, X3)) s(ok(X)) -> ok(s(X)) plus(ok(X1), ok(X2)) -> ok(plus(X1, X2)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) S is empty. Rewrite Strategy: FULL