40.09/11.13 WORST_CASE(Omega(n^1), O(n^1)) 40.53/11.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 40.53/11.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 40.53/11.14 40.53/11.14 40.53/11.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 40.53/11.14 40.53/11.14 (0) CpxTRS 40.53/11.14 (1) NestedDefinedSymbolProof [UPPER BOUND(ID), 0 ms] 40.53/11.14 (2) CpxTRS 40.53/11.14 (3) RcToIrcProof [BOTH BOUNDS(ID, ID), 73 ms] 40.53/11.14 (4) CpxTRS 40.53/11.14 (5) CpxTrsToCdtProof [UPPER BOUND(ID), 0 ms] 40.53/11.14 (6) CdtProblem 40.53/11.14 (7) CdtLeafRemovalProof [BOTH BOUNDS(ID, ID), 0 ms] 40.53/11.14 (8) CdtProblem 40.53/11.14 (9) CdtRhsSimplificationProcessorProof [BOTH BOUNDS(ID, ID), 0 ms] 40.53/11.14 (10) CdtProblem 40.53/11.14 (11) CdtUsableRulesProof [BOTH BOUNDS(ID, ID), 0 ms] 40.53/11.14 (12) CdtProblem 40.53/11.14 (13) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 221 ms] 40.53/11.14 (14) CdtProblem 40.53/11.14 (15) CdtRuleRemovalProof [UPPER BOUND(ADD(n^1)), 62 ms] 40.53/11.14 (16) CdtProblem 40.53/11.14 (17) SIsEmptyProof [BOTH BOUNDS(ID, ID), 0 ms] 40.53/11.14 (18) BOUNDS(1, 1) 40.53/11.14 (19) RelTrsToDecreasingLoopProblemProof [LOWER BOUND(ID), 0 ms] 40.53/11.14 (20) TRS for Loop Detection 40.53/11.14 (21) DecreasingLoopProof [LOWER BOUND(ID), 0 ms] 40.53/11.14 (22) BEST 40.53/11.14 (23) proven lower bound 40.53/11.14 (24) LowerBoundPropagationProof [FINISHED, 0 ms] 40.53/11.14 (25) BOUNDS(n^1, INF) 40.53/11.14 (26) TRS for Loop Detection 40.53/11.14 40.53/11.14 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (0) 40.53/11.14 Obligation: 40.53/11.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 40.53/11.14 40.53/11.14 40.53/11.14 The TRS R consists of the following rules: 40.53/11.14 40.53/11.14 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 40.53/11.14 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 40.53/11.14 active(U21(tt, X)) -> mark(U22(tt, X)) 40.53/11.14 active(U22(tt, X)) -> mark(X) 40.53/11.14 active(U31(tt, N)) -> mark(U32(tt, N)) 40.53/11.14 active(U32(tt, N)) -> mark(N) 40.53/11.14 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 40.53/11.14 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 40.53/11.14 active(U51(tt, Y)) -> mark(U52(tt, Y)) 40.53/11.14 active(U52(tt, Y)) -> mark(Y) 40.53/11.14 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 40.53/11.14 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 40.53/11.14 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 40.53/11.14 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 40.53/11.14 active(U71(tt, XS)) -> mark(U72(tt, XS)) 40.53/11.14 active(U72(tt, XS)) -> mark(XS) 40.53/11.14 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 40.53/11.14 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 40.53/11.14 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 40.53/11.14 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 40.53/11.14 active(head(cons(N, XS))) -> mark(U31(tt, N)) 40.53/11.14 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 40.53/11.14 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 40.53/11.14 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 40.53/11.14 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 40.53/11.14 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 40.53/11.14 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 40.53/11.14 active(take(N, XS)) -> mark(U81(tt, N, XS)) 40.53/11.14 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 40.53/11.14 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 40.53/11.14 active(snd(X)) -> snd(active(X)) 40.53/11.14 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 40.53/11.14 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 40.53/11.14 active(U21(X1, X2)) -> U21(active(X1), X2) 40.53/11.14 active(U22(X1, X2)) -> U22(active(X1), X2) 40.53/11.14 active(U31(X1, X2)) -> U31(active(X1), X2) 40.53/11.14 active(U32(X1, X2)) -> U32(active(X1), X2) 40.53/11.14 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 40.53/11.14 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 40.53/11.14 active(head(X)) -> head(active(X)) 40.53/11.14 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 40.53/11.14 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 40.53/11.14 active(U51(X1, X2)) -> U51(active(X1), X2) 40.53/11.14 active(U52(X1, X2)) -> U52(active(X1), X2) 40.53/11.14 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 40.53/11.14 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 40.53/11.14 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 40.53/11.14 active(U64(X1, X2)) -> U64(active(X1), X2) 40.53/11.14 active(pair(X1, X2)) -> pair(active(X1), X2) 40.53/11.14 active(pair(X1, X2)) -> pair(X1, active(X2)) 40.53/11.14 active(cons(X1, X2)) -> cons(active(X1), X2) 40.53/11.14 active(U71(X1, X2)) -> U71(active(X1), X2) 40.53/11.14 active(U72(X1, X2)) -> U72(active(X1), X2) 40.53/11.14 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 40.53/11.14 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 40.53/11.14 active(fst(X)) -> fst(active(X)) 40.53/11.14 active(natsFrom(X)) -> natsFrom(active(X)) 40.53/11.14 active(s(X)) -> s(active(X)) 40.53/11.14 active(sel(X1, X2)) -> sel(active(X1), X2) 40.53/11.14 active(sel(X1, X2)) -> sel(X1, active(X2)) 40.53/11.14 active(tail(X)) -> tail(active(X)) 40.53/11.14 active(take(X1, X2)) -> take(active(X1), X2) 40.53/11.14 active(take(X1, X2)) -> take(X1, active(X2)) 40.53/11.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 40.53/11.14 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 40.53/11.14 snd(mark(X)) -> mark(snd(X)) 40.53/11.14 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 40.53/11.14 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 40.53/11.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 40.53/11.14 U22(mark(X1), X2) -> mark(U22(X1, X2)) 40.53/11.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 40.53/11.14 U32(mark(X1), X2) -> mark(U32(X1, X2)) 40.53/11.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 40.53/11.14 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 40.53/11.14 head(mark(X)) -> mark(head(X)) 40.53/11.14 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 40.53/11.14 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 40.53/11.14 U51(mark(X1), X2) -> mark(U51(X1, X2)) 40.53/11.14 U52(mark(X1), X2) -> mark(U52(X1, X2)) 40.53/11.14 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 40.53/11.14 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 40.53/11.14 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 40.53/11.14 U64(mark(X1), X2) -> mark(U64(X1, X2)) 40.53/11.14 pair(mark(X1), X2) -> mark(pair(X1, X2)) 40.53/11.14 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 40.53/11.14 cons(mark(X1), X2) -> mark(cons(X1, X2)) 40.53/11.14 U71(mark(X1), X2) -> mark(U71(X1, X2)) 40.53/11.14 U72(mark(X1), X2) -> mark(U72(X1, X2)) 40.53/11.14 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 40.53/11.14 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 40.53/11.14 fst(mark(X)) -> mark(fst(X)) 40.53/11.14 natsFrom(mark(X)) -> mark(natsFrom(X)) 40.53/11.14 s(mark(X)) -> mark(s(X)) 40.53/11.14 sel(mark(X1), X2) -> mark(sel(X1, X2)) 40.53/11.14 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 40.53/11.14 tail(mark(X)) -> mark(tail(X)) 40.53/11.14 take(mark(X1), X2) -> mark(take(X1, X2)) 40.53/11.14 take(X1, mark(X2)) -> mark(take(X1, X2)) 40.53/11.14 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(tt) -> ok(tt) 40.53/11.14 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(snd(X)) -> snd(proper(X)) 40.53/11.14 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 40.53/11.14 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 40.53/11.14 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 40.53/11.14 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 40.53/11.14 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 40.53/11.14 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(head(X)) -> head(proper(X)) 40.53/11.14 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 40.53/11.14 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 40.53/11.14 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 40.53/11.14 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.14 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.14 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.14 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 40.53/11.14 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 40.53/11.14 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 40.53/11.14 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 40.53/11.14 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 40.53/11.14 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(fst(X)) -> fst(proper(X)) 40.53/11.14 proper(natsFrom(X)) -> natsFrom(proper(X)) 40.53/11.14 proper(s(X)) -> s(proper(X)) 40.53/11.14 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 40.53/11.14 proper(0) -> ok(0) 40.53/11.14 proper(nil) -> ok(nil) 40.53/11.14 proper(tail(X)) -> tail(proper(X)) 40.53/11.14 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 40.53/11.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 40.53/11.14 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 40.53/11.14 snd(ok(X)) -> ok(snd(X)) 40.53/11.14 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 40.53/11.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 40.53/11.14 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 40.53/11.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 40.53/11.14 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 40.53/11.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 40.53/11.14 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 40.53/11.14 head(ok(X)) -> ok(head(X)) 40.53/11.14 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 40.53/11.14 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 40.53/11.14 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 40.53/11.14 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 40.53/11.14 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 40.53/11.14 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 40.53/11.14 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 40.53/11.14 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 40.53/11.14 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 40.53/11.14 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 40.53/11.14 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 40.53/11.14 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 40.53/11.14 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 40.53/11.14 fst(ok(X)) -> ok(fst(X)) 40.53/11.14 natsFrom(ok(X)) -> ok(natsFrom(X)) 40.53/11.14 s(ok(X)) -> ok(s(X)) 40.53/11.14 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 40.53/11.14 tail(ok(X)) -> ok(tail(X)) 40.53/11.14 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 40.53/11.14 top(mark(X)) -> top(proper(X)) 40.53/11.14 top(ok(X)) -> top(active(X)) 40.53/11.14 40.53/11.14 S is empty. 40.53/11.14 Rewrite Strategy: FULL 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (1) NestedDefinedSymbolProof (UPPER BOUND(ID)) 40.53/11.14 The following defined symbols can occur below the 0th argument of top: proper, active 40.53/11.14 The following defined symbols can occur below the 0th argument of proper: proper, active 40.53/11.14 The following defined symbols can occur below the 0th argument of active: proper, active 40.53/11.14 40.53/11.14 Hence, the left-hand sides of the following rules are not basic-reachable and can be removed: 40.53/11.14 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 40.53/11.14 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 40.53/11.14 active(U21(tt, X)) -> mark(U22(tt, X)) 40.53/11.14 active(U22(tt, X)) -> mark(X) 40.53/11.14 active(U31(tt, N)) -> mark(U32(tt, N)) 40.53/11.14 active(U32(tt, N)) -> mark(N) 40.53/11.14 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 40.53/11.14 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 40.53/11.14 active(U51(tt, Y)) -> mark(U52(tt, Y)) 40.53/11.14 active(U52(tt, Y)) -> mark(Y) 40.53/11.14 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 40.53/11.14 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 40.53/11.14 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 40.53/11.14 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 40.53/11.14 active(U71(tt, XS)) -> mark(U72(tt, XS)) 40.53/11.14 active(U72(tt, XS)) -> mark(XS) 40.53/11.14 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 40.53/11.14 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 40.53/11.14 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 40.53/11.14 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 40.53/11.14 active(head(cons(N, XS))) -> mark(U31(tt, N)) 40.53/11.14 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 40.53/11.14 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 40.53/11.14 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 40.53/11.14 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 40.53/11.14 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 40.53/11.14 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 40.53/11.14 active(take(N, XS)) -> mark(U81(tt, N, XS)) 40.53/11.14 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 40.53/11.14 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 40.53/11.14 active(snd(X)) -> snd(active(X)) 40.53/11.14 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 40.53/11.14 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 40.53/11.14 active(U21(X1, X2)) -> U21(active(X1), X2) 40.53/11.14 active(U22(X1, X2)) -> U22(active(X1), X2) 40.53/11.14 active(U31(X1, X2)) -> U31(active(X1), X2) 40.53/11.14 active(U32(X1, X2)) -> U32(active(X1), X2) 40.53/11.14 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 40.53/11.14 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 40.53/11.14 active(head(X)) -> head(active(X)) 40.53/11.14 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 40.53/11.14 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 40.53/11.14 active(U51(X1, X2)) -> U51(active(X1), X2) 40.53/11.14 active(U52(X1, X2)) -> U52(active(X1), X2) 40.53/11.14 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 40.53/11.14 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 40.53/11.14 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 40.53/11.14 active(U64(X1, X2)) -> U64(active(X1), X2) 40.53/11.14 active(pair(X1, X2)) -> pair(active(X1), X2) 40.53/11.14 active(pair(X1, X2)) -> pair(X1, active(X2)) 40.53/11.14 active(cons(X1, X2)) -> cons(active(X1), X2) 40.53/11.14 active(U71(X1, X2)) -> U71(active(X1), X2) 40.53/11.14 active(U72(X1, X2)) -> U72(active(X1), X2) 40.53/11.14 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 40.53/11.14 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 40.53/11.14 active(fst(X)) -> fst(active(X)) 40.53/11.14 active(natsFrom(X)) -> natsFrom(active(X)) 40.53/11.14 active(s(X)) -> s(active(X)) 40.53/11.14 active(sel(X1, X2)) -> sel(active(X1), X2) 40.53/11.14 active(sel(X1, X2)) -> sel(X1, active(X2)) 40.53/11.14 active(tail(X)) -> tail(active(X)) 40.53/11.14 active(take(X1, X2)) -> take(active(X1), X2) 40.53/11.14 active(take(X1, X2)) -> take(X1, active(X2)) 40.53/11.14 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(snd(X)) -> snd(proper(X)) 40.53/11.14 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 40.53/11.14 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 40.53/11.14 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 40.53/11.14 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 40.53/11.14 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 40.53/11.14 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(head(X)) -> head(proper(X)) 40.53/11.14 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 40.53/11.14 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 40.53/11.14 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 40.53/11.14 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.14 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.14 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.14 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 40.53/11.14 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 40.53/11.14 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 40.53/11.14 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 40.53/11.14 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 40.53/11.14 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 40.53/11.14 proper(fst(X)) -> fst(proper(X)) 40.53/11.14 proper(natsFrom(X)) -> natsFrom(proper(X)) 40.53/11.14 proper(s(X)) -> s(proper(X)) 40.53/11.14 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 40.53/11.14 proper(tail(X)) -> tail(proper(X)) 40.53/11.14 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 40.53/11.14 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (2) 40.53/11.14 Obligation: 40.53/11.14 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 40.53/11.14 40.53/11.14 40.53/11.14 The TRS R consists of the following rules: 40.53/11.14 40.53/11.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 40.53/11.14 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 40.53/11.14 snd(mark(X)) -> mark(snd(X)) 40.53/11.14 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 40.53/11.14 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 40.53/11.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 40.53/11.14 U22(mark(X1), X2) -> mark(U22(X1, X2)) 40.53/11.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 40.53/11.14 U32(mark(X1), X2) -> mark(U32(X1, X2)) 40.53/11.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 40.53/11.14 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 40.53/11.14 head(mark(X)) -> mark(head(X)) 40.53/11.14 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 40.53/11.14 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 40.53/11.14 U51(mark(X1), X2) -> mark(U51(X1, X2)) 40.53/11.14 U52(mark(X1), X2) -> mark(U52(X1, X2)) 40.53/11.14 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 40.53/11.14 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 40.53/11.14 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 40.53/11.14 U64(mark(X1), X2) -> mark(U64(X1, X2)) 40.53/11.14 pair(mark(X1), X2) -> mark(pair(X1, X2)) 40.53/11.14 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 40.53/11.14 cons(mark(X1), X2) -> mark(cons(X1, X2)) 40.53/11.14 U71(mark(X1), X2) -> mark(U71(X1, X2)) 40.53/11.14 U72(mark(X1), X2) -> mark(U72(X1, X2)) 40.53/11.14 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 40.53/11.14 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 40.53/11.14 fst(mark(X)) -> mark(fst(X)) 40.53/11.14 natsFrom(mark(X)) -> mark(natsFrom(X)) 40.53/11.14 s(mark(X)) -> mark(s(X)) 40.53/11.14 sel(mark(X1), X2) -> mark(sel(X1, X2)) 40.53/11.14 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 40.53/11.14 tail(mark(X)) -> mark(tail(X)) 40.53/11.14 take(mark(X1), X2) -> mark(take(X1, X2)) 40.53/11.14 take(X1, mark(X2)) -> mark(take(X1, X2)) 40.53/11.14 proper(tt) -> ok(tt) 40.53/11.14 proper(0) -> ok(0) 40.53/11.14 proper(nil) -> ok(nil) 40.53/11.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 40.53/11.14 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 40.53/11.14 snd(ok(X)) -> ok(snd(X)) 40.53/11.14 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 40.53/11.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 40.53/11.14 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 40.53/11.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 40.53/11.14 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 40.53/11.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 40.53/11.14 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 40.53/11.14 head(ok(X)) -> ok(head(X)) 40.53/11.14 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 40.53/11.14 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 40.53/11.14 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 40.53/11.14 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 40.53/11.14 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 40.53/11.14 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 40.53/11.14 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 40.53/11.14 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 40.53/11.14 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 40.53/11.14 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 40.53/11.14 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 40.53/11.14 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 40.53/11.14 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 40.53/11.14 fst(ok(X)) -> ok(fst(X)) 40.53/11.14 natsFrom(ok(X)) -> ok(natsFrom(X)) 40.53/11.14 s(ok(X)) -> ok(s(X)) 40.53/11.14 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 40.53/11.14 tail(ok(X)) -> ok(tail(X)) 40.53/11.14 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 40.53/11.14 top(mark(X)) -> top(proper(X)) 40.53/11.14 top(ok(X)) -> top(active(X)) 40.53/11.14 40.53/11.14 S is empty. 40.53/11.14 Rewrite Strategy: FULL 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (3) RcToIrcProof (BOTH BOUNDS(ID, ID)) 40.53/11.14 Converted rc-obligation to irc-obligation. 40.53/11.14 40.53/11.14 As the TRS is a non-duplicating overlay system, we have rc = irc. 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (4) 40.53/11.14 Obligation: 40.53/11.14 The Runtime Complexity (innermost) of the given CpxTRS could be proven to be BOUNDS(1, n^1). 40.53/11.14 40.53/11.14 40.53/11.14 The TRS R consists of the following rules: 40.53/11.14 40.53/11.14 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 40.53/11.14 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 40.53/11.14 snd(mark(X)) -> mark(snd(X)) 40.53/11.14 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 40.53/11.14 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 40.53/11.14 U21(mark(X1), X2) -> mark(U21(X1, X2)) 40.53/11.14 U22(mark(X1), X2) -> mark(U22(X1, X2)) 40.53/11.14 U31(mark(X1), X2) -> mark(U31(X1, X2)) 40.53/11.14 U32(mark(X1), X2) -> mark(U32(X1, X2)) 40.53/11.14 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 40.53/11.14 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 40.53/11.14 head(mark(X)) -> mark(head(X)) 40.53/11.14 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 40.53/11.14 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 40.53/11.14 U51(mark(X1), X2) -> mark(U51(X1, X2)) 40.53/11.14 U52(mark(X1), X2) -> mark(U52(X1, X2)) 40.53/11.14 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 40.53/11.14 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 40.53/11.14 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 40.53/11.14 U64(mark(X1), X2) -> mark(U64(X1, X2)) 40.53/11.14 pair(mark(X1), X2) -> mark(pair(X1, X2)) 40.53/11.14 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 40.53/11.14 cons(mark(X1), X2) -> mark(cons(X1, X2)) 40.53/11.14 U71(mark(X1), X2) -> mark(U71(X1, X2)) 40.53/11.14 U72(mark(X1), X2) -> mark(U72(X1, X2)) 40.53/11.14 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 40.53/11.14 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 40.53/11.14 fst(mark(X)) -> mark(fst(X)) 40.53/11.14 natsFrom(mark(X)) -> mark(natsFrom(X)) 40.53/11.14 s(mark(X)) -> mark(s(X)) 40.53/11.14 sel(mark(X1), X2) -> mark(sel(X1, X2)) 40.53/11.14 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 40.53/11.14 tail(mark(X)) -> mark(tail(X)) 40.53/11.14 take(mark(X1), X2) -> mark(take(X1, X2)) 40.53/11.14 take(X1, mark(X2)) -> mark(take(X1, X2)) 40.53/11.14 proper(tt) -> ok(tt) 40.53/11.14 proper(0) -> ok(0) 40.53/11.14 proper(nil) -> ok(nil) 40.53/11.14 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 40.53/11.14 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 40.53/11.14 snd(ok(X)) -> ok(snd(X)) 40.53/11.14 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 40.53/11.14 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 40.53/11.14 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 40.53/11.14 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 40.53/11.14 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 40.53/11.14 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 40.53/11.14 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 40.53/11.14 head(ok(X)) -> ok(head(X)) 40.53/11.14 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 40.53/11.14 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 40.53/11.14 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 40.53/11.14 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 40.53/11.14 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 40.53/11.14 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 40.53/11.14 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 40.53/11.14 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 40.53/11.14 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 40.53/11.14 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 40.53/11.14 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 40.53/11.14 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 40.53/11.14 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 40.53/11.14 fst(ok(X)) -> ok(fst(X)) 40.53/11.14 natsFrom(ok(X)) -> ok(natsFrom(X)) 40.53/11.14 s(ok(X)) -> ok(s(X)) 40.53/11.14 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 40.53/11.14 tail(ok(X)) -> ok(tail(X)) 40.53/11.14 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 40.53/11.14 top(mark(X)) -> top(proper(X)) 40.53/11.14 top(ok(X)) -> top(active(X)) 40.53/11.14 40.53/11.14 S is empty. 40.53/11.14 Rewrite Strategy: INNERMOST 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (5) CpxTrsToCdtProof (UPPER BOUND(ID)) 40.53/11.14 Converted Cpx (relative) TRS to CDT 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (6) 40.53/11.14 Obligation: 40.53/11.14 Complexity Dependency Tuples Problem 40.53/11.14 40.53/11.14 Rules: 40.53/11.14 U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) 40.53/11.14 U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) 40.53/11.14 U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) 40.53/11.14 U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) 40.53/11.14 snd(mark(z0)) -> mark(snd(z0)) 40.53/11.14 snd(ok(z0)) -> ok(snd(z0)) 40.53/11.14 splitAt(mark(z0), z1) -> mark(splitAt(z0, z1)) 40.53/11.14 splitAt(z0, mark(z1)) -> mark(splitAt(z0, z1)) 40.53/11.14 splitAt(ok(z0), ok(z1)) -> ok(splitAt(z0, z1)) 40.53/11.14 U21(mark(z0), z1) -> mark(U21(z0, z1)) 40.53/11.14 U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) 40.53/11.14 U22(mark(z0), z1) -> mark(U22(z0, z1)) 40.53/11.14 U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) 40.53/11.14 U31(mark(z0), z1) -> mark(U31(z0, z1)) 40.53/11.14 U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) 40.53/11.14 U32(mark(z0), z1) -> mark(U32(z0, z1)) 40.53/11.14 U32(ok(z0), ok(z1)) -> ok(U32(z0, z1)) 40.53/11.14 U41(mark(z0), z1, z2) -> mark(U41(z0, z1, z2)) 40.53/11.14 U41(ok(z0), ok(z1), ok(z2)) -> ok(U41(z0, z1, z2)) 40.53/11.14 U42(mark(z0), z1, z2) -> mark(U42(z0, z1, z2)) 40.53/11.14 U42(ok(z0), ok(z1), ok(z2)) -> ok(U42(z0, z1, z2)) 40.53/11.14 head(mark(z0)) -> mark(head(z0)) 40.53/11.14 head(ok(z0)) -> ok(head(z0)) 40.53/11.14 afterNth(mark(z0), z1) -> mark(afterNth(z0, z1)) 40.53/11.14 afterNth(z0, mark(z1)) -> mark(afterNth(z0, z1)) 40.53/11.14 afterNth(ok(z0), ok(z1)) -> ok(afterNth(z0, z1)) 40.53/11.14 U51(mark(z0), z1) -> mark(U51(z0, z1)) 40.53/11.14 U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) 40.53/11.14 U52(mark(z0), z1) -> mark(U52(z0, z1)) 40.53/11.14 U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) 40.53/11.14 U61(mark(z0), z1, z2, z3) -> mark(U61(z0, z1, z2, z3)) 40.53/11.14 U61(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U61(z0, z1, z2, z3)) 40.53/11.14 U62(mark(z0), z1, z2, z3) -> mark(U62(z0, z1, z2, z3)) 40.53/11.14 U62(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U62(z0, z1, z2, z3)) 40.53/11.14 U63(mark(z0), z1, z2, z3) -> mark(U63(z0, z1, z2, z3)) 40.53/11.14 U63(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U63(z0, z1, z2, z3)) 40.53/11.14 U64(mark(z0), z1) -> mark(U64(z0, z1)) 40.53/11.14 U64(ok(z0), ok(z1)) -> ok(U64(z0, z1)) 40.53/11.14 pair(mark(z0), z1) -> mark(pair(z0, z1)) 40.53/11.14 pair(z0, mark(z1)) -> mark(pair(z0, z1)) 40.53/11.14 pair(ok(z0), ok(z1)) -> ok(pair(z0, z1)) 40.53/11.14 cons(mark(z0), z1) -> mark(cons(z0, z1)) 40.53/11.14 cons(ok(z0), ok(z1)) -> ok(cons(z0, z1)) 40.53/11.14 U71(mark(z0), z1) -> mark(U71(z0, z1)) 40.53/11.14 U71(ok(z0), ok(z1)) -> ok(U71(z0, z1)) 40.53/11.14 U72(mark(z0), z1) -> mark(U72(z0, z1)) 40.53/11.14 U72(ok(z0), ok(z1)) -> ok(U72(z0, z1)) 40.53/11.14 U81(mark(z0), z1, z2) -> mark(U81(z0, z1, z2)) 40.53/11.14 U81(ok(z0), ok(z1), ok(z2)) -> ok(U81(z0, z1, z2)) 40.53/11.14 U82(mark(z0), z1, z2) -> mark(U82(z0, z1, z2)) 40.53/11.14 U82(ok(z0), ok(z1), ok(z2)) -> ok(U82(z0, z1, z2)) 40.53/11.14 fst(mark(z0)) -> mark(fst(z0)) 40.53/11.14 fst(ok(z0)) -> ok(fst(z0)) 40.53/11.14 natsFrom(mark(z0)) -> mark(natsFrom(z0)) 40.53/11.14 natsFrom(ok(z0)) -> ok(natsFrom(z0)) 40.53/11.14 s(mark(z0)) -> mark(s(z0)) 40.53/11.14 s(ok(z0)) -> ok(s(z0)) 40.53/11.14 sel(mark(z0), z1) -> mark(sel(z0, z1)) 40.53/11.14 sel(z0, mark(z1)) -> mark(sel(z0, z1)) 40.53/11.14 sel(ok(z0), ok(z1)) -> ok(sel(z0, z1)) 40.53/11.14 tail(mark(z0)) -> mark(tail(z0)) 40.53/11.14 tail(ok(z0)) -> ok(tail(z0)) 40.53/11.14 take(mark(z0), z1) -> mark(take(z0, z1)) 40.53/11.14 take(z0, mark(z1)) -> mark(take(z0, z1)) 40.53/11.14 take(ok(z0), ok(z1)) -> ok(take(z0, z1)) 40.53/11.14 proper(tt) -> ok(tt) 40.53/11.14 proper(0) -> ok(0) 40.53/11.14 proper(nil) -> ok(nil) 40.53/11.14 top(mark(z0)) -> top(proper(z0)) 40.53/11.14 top(ok(z0)) -> top(active(z0)) 40.53/11.14 Tuples: 40.53/11.14 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.14 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.14 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.14 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.14 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.14 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.14 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.14 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.14 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.14 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.14 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.14 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.14 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.14 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.14 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.14 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.14 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.14 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.14 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.14 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.14 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.14 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.14 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.14 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.14 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.14 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.14 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.14 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.14 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.14 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.14 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.14 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.14 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.14 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.14 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.14 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.14 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.14 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.14 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.14 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.14 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.14 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.14 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.14 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.14 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.14 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.14 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.14 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.14 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.14 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.14 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.14 S(mark(z0)) -> c55(S(z0)) 40.53/11.14 S(ok(z0)) -> c56(S(z0)) 40.53/11.14 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.14 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.14 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.14 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.14 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.14 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.14 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.14 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.14 PROPER(tt) -> c65 40.53/11.14 PROPER(0) -> c66 40.53/11.14 PROPER(nil) -> c67 40.53/11.14 TOP(mark(z0)) -> c68(TOP(proper(z0)), PROPER(z0)) 40.53/11.14 TOP(ok(z0)) -> c69(TOP(active(z0))) 40.53/11.14 S tuples: 40.53/11.14 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.14 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.14 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.14 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.14 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.14 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.14 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.14 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.14 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.14 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.14 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.14 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.14 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.14 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.14 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.14 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.14 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.14 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.14 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.14 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.14 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.14 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.14 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.14 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.14 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.14 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.14 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.14 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.14 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.14 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.14 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.14 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.14 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.14 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.14 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.14 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.14 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.14 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.14 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.14 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.14 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.14 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.14 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.14 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.14 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.14 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.14 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.14 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.14 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.14 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.14 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.14 S(mark(z0)) -> c55(S(z0)) 40.53/11.14 S(ok(z0)) -> c56(S(z0)) 40.53/11.14 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.14 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.14 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.14 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.14 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.14 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.14 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.14 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.14 PROPER(tt) -> c65 40.53/11.14 PROPER(0) -> c66 40.53/11.14 PROPER(nil) -> c67 40.53/11.14 TOP(mark(z0)) -> c68(TOP(proper(z0)), PROPER(z0)) 40.53/11.14 TOP(ok(z0)) -> c69(TOP(active(z0))) 40.53/11.14 K tuples:none 40.53/11.14 Defined Rule Symbols: U11_3, U12_3, snd_1, splitAt_2, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, head_1, afterNth_2, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, pair_2, cons_2, U71_2, U72_2, U81_3, U82_3, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, proper_1, top_1 40.53/11.14 40.53/11.14 Defined Pair Symbols: U11'_3, U12'_3, SND_1, SPLITAT_2, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, HEAD_1, AFTERNTH_2, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, PAIR_2, CONS_2, U71'_2, U72'_2, U81'_3, U82'_3, FST_1, NATSFROM_1, S_1, SEL_2, TAIL_1, TAKE_2, PROPER_1, TOP_1 40.53/11.14 40.53/11.14 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_1, c42_1, c43_1, c44_1, c45_1, c46_1, c47_1, c48_1, c49_1, c50_1, c51_1, c52_1, c53_1, c54_1, c55_1, c56_1, c57_1, c58_1, c59_1, c60_1, c61_1, c62_1, c63_1, c64_1, c65, c66, c67, c68_2, c69_1 40.53/11.14 40.53/11.14 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (7) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID)) 40.53/11.14 Removed 4 trailing nodes: 40.53/11.14 TOP(ok(z0)) -> c69(TOP(active(z0))) 40.53/11.14 PROPER(tt) -> c65 40.53/11.14 PROPER(nil) -> c67 40.53/11.14 PROPER(0) -> c66 40.53/11.14 40.53/11.14 ---------------------------------------- 40.53/11.14 40.53/11.14 (8) 40.53/11.14 Obligation: 40.53/11.14 Complexity Dependency Tuples Problem 40.53/11.14 40.53/11.14 Rules: 40.53/11.14 U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) 40.53/11.14 U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) 40.53/11.14 U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) 40.53/11.14 U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) 40.53/11.14 snd(mark(z0)) -> mark(snd(z0)) 40.53/11.14 snd(ok(z0)) -> ok(snd(z0)) 40.53/11.14 splitAt(mark(z0), z1) -> mark(splitAt(z0, z1)) 40.53/11.14 splitAt(z0, mark(z1)) -> mark(splitAt(z0, z1)) 40.53/11.14 splitAt(ok(z0), ok(z1)) -> ok(splitAt(z0, z1)) 40.53/11.14 U21(mark(z0), z1) -> mark(U21(z0, z1)) 40.53/11.14 U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) 40.53/11.14 U22(mark(z0), z1) -> mark(U22(z0, z1)) 40.53/11.14 U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) 40.53/11.14 U31(mark(z0), z1) -> mark(U31(z0, z1)) 40.53/11.14 U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) 40.53/11.14 U32(mark(z0), z1) -> mark(U32(z0, z1)) 40.53/11.14 U32(ok(z0), ok(z1)) -> ok(U32(z0, z1)) 40.53/11.14 U41(mark(z0), z1, z2) -> mark(U41(z0, z1, z2)) 40.53/11.14 U41(ok(z0), ok(z1), ok(z2)) -> ok(U41(z0, z1, z2)) 40.53/11.14 U42(mark(z0), z1, z2) -> mark(U42(z0, z1, z2)) 40.53/11.14 U42(ok(z0), ok(z1), ok(z2)) -> ok(U42(z0, z1, z2)) 40.53/11.14 head(mark(z0)) -> mark(head(z0)) 40.53/11.14 head(ok(z0)) -> ok(head(z0)) 40.53/11.14 afterNth(mark(z0), z1) -> mark(afterNth(z0, z1)) 40.53/11.14 afterNth(z0, mark(z1)) -> mark(afterNth(z0, z1)) 40.53/11.14 afterNth(ok(z0), ok(z1)) -> ok(afterNth(z0, z1)) 40.53/11.14 U51(mark(z0), z1) -> mark(U51(z0, z1)) 40.53/11.14 U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) 40.53/11.14 U52(mark(z0), z1) -> mark(U52(z0, z1)) 40.53/11.14 U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) 40.53/11.14 U61(mark(z0), z1, z2, z3) -> mark(U61(z0, z1, z2, z3)) 40.53/11.14 U61(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U61(z0, z1, z2, z3)) 40.53/11.14 U62(mark(z0), z1, z2, z3) -> mark(U62(z0, z1, z2, z3)) 40.53/11.14 U62(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U62(z0, z1, z2, z3)) 40.53/11.14 U63(mark(z0), z1, z2, z3) -> mark(U63(z0, z1, z2, z3)) 40.53/11.14 U63(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U63(z0, z1, z2, z3)) 40.53/11.14 U64(mark(z0), z1) -> mark(U64(z0, z1)) 40.53/11.14 U64(ok(z0), ok(z1)) -> ok(U64(z0, z1)) 40.53/11.14 pair(mark(z0), z1) -> mark(pair(z0, z1)) 40.53/11.14 pair(z0, mark(z1)) -> mark(pair(z0, z1)) 40.53/11.14 pair(ok(z0), ok(z1)) -> ok(pair(z0, z1)) 40.53/11.14 cons(mark(z0), z1) -> mark(cons(z0, z1)) 40.53/11.14 cons(ok(z0), ok(z1)) -> ok(cons(z0, z1)) 40.53/11.14 U71(mark(z0), z1) -> mark(U71(z0, z1)) 40.53/11.14 U71(ok(z0), ok(z1)) -> ok(U71(z0, z1)) 40.53/11.14 U72(mark(z0), z1) -> mark(U72(z0, z1)) 40.53/11.14 U72(ok(z0), ok(z1)) -> ok(U72(z0, z1)) 40.53/11.14 U81(mark(z0), z1, z2) -> mark(U81(z0, z1, z2)) 40.53/11.14 U81(ok(z0), ok(z1), ok(z2)) -> ok(U81(z0, z1, z2)) 40.53/11.14 U82(mark(z0), z1, z2) -> mark(U82(z0, z1, z2)) 40.53/11.14 U82(ok(z0), ok(z1), ok(z2)) -> ok(U82(z0, z1, z2)) 40.53/11.14 fst(mark(z0)) -> mark(fst(z0)) 40.53/11.14 fst(ok(z0)) -> ok(fst(z0)) 40.53/11.14 natsFrom(mark(z0)) -> mark(natsFrom(z0)) 40.53/11.14 natsFrom(ok(z0)) -> ok(natsFrom(z0)) 40.53/11.14 s(mark(z0)) -> mark(s(z0)) 40.53/11.14 s(ok(z0)) -> ok(s(z0)) 40.53/11.14 sel(mark(z0), z1) -> mark(sel(z0, z1)) 40.53/11.14 sel(z0, mark(z1)) -> mark(sel(z0, z1)) 40.53/11.14 sel(ok(z0), ok(z1)) -> ok(sel(z0, z1)) 40.53/11.14 tail(mark(z0)) -> mark(tail(z0)) 40.53/11.14 tail(ok(z0)) -> ok(tail(z0)) 40.53/11.14 take(mark(z0), z1) -> mark(take(z0, z1)) 40.53/11.14 take(z0, mark(z1)) -> mark(take(z0, z1)) 40.53/11.14 take(ok(z0), ok(z1)) -> ok(take(z0, z1)) 40.53/11.14 proper(tt) -> ok(tt) 40.53/11.14 proper(0) -> ok(0) 40.53/11.14 proper(nil) -> ok(nil) 40.53/11.14 top(mark(z0)) -> top(proper(z0)) 40.53/11.14 top(ok(z0)) -> top(active(z0)) 40.53/11.14 Tuples: 40.53/11.14 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.14 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.14 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.14 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.14 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.14 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.14 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.14 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.14 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.14 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.14 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.14 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.14 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.14 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.14 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.14 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.14 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.14 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.14 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.14 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.14 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.14 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.14 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.14 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.14 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.14 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.14 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.14 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.14 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.14 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.14 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.14 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.14 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.14 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.14 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.14 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.14 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.14 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.14 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.14 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.14 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.14 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.14 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.14 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.14 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.14 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.14 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.14 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.14 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.14 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.14 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.14 S(mark(z0)) -> c55(S(z0)) 40.53/11.14 S(ok(z0)) -> c56(S(z0)) 40.53/11.14 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.14 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.14 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.14 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.14 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.14 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.14 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.14 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.14 TOP(mark(z0)) -> c68(TOP(proper(z0)), PROPER(z0)) 40.53/11.14 S tuples: 40.53/11.14 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.14 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.14 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.14 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.14 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.14 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.14 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.14 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.14 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.14 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.14 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.14 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.14 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.14 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.14 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.14 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.14 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.14 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.14 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.14 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.14 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.14 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.14 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.14 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.14 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.14 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.14 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.14 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.14 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.14 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.14 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.14 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.14 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.14 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.14 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.14 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.14 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.14 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.14 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.14 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.14 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.14 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.14 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.14 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.14 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.14 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.14 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.14 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.14 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.14 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.14 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.14 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.14 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.14 S(mark(z0)) -> c55(S(z0)) 40.53/11.14 S(ok(z0)) -> c56(S(z0)) 40.53/11.14 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.14 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.14 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.14 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.14 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.14 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.14 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.14 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.14 TOP(mark(z0)) -> c68(TOP(proper(z0)), PROPER(z0)) 40.53/11.14 K tuples:none 40.53/11.14 Defined Rule Symbols: U11_3, U12_3, snd_1, splitAt_2, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, head_1, afterNth_2, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, pair_2, cons_2, U71_2, U72_2, U81_3, U82_3, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, proper_1, top_1 40.53/11.14 40.53/11.14 Defined Pair Symbols: U11'_3, U12'_3, SND_1, SPLITAT_2, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, HEAD_1, AFTERNTH_2, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, PAIR_2, CONS_2, U71'_2, U72'_2, U81'_3, U82'_3, FST_1, NATSFROM_1, S_1, SEL_2, TAIL_1, TAKE_2, TOP_1 40.53/11.14 40.53/11.14 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_1, c42_1, c43_1, c44_1, c45_1, c46_1, c47_1, c48_1, c49_1, c50_1, c51_1, c52_1, c53_1, c54_1, c55_1, c56_1, c57_1, c58_1, c59_1, c60_1, c61_1, c62_1, c63_1, c64_1, c68_2 40.53/11.15 40.53/11.15 40.53/11.15 ---------------------------------------- 40.53/11.15 40.53/11.15 (9) CdtRhsSimplificationProcessorProof (BOTH BOUNDS(ID, ID)) 40.53/11.15 Removed 1 trailing tuple parts 40.53/11.15 ---------------------------------------- 40.53/11.15 40.53/11.15 (10) 40.53/11.15 Obligation: 40.53/11.15 Complexity Dependency Tuples Problem 40.53/11.15 40.53/11.15 Rules: 40.53/11.15 U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) 40.53/11.15 U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) 40.53/11.15 U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) 40.53/11.15 U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) 40.53/11.15 snd(mark(z0)) -> mark(snd(z0)) 40.53/11.15 snd(ok(z0)) -> ok(snd(z0)) 40.53/11.15 splitAt(mark(z0), z1) -> mark(splitAt(z0, z1)) 40.53/11.15 splitAt(z0, mark(z1)) -> mark(splitAt(z0, z1)) 40.53/11.15 splitAt(ok(z0), ok(z1)) -> ok(splitAt(z0, z1)) 40.53/11.15 U21(mark(z0), z1) -> mark(U21(z0, z1)) 40.53/11.15 U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) 40.53/11.15 U22(mark(z0), z1) -> mark(U22(z0, z1)) 40.53/11.15 U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) 40.53/11.15 U31(mark(z0), z1) -> mark(U31(z0, z1)) 40.53/11.15 U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) 40.53/11.15 U32(mark(z0), z1) -> mark(U32(z0, z1)) 40.53/11.15 U32(ok(z0), ok(z1)) -> ok(U32(z0, z1)) 40.53/11.15 U41(mark(z0), z1, z2) -> mark(U41(z0, z1, z2)) 40.53/11.15 U41(ok(z0), ok(z1), ok(z2)) -> ok(U41(z0, z1, z2)) 40.53/11.15 U42(mark(z0), z1, z2) -> mark(U42(z0, z1, z2)) 40.53/11.15 U42(ok(z0), ok(z1), ok(z2)) -> ok(U42(z0, z1, z2)) 40.53/11.15 head(mark(z0)) -> mark(head(z0)) 40.53/11.15 head(ok(z0)) -> ok(head(z0)) 40.53/11.15 afterNth(mark(z0), z1) -> mark(afterNth(z0, z1)) 40.53/11.15 afterNth(z0, mark(z1)) -> mark(afterNth(z0, z1)) 40.53/11.15 afterNth(ok(z0), ok(z1)) -> ok(afterNth(z0, z1)) 40.53/11.15 U51(mark(z0), z1) -> mark(U51(z0, z1)) 40.53/11.15 U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) 40.53/11.15 U52(mark(z0), z1) -> mark(U52(z0, z1)) 40.53/11.15 U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) 40.53/11.15 U61(mark(z0), z1, z2, z3) -> mark(U61(z0, z1, z2, z3)) 40.53/11.15 U61(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U61(z0, z1, z2, z3)) 40.53/11.15 U62(mark(z0), z1, z2, z3) -> mark(U62(z0, z1, z2, z3)) 40.53/11.15 U62(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U62(z0, z1, z2, z3)) 40.53/11.15 U63(mark(z0), z1, z2, z3) -> mark(U63(z0, z1, z2, z3)) 40.53/11.15 U63(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U63(z0, z1, z2, z3)) 40.53/11.15 U64(mark(z0), z1) -> mark(U64(z0, z1)) 40.53/11.15 U64(ok(z0), ok(z1)) -> ok(U64(z0, z1)) 40.53/11.15 pair(mark(z0), z1) -> mark(pair(z0, z1)) 40.53/11.15 pair(z0, mark(z1)) -> mark(pair(z0, z1)) 40.53/11.15 pair(ok(z0), ok(z1)) -> ok(pair(z0, z1)) 40.53/11.15 cons(mark(z0), z1) -> mark(cons(z0, z1)) 40.53/11.15 cons(ok(z0), ok(z1)) -> ok(cons(z0, z1)) 40.53/11.15 U71(mark(z0), z1) -> mark(U71(z0, z1)) 40.53/11.15 U71(ok(z0), ok(z1)) -> ok(U71(z0, z1)) 40.53/11.15 U72(mark(z0), z1) -> mark(U72(z0, z1)) 40.53/11.15 U72(ok(z0), ok(z1)) -> ok(U72(z0, z1)) 40.53/11.15 U81(mark(z0), z1, z2) -> mark(U81(z0, z1, z2)) 40.53/11.15 U81(ok(z0), ok(z1), ok(z2)) -> ok(U81(z0, z1, z2)) 40.53/11.15 U82(mark(z0), z1, z2) -> mark(U82(z0, z1, z2)) 40.53/11.15 U82(ok(z0), ok(z1), ok(z2)) -> ok(U82(z0, z1, z2)) 40.53/11.15 fst(mark(z0)) -> mark(fst(z0)) 40.53/11.15 fst(ok(z0)) -> ok(fst(z0)) 40.53/11.15 natsFrom(mark(z0)) -> mark(natsFrom(z0)) 40.53/11.15 natsFrom(ok(z0)) -> ok(natsFrom(z0)) 40.53/11.15 s(mark(z0)) -> mark(s(z0)) 40.53/11.15 s(ok(z0)) -> ok(s(z0)) 40.53/11.15 sel(mark(z0), z1) -> mark(sel(z0, z1)) 40.53/11.15 sel(z0, mark(z1)) -> mark(sel(z0, z1)) 40.53/11.15 sel(ok(z0), ok(z1)) -> ok(sel(z0, z1)) 40.53/11.15 tail(mark(z0)) -> mark(tail(z0)) 40.53/11.15 tail(ok(z0)) -> ok(tail(z0)) 40.53/11.15 take(mark(z0), z1) -> mark(take(z0, z1)) 40.53/11.15 take(z0, mark(z1)) -> mark(take(z0, z1)) 40.53/11.15 take(ok(z0), ok(z1)) -> ok(take(z0, z1)) 40.53/11.15 proper(tt) -> ok(tt) 40.53/11.15 proper(0) -> ok(0) 40.53/11.15 proper(nil) -> ok(nil) 40.53/11.15 top(mark(z0)) -> top(proper(z0)) 40.53/11.15 top(ok(z0)) -> top(active(z0)) 40.53/11.15 Tuples: 40.53/11.15 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.15 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.15 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.15 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.15 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.15 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.15 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.15 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.15 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.15 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.15 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.15 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.15 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.15 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.15 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.15 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.15 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.15 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.15 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.15 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.15 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.15 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.15 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.15 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.15 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.15 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.15 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.15 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.15 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.15 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.15 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.15 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.15 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.15 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.15 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.15 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.15 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.15 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.15 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.15 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.15 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.15 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.15 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.15 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.15 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.15 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.15 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.15 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.15 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.15 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.15 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.15 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.15 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.15 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.15 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.15 S(mark(z0)) -> c55(S(z0)) 40.53/11.15 S(ok(z0)) -> c56(S(z0)) 40.53/11.15 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.15 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.15 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.15 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.15 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.15 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.15 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.15 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.15 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.15 S tuples: 40.53/11.15 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.15 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.15 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.15 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.15 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.15 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.15 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.15 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.15 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.15 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.15 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.15 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.15 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.15 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.15 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.15 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.15 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.15 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.15 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.15 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.15 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.15 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.15 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.15 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.15 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.15 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.15 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.15 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.15 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.15 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.15 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.15 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 K tuples:none 40.53/11.16 Defined Rule Symbols: U11_3, U12_3, snd_1, splitAt_2, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, head_1, afterNth_2, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, pair_2, cons_2, U71_2, U72_2, U81_3, U82_3, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, proper_1, top_1 40.53/11.16 40.53/11.16 Defined Pair Symbols: U11'_3, U12'_3, SND_1, SPLITAT_2, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, HEAD_1, AFTERNTH_2, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, PAIR_2, CONS_2, U71'_2, U72'_2, U81'_3, U82'_3, FST_1, NATSFROM_1, S_1, SEL_2, TAIL_1, TAKE_2, TOP_1 40.53/11.16 40.53/11.16 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_1, c42_1, c43_1, c44_1, c45_1, c46_1, c47_1, c48_1, c49_1, c50_1, c51_1, c52_1, c53_1, c54_1, c55_1, c56_1, c57_1, c58_1, c59_1, c60_1, c61_1, c62_1, c63_1, c64_1, c68_1 40.53/11.16 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (11) CdtUsableRulesProof (BOTH BOUNDS(ID, ID)) 40.53/11.16 The following rules are not usable and were removed: 40.53/11.16 U11(mark(z0), z1, z2) -> mark(U11(z0, z1, z2)) 40.53/11.16 U11(ok(z0), ok(z1), ok(z2)) -> ok(U11(z0, z1, z2)) 40.53/11.16 U12(mark(z0), z1, z2) -> mark(U12(z0, z1, z2)) 40.53/11.16 U12(ok(z0), ok(z1), ok(z2)) -> ok(U12(z0, z1, z2)) 40.53/11.16 snd(mark(z0)) -> mark(snd(z0)) 40.53/11.16 snd(ok(z0)) -> ok(snd(z0)) 40.53/11.16 splitAt(mark(z0), z1) -> mark(splitAt(z0, z1)) 40.53/11.16 splitAt(z0, mark(z1)) -> mark(splitAt(z0, z1)) 40.53/11.16 splitAt(ok(z0), ok(z1)) -> ok(splitAt(z0, z1)) 40.53/11.16 U21(mark(z0), z1) -> mark(U21(z0, z1)) 40.53/11.16 U21(ok(z0), ok(z1)) -> ok(U21(z0, z1)) 40.53/11.16 U22(mark(z0), z1) -> mark(U22(z0, z1)) 40.53/11.16 U22(ok(z0), ok(z1)) -> ok(U22(z0, z1)) 40.53/11.16 U31(mark(z0), z1) -> mark(U31(z0, z1)) 40.53/11.16 U31(ok(z0), ok(z1)) -> ok(U31(z0, z1)) 40.53/11.16 U32(mark(z0), z1) -> mark(U32(z0, z1)) 40.53/11.16 U32(ok(z0), ok(z1)) -> ok(U32(z0, z1)) 40.53/11.16 U41(mark(z0), z1, z2) -> mark(U41(z0, z1, z2)) 40.53/11.16 U41(ok(z0), ok(z1), ok(z2)) -> ok(U41(z0, z1, z2)) 40.53/11.16 U42(mark(z0), z1, z2) -> mark(U42(z0, z1, z2)) 40.53/11.16 U42(ok(z0), ok(z1), ok(z2)) -> ok(U42(z0, z1, z2)) 40.53/11.16 head(mark(z0)) -> mark(head(z0)) 40.53/11.16 head(ok(z0)) -> ok(head(z0)) 40.53/11.16 afterNth(mark(z0), z1) -> mark(afterNth(z0, z1)) 40.53/11.16 afterNth(z0, mark(z1)) -> mark(afterNth(z0, z1)) 40.53/11.16 afterNth(ok(z0), ok(z1)) -> ok(afterNth(z0, z1)) 40.53/11.16 U51(mark(z0), z1) -> mark(U51(z0, z1)) 40.53/11.16 U51(ok(z0), ok(z1)) -> ok(U51(z0, z1)) 40.53/11.16 U52(mark(z0), z1) -> mark(U52(z0, z1)) 40.53/11.16 U52(ok(z0), ok(z1)) -> ok(U52(z0, z1)) 40.53/11.16 U61(mark(z0), z1, z2, z3) -> mark(U61(z0, z1, z2, z3)) 40.53/11.16 U61(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U61(z0, z1, z2, z3)) 40.53/11.16 U62(mark(z0), z1, z2, z3) -> mark(U62(z0, z1, z2, z3)) 40.53/11.16 U62(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U62(z0, z1, z2, z3)) 40.53/11.16 U63(mark(z0), z1, z2, z3) -> mark(U63(z0, z1, z2, z3)) 40.53/11.16 U63(ok(z0), ok(z1), ok(z2), ok(z3)) -> ok(U63(z0, z1, z2, z3)) 40.53/11.16 U64(mark(z0), z1) -> mark(U64(z0, z1)) 40.53/11.16 U64(ok(z0), ok(z1)) -> ok(U64(z0, z1)) 40.53/11.16 pair(mark(z0), z1) -> mark(pair(z0, z1)) 40.53/11.16 pair(z0, mark(z1)) -> mark(pair(z0, z1)) 40.53/11.16 pair(ok(z0), ok(z1)) -> ok(pair(z0, z1)) 40.53/11.16 cons(mark(z0), z1) -> mark(cons(z0, z1)) 40.53/11.16 cons(ok(z0), ok(z1)) -> ok(cons(z0, z1)) 40.53/11.16 U71(mark(z0), z1) -> mark(U71(z0, z1)) 40.53/11.16 U71(ok(z0), ok(z1)) -> ok(U71(z0, z1)) 40.53/11.16 U72(mark(z0), z1) -> mark(U72(z0, z1)) 40.53/11.16 U72(ok(z0), ok(z1)) -> ok(U72(z0, z1)) 40.53/11.16 U81(mark(z0), z1, z2) -> mark(U81(z0, z1, z2)) 40.53/11.16 U81(ok(z0), ok(z1), ok(z2)) -> ok(U81(z0, z1, z2)) 40.53/11.16 U82(mark(z0), z1, z2) -> mark(U82(z0, z1, z2)) 40.53/11.16 U82(ok(z0), ok(z1), ok(z2)) -> ok(U82(z0, z1, z2)) 40.53/11.16 fst(mark(z0)) -> mark(fst(z0)) 40.53/11.16 fst(ok(z0)) -> ok(fst(z0)) 40.53/11.16 natsFrom(mark(z0)) -> mark(natsFrom(z0)) 40.53/11.16 natsFrom(ok(z0)) -> ok(natsFrom(z0)) 40.53/11.16 s(mark(z0)) -> mark(s(z0)) 40.53/11.16 s(ok(z0)) -> ok(s(z0)) 40.53/11.16 sel(mark(z0), z1) -> mark(sel(z0, z1)) 40.53/11.16 sel(z0, mark(z1)) -> mark(sel(z0, z1)) 40.53/11.16 sel(ok(z0), ok(z1)) -> ok(sel(z0, z1)) 40.53/11.16 tail(mark(z0)) -> mark(tail(z0)) 40.53/11.16 tail(ok(z0)) -> ok(tail(z0)) 40.53/11.16 take(mark(z0), z1) -> mark(take(z0, z1)) 40.53/11.16 take(z0, mark(z1)) -> mark(take(z0, z1)) 40.53/11.16 take(ok(z0), ok(z1)) -> ok(take(z0, z1)) 40.53/11.16 top(mark(z0)) -> top(proper(z0)) 40.53/11.16 top(ok(z0)) -> top(active(z0)) 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (12) 40.53/11.16 Obligation: 40.53/11.16 Complexity Dependency Tuples Problem 40.53/11.16 40.53/11.16 Rules: 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 Tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 S tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 K tuples:none 40.53/11.16 Defined Rule Symbols: proper_1 40.53/11.16 40.53/11.16 Defined Pair Symbols: U11'_3, U12'_3, SND_1, SPLITAT_2, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, HEAD_1, AFTERNTH_2, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, PAIR_2, CONS_2, U71'_2, U72'_2, U81'_3, U82'_3, FST_1, NATSFROM_1, S_1, SEL_2, TAIL_1, TAKE_2, TOP_1 40.53/11.16 40.53/11.16 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_1, c42_1, c43_1, c44_1, c45_1, c46_1, c47_1, c48_1, c49_1, c50_1, c51_1, c52_1, c53_1, c54_1, c55_1, c56_1, c57_1, c58_1, c59_1, c60_1, c61_1, c62_1, c63_1, c64_1, c68_1 40.53/11.16 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (13) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 40.53/11.16 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 We considered the (Usable) Rules: 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 And the Tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 The order we found is given by the following interpretation: 40.53/11.16 40.53/11.16 Polynomial interpretation : 40.53/11.16 40.53/11.16 POL(0) = [1] 40.53/11.16 POL(AFTERNTH(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(CONS(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(FST(x_1)) = x_1 40.53/11.16 POL(HEAD(x_1)) = x_1 40.53/11.16 POL(NATSFROM(x_1)) = x_1 40.53/11.16 POL(PAIR(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(S(x_1)) = x_1 40.53/11.16 POL(SEL(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(SND(x_1)) = x_1 40.53/11.16 POL(SPLITAT(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(TAIL(x_1)) = x_1 40.53/11.16 POL(TAKE(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(TOP(x_1)) = x_1 40.53/11.16 POL(U11'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U12'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U21'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U22'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U31'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U32'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U41'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U42'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U51'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U52'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U61'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 40.53/11.16 POL(U62'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 40.53/11.16 POL(U63'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 40.53/11.16 POL(U64'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U71'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U72'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U81'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U82'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(c(x_1)) = x_1 40.53/11.16 POL(c1(x_1)) = x_1 40.53/11.16 POL(c10(x_1)) = x_1 40.53/11.16 POL(c11(x_1)) = x_1 40.53/11.16 POL(c12(x_1)) = x_1 40.53/11.16 POL(c13(x_1)) = x_1 40.53/11.16 POL(c14(x_1)) = x_1 40.53/11.16 POL(c15(x_1)) = x_1 40.53/11.16 POL(c16(x_1)) = x_1 40.53/11.16 POL(c17(x_1)) = x_1 40.53/11.16 POL(c18(x_1)) = x_1 40.53/11.16 POL(c19(x_1)) = x_1 40.53/11.16 POL(c2(x_1)) = x_1 40.53/11.16 POL(c20(x_1)) = x_1 40.53/11.16 POL(c21(x_1)) = x_1 40.53/11.16 POL(c22(x_1)) = x_1 40.53/11.16 POL(c23(x_1)) = x_1 40.53/11.16 POL(c24(x_1)) = x_1 40.53/11.16 POL(c25(x_1)) = x_1 40.53/11.16 POL(c26(x_1)) = x_1 40.53/11.16 POL(c27(x_1)) = x_1 40.53/11.16 POL(c28(x_1)) = x_1 40.53/11.16 POL(c29(x_1)) = x_1 40.53/11.16 POL(c3(x_1)) = x_1 40.53/11.16 POL(c30(x_1)) = x_1 40.53/11.16 POL(c31(x_1)) = x_1 40.53/11.16 POL(c32(x_1)) = x_1 40.53/11.16 POL(c33(x_1)) = x_1 40.53/11.16 POL(c34(x_1)) = x_1 40.53/11.16 POL(c35(x_1)) = x_1 40.53/11.16 POL(c36(x_1)) = x_1 40.53/11.16 POL(c37(x_1)) = x_1 40.53/11.16 POL(c38(x_1)) = x_1 40.53/11.16 POL(c39(x_1)) = x_1 40.53/11.16 POL(c4(x_1)) = x_1 40.53/11.16 POL(c40(x_1)) = x_1 40.53/11.16 POL(c41(x_1)) = x_1 40.53/11.16 POL(c42(x_1)) = x_1 40.53/11.16 POL(c43(x_1)) = x_1 40.53/11.16 POL(c44(x_1)) = x_1 40.53/11.16 POL(c45(x_1)) = x_1 40.53/11.16 POL(c46(x_1)) = x_1 40.53/11.16 POL(c47(x_1)) = x_1 40.53/11.16 POL(c48(x_1)) = x_1 40.53/11.16 POL(c49(x_1)) = x_1 40.53/11.16 POL(c5(x_1)) = x_1 40.53/11.16 POL(c50(x_1)) = x_1 40.53/11.16 POL(c51(x_1)) = x_1 40.53/11.16 POL(c52(x_1)) = x_1 40.53/11.16 POL(c53(x_1)) = x_1 40.53/11.16 POL(c54(x_1)) = x_1 40.53/11.16 POL(c55(x_1)) = x_1 40.53/11.16 POL(c56(x_1)) = x_1 40.53/11.16 POL(c57(x_1)) = x_1 40.53/11.16 POL(c58(x_1)) = x_1 40.53/11.16 POL(c59(x_1)) = x_1 40.53/11.16 POL(c6(x_1)) = x_1 40.53/11.16 POL(c60(x_1)) = x_1 40.53/11.16 POL(c61(x_1)) = x_1 40.53/11.16 POL(c62(x_1)) = x_1 40.53/11.16 POL(c63(x_1)) = x_1 40.53/11.16 POL(c64(x_1)) = x_1 40.53/11.16 POL(c68(x_1)) = x_1 40.53/11.16 POL(c7(x_1)) = x_1 40.53/11.16 POL(c8(x_1)) = x_1 40.53/11.16 POL(c9(x_1)) = x_1 40.53/11.16 POL(mark(x_1)) = [1] + x_1 40.53/11.16 POL(nil) = [1] 40.53/11.16 POL(ok(x_1)) = [1] + x_1 40.53/11.16 POL(proper(x_1)) = [1] + x_1 40.53/11.16 POL(tt) = [1] 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (14) 40.53/11.16 Obligation: 40.53/11.16 Complexity Dependency Tuples Problem 40.53/11.16 40.53/11.16 Rules: 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 Tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 S tuples: 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 K tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 Defined Rule Symbols: proper_1 40.53/11.16 40.53/11.16 Defined Pair Symbols: U11'_3, U12'_3, SND_1, SPLITAT_2, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, HEAD_1, AFTERNTH_2, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, PAIR_2, CONS_2, U71'_2, U72'_2, U81'_3, U82'_3, FST_1, NATSFROM_1, S_1, SEL_2, TAIL_1, TAKE_2, TOP_1 40.53/11.16 40.53/11.16 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_1, c42_1, c43_1, c44_1, c45_1, c46_1, c47_1, c48_1, c49_1, c50_1, c51_1, c52_1, c53_1, c54_1, c55_1, c56_1, c57_1, c58_1, c59_1, c60_1, c61_1, c62_1, c63_1, c64_1, c68_1 40.53/11.16 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (15) CdtRuleRemovalProof (UPPER BOUND(ADD(n^1))) 40.53/11.16 Found a reduction pair which oriented the following tuples strictly. Hence they can be removed from S. 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 We considered the (Usable) Rules: 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 And the Tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 The order we found is given by the following interpretation: 40.53/11.16 40.53/11.16 Polynomial interpretation : 40.53/11.16 40.53/11.16 POL(0) = [1] 40.53/11.16 POL(AFTERNTH(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(CONS(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(FST(x_1)) = x_1 40.53/11.16 POL(HEAD(x_1)) = x_1 40.53/11.16 POL(NATSFROM(x_1)) = x_1 40.53/11.16 POL(PAIR(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(S(x_1)) = x_1 40.53/11.16 POL(SEL(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(SND(x_1)) = x_1 40.53/11.16 POL(SPLITAT(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(TAIL(x_1)) = x_1 40.53/11.16 POL(TAKE(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(TOP(x_1)) = x_1 40.53/11.16 POL(U11'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U12'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U21'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U22'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U31'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U32'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U41'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U42'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U51'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U52'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U61'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 40.53/11.16 POL(U62'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 40.53/11.16 POL(U63'(x_1, x_2, x_3, x_4)) = x_1 + x_2 + x_3 + x_4 40.53/11.16 POL(U64'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U71'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U72'(x_1, x_2)) = x_1 + x_2 40.53/11.16 POL(U81'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(U82'(x_1, x_2, x_3)) = x_1 + x_2 + x_3 40.53/11.16 POL(c(x_1)) = x_1 40.53/11.16 POL(c1(x_1)) = x_1 40.53/11.16 POL(c10(x_1)) = x_1 40.53/11.16 POL(c11(x_1)) = x_1 40.53/11.16 POL(c12(x_1)) = x_1 40.53/11.16 POL(c13(x_1)) = x_1 40.53/11.16 POL(c14(x_1)) = x_1 40.53/11.16 POL(c15(x_1)) = x_1 40.53/11.16 POL(c16(x_1)) = x_1 40.53/11.16 POL(c17(x_1)) = x_1 40.53/11.16 POL(c18(x_1)) = x_1 40.53/11.16 POL(c19(x_1)) = x_1 40.53/11.16 POL(c2(x_1)) = x_1 40.53/11.16 POL(c20(x_1)) = x_1 40.53/11.16 POL(c21(x_1)) = x_1 40.53/11.16 POL(c22(x_1)) = x_1 40.53/11.16 POL(c23(x_1)) = x_1 40.53/11.16 POL(c24(x_1)) = x_1 40.53/11.16 POL(c25(x_1)) = x_1 40.53/11.16 POL(c26(x_1)) = x_1 40.53/11.16 POL(c27(x_1)) = x_1 40.53/11.16 POL(c28(x_1)) = x_1 40.53/11.16 POL(c29(x_1)) = x_1 40.53/11.16 POL(c3(x_1)) = x_1 40.53/11.16 POL(c30(x_1)) = x_1 40.53/11.16 POL(c31(x_1)) = x_1 40.53/11.16 POL(c32(x_1)) = x_1 40.53/11.16 POL(c33(x_1)) = x_1 40.53/11.16 POL(c34(x_1)) = x_1 40.53/11.16 POL(c35(x_1)) = x_1 40.53/11.16 POL(c36(x_1)) = x_1 40.53/11.16 POL(c37(x_1)) = x_1 40.53/11.16 POL(c38(x_1)) = x_1 40.53/11.16 POL(c39(x_1)) = x_1 40.53/11.16 POL(c4(x_1)) = x_1 40.53/11.16 POL(c40(x_1)) = x_1 40.53/11.16 POL(c41(x_1)) = x_1 40.53/11.16 POL(c42(x_1)) = x_1 40.53/11.16 POL(c43(x_1)) = x_1 40.53/11.16 POL(c44(x_1)) = x_1 40.53/11.16 POL(c45(x_1)) = x_1 40.53/11.16 POL(c46(x_1)) = x_1 40.53/11.16 POL(c47(x_1)) = x_1 40.53/11.16 POL(c48(x_1)) = x_1 40.53/11.16 POL(c49(x_1)) = x_1 40.53/11.16 POL(c5(x_1)) = x_1 40.53/11.16 POL(c50(x_1)) = x_1 40.53/11.16 POL(c51(x_1)) = x_1 40.53/11.16 POL(c52(x_1)) = x_1 40.53/11.16 POL(c53(x_1)) = x_1 40.53/11.16 POL(c54(x_1)) = x_1 40.53/11.16 POL(c55(x_1)) = x_1 40.53/11.16 POL(c56(x_1)) = x_1 40.53/11.16 POL(c57(x_1)) = x_1 40.53/11.16 POL(c58(x_1)) = x_1 40.53/11.16 POL(c59(x_1)) = x_1 40.53/11.16 POL(c6(x_1)) = x_1 40.53/11.16 POL(c60(x_1)) = x_1 40.53/11.16 POL(c61(x_1)) = x_1 40.53/11.16 POL(c62(x_1)) = x_1 40.53/11.16 POL(c63(x_1)) = x_1 40.53/11.16 POL(c64(x_1)) = x_1 40.53/11.16 POL(c68(x_1)) = x_1 40.53/11.16 POL(c7(x_1)) = x_1 40.53/11.16 POL(c8(x_1)) = x_1 40.53/11.16 POL(c9(x_1)) = x_1 40.53/11.16 POL(mark(x_1)) = [1] + x_1 40.53/11.16 POL(nil) = [1] 40.53/11.16 POL(ok(x_1)) = x_1 40.53/11.16 POL(proper(x_1)) = x_1 40.53/11.16 POL(tt) = [1] 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (16) 40.53/11.16 Obligation: 40.53/11.16 Complexity Dependency Tuples Problem 40.53/11.16 40.53/11.16 Rules: 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 Tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 S tuples:none 40.53/11.16 K tuples: 40.53/11.16 U11'(mark(z0), z1, z2) -> c(U11'(z0, z1, z2)) 40.53/11.16 U11'(ok(z0), ok(z1), ok(z2)) -> c1(U11'(z0, z1, z2)) 40.53/11.16 U12'(mark(z0), z1, z2) -> c2(U12'(z0, z1, z2)) 40.53/11.16 U12'(ok(z0), ok(z1), ok(z2)) -> c3(U12'(z0, z1, z2)) 40.53/11.16 SND(mark(z0)) -> c4(SND(z0)) 40.53/11.16 SND(ok(z0)) -> c5(SND(z0)) 40.53/11.16 SPLITAT(mark(z0), z1) -> c6(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(z0, mark(z1)) -> c7(SPLITAT(z0, z1)) 40.53/11.16 SPLITAT(ok(z0), ok(z1)) -> c8(SPLITAT(z0, z1)) 40.53/11.16 U21'(mark(z0), z1) -> c9(U21'(z0, z1)) 40.53/11.16 U21'(ok(z0), ok(z1)) -> c10(U21'(z0, z1)) 40.53/11.16 U22'(mark(z0), z1) -> c11(U22'(z0, z1)) 40.53/11.16 U22'(ok(z0), ok(z1)) -> c12(U22'(z0, z1)) 40.53/11.16 U31'(mark(z0), z1) -> c13(U31'(z0, z1)) 40.53/11.16 U31'(ok(z0), ok(z1)) -> c14(U31'(z0, z1)) 40.53/11.16 U32'(mark(z0), z1) -> c15(U32'(z0, z1)) 40.53/11.16 U32'(ok(z0), ok(z1)) -> c16(U32'(z0, z1)) 40.53/11.16 U41'(mark(z0), z1, z2) -> c17(U41'(z0, z1, z2)) 40.53/11.16 U41'(ok(z0), ok(z1), ok(z2)) -> c18(U41'(z0, z1, z2)) 40.53/11.16 U42'(mark(z0), z1, z2) -> c19(U42'(z0, z1, z2)) 40.53/11.16 U42'(ok(z0), ok(z1), ok(z2)) -> c20(U42'(z0, z1, z2)) 40.53/11.16 HEAD(mark(z0)) -> c21(HEAD(z0)) 40.53/11.16 HEAD(ok(z0)) -> c22(HEAD(z0)) 40.53/11.16 AFTERNTH(mark(z0), z1) -> c23(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(z0, mark(z1)) -> c24(AFTERNTH(z0, z1)) 40.53/11.16 AFTERNTH(ok(z0), ok(z1)) -> c25(AFTERNTH(z0, z1)) 40.53/11.16 U51'(mark(z0), z1) -> c26(U51'(z0, z1)) 40.53/11.16 U51'(ok(z0), ok(z1)) -> c27(U51'(z0, z1)) 40.53/11.16 U52'(mark(z0), z1) -> c28(U52'(z0, z1)) 40.53/11.16 U52'(ok(z0), ok(z1)) -> c29(U52'(z0, z1)) 40.53/11.16 U61'(mark(z0), z1, z2, z3) -> c30(U61'(z0, z1, z2, z3)) 40.53/11.16 U61'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c31(U61'(z0, z1, z2, z3)) 40.53/11.16 U62'(mark(z0), z1, z2, z3) -> c32(U62'(z0, z1, z2, z3)) 40.53/11.16 U62'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c33(U62'(z0, z1, z2, z3)) 40.53/11.16 U63'(mark(z0), z1, z2, z3) -> c34(U63'(z0, z1, z2, z3)) 40.53/11.16 U63'(ok(z0), ok(z1), ok(z2), ok(z3)) -> c35(U63'(z0, z1, z2, z3)) 40.53/11.16 U64'(mark(z0), z1) -> c36(U64'(z0, z1)) 40.53/11.16 U64'(ok(z0), ok(z1)) -> c37(U64'(z0, z1)) 40.53/11.16 PAIR(mark(z0), z1) -> c38(PAIR(z0, z1)) 40.53/11.16 PAIR(z0, mark(z1)) -> c39(PAIR(z0, z1)) 40.53/11.16 PAIR(ok(z0), ok(z1)) -> c40(PAIR(z0, z1)) 40.53/11.16 CONS(mark(z0), z1) -> c41(CONS(z0, z1)) 40.53/11.16 CONS(ok(z0), ok(z1)) -> c42(CONS(z0, z1)) 40.53/11.16 U71'(mark(z0), z1) -> c43(U71'(z0, z1)) 40.53/11.16 U71'(ok(z0), ok(z1)) -> c44(U71'(z0, z1)) 40.53/11.16 U72'(mark(z0), z1) -> c45(U72'(z0, z1)) 40.53/11.16 U72'(ok(z0), ok(z1)) -> c46(U72'(z0, z1)) 40.53/11.16 U81'(mark(z0), z1, z2) -> c47(U81'(z0, z1, z2)) 40.53/11.16 U81'(ok(z0), ok(z1), ok(z2)) -> c48(U81'(z0, z1, z2)) 40.53/11.16 U82'(mark(z0), z1, z2) -> c49(U82'(z0, z1, z2)) 40.53/11.16 U82'(ok(z0), ok(z1), ok(z2)) -> c50(U82'(z0, z1, z2)) 40.53/11.16 FST(mark(z0)) -> c51(FST(z0)) 40.53/11.16 FST(ok(z0)) -> c52(FST(z0)) 40.53/11.16 NATSFROM(mark(z0)) -> c53(NATSFROM(z0)) 40.53/11.16 NATSFROM(ok(z0)) -> c54(NATSFROM(z0)) 40.53/11.16 S(mark(z0)) -> c55(S(z0)) 40.53/11.16 S(ok(z0)) -> c56(S(z0)) 40.53/11.16 SEL(mark(z0), z1) -> c57(SEL(z0, z1)) 40.53/11.16 SEL(z0, mark(z1)) -> c58(SEL(z0, z1)) 40.53/11.16 SEL(ok(z0), ok(z1)) -> c59(SEL(z0, z1)) 40.53/11.16 TAIL(mark(z0)) -> c60(TAIL(z0)) 40.53/11.16 TAIL(ok(z0)) -> c61(TAIL(z0)) 40.53/11.16 TAKE(mark(z0), z1) -> c62(TAKE(z0, z1)) 40.53/11.16 TAKE(z0, mark(z1)) -> c63(TAKE(z0, z1)) 40.53/11.16 TAKE(ok(z0), ok(z1)) -> c64(TAKE(z0, z1)) 40.53/11.16 TOP(mark(z0)) -> c68(TOP(proper(z0))) 40.53/11.16 Defined Rule Symbols: proper_1 40.53/11.16 40.53/11.16 Defined Pair Symbols: U11'_3, U12'_3, SND_1, SPLITAT_2, U21'_2, U22'_2, U31'_2, U32'_2, U41'_3, U42'_3, HEAD_1, AFTERNTH_2, U51'_2, U52'_2, U61'_4, U62'_4, U63'_4, U64'_2, PAIR_2, CONS_2, U71'_2, U72'_2, U81'_3, U82'_3, FST_1, NATSFROM_1, S_1, SEL_2, TAIL_1, TAKE_2, TOP_1 40.53/11.16 40.53/11.16 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_1, c42_1, c43_1, c44_1, c45_1, c46_1, c47_1, c48_1, c49_1, c50_1, c51_1, c52_1, c53_1, c54_1, c55_1, c56_1, c57_1, c58_1, c59_1, c60_1, c61_1, c62_1, c63_1, c64_1, c68_1 40.53/11.16 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (17) SIsEmptyProof (BOTH BOUNDS(ID, ID)) 40.53/11.16 The set S is empty 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (18) 40.53/11.16 BOUNDS(1, 1) 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (19) RelTrsToDecreasingLoopProblemProof (LOWER BOUND(ID)) 40.53/11.16 Transformed a relative TRS into a decreasing-loop problem. 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (20) 40.53/11.16 Obligation: 40.53/11.16 Analyzing the following TRS for decreasing loops: 40.53/11.16 40.53/11.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 40.53/11.16 40.53/11.16 40.53/11.16 The TRS R consists of the following rules: 40.53/11.16 40.53/11.16 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 40.53/11.16 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 40.53/11.16 active(U21(tt, X)) -> mark(U22(tt, X)) 40.53/11.16 active(U22(tt, X)) -> mark(X) 40.53/11.16 active(U31(tt, N)) -> mark(U32(tt, N)) 40.53/11.16 active(U32(tt, N)) -> mark(N) 40.53/11.16 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 40.53/11.16 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 40.53/11.16 active(U51(tt, Y)) -> mark(U52(tt, Y)) 40.53/11.16 active(U52(tt, Y)) -> mark(Y) 40.53/11.16 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 40.53/11.16 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 40.53/11.16 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 40.53/11.16 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 40.53/11.16 active(U71(tt, XS)) -> mark(U72(tt, XS)) 40.53/11.16 active(U72(tt, XS)) -> mark(XS) 40.53/11.16 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 40.53/11.16 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 40.53/11.16 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 40.53/11.16 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 40.53/11.16 active(head(cons(N, XS))) -> mark(U31(tt, N)) 40.53/11.16 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 40.53/11.16 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 40.53/11.16 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 40.53/11.16 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 40.53/11.16 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 40.53/11.16 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 40.53/11.16 active(take(N, XS)) -> mark(U81(tt, N, XS)) 40.53/11.16 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 40.53/11.16 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 40.53/11.16 active(snd(X)) -> snd(active(X)) 40.53/11.16 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 40.53/11.16 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 40.53/11.16 active(U21(X1, X2)) -> U21(active(X1), X2) 40.53/11.16 active(U22(X1, X2)) -> U22(active(X1), X2) 40.53/11.16 active(U31(X1, X2)) -> U31(active(X1), X2) 40.53/11.16 active(U32(X1, X2)) -> U32(active(X1), X2) 40.53/11.16 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 40.53/11.16 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 40.53/11.16 active(head(X)) -> head(active(X)) 40.53/11.16 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 40.53/11.16 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 40.53/11.16 active(U51(X1, X2)) -> U51(active(X1), X2) 40.53/11.16 active(U52(X1, X2)) -> U52(active(X1), X2) 40.53/11.16 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 40.53/11.16 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 40.53/11.16 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 40.53/11.16 active(U64(X1, X2)) -> U64(active(X1), X2) 40.53/11.16 active(pair(X1, X2)) -> pair(active(X1), X2) 40.53/11.16 active(pair(X1, X2)) -> pair(X1, active(X2)) 40.53/11.16 active(cons(X1, X2)) -> cons(active(X1), X2) 40.53/11.16 active(U71(X1, X2)) -> U71(active(X1), X2) 40.53/11.16 active(U72(X1, X2)) -> U72(active(X1), X2) 40.53/11.16 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 40.53/11.16 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 40.53/11.16 active(fst(X)) -> fst(active(X)) 40.53/11.16 active(natsFrom(X)) -> natsFrom(active(X)) 40.53/11.16 active(s(X)) -> s(active(X)) 40.53/11.16 active(sel(X1, X2)) -> sel(active(X1), X2) 40.53/11.16 active(sel(X1, X2)) -> sel(X1, active(X2)) 40.53/11.16 active(tail(X)) -> tail(active(X)) 40.53/11.16 active(take(X1, X2)) -> take(active(X1), X2) 40.53/11.16 active(take(X1, X2)) -> take(X1, active(X2)) 40.53/11.16 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 40.53/11.16 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 40.53/11.16 snd(mark(X)) -> mark(snd(X)) 40.53/11.16 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 40.53/11.16 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 40.53/11.16 U21(mark(X1), X2) -> mark(U21(X1, X2)) 40.53/11.16 U22(mark(X1), X2) -> mark(U22(X1, X2)) 40.53/11.16 U31(mark(X1), X2) -> mark(U31(X1, X2)) 40.53/11.16 U32(mark(X1), X2) -> mark(U32(X1, X2)) 40.53/11.16 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 40.53/11.16 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 40.53/11.16 head(mark(X)) -> mark(head(X)) 40.53/11.16 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 40.53/11.16 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 40.53/11.16 U51(mark(X1), X2) -> mark(U51(X1, X2)) 40.53/11.16 U52(mark(X1), X2) -> mark(U52(X1, X2)) 40.53/11.16 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 40.53/11.16 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 40.53/11.16 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 40.53/11.16 U64(mark(X1), X2) -> mark(U64(X1, X2)) 40.53/11.16 pair(mark(X1), X2) -> mark(pair(X1, X2)) 40.53/11.16 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 40.53/11.16 cons(mark(X1), X2) -> mark(cons(X1, X2)) 40.53/11.16 U71(mark(X1), X2) -> mark(U71(X1, X2)) 40.53/11.16 U72(mark(X1), X2) -> mark(U72(X1, X2)) 40.53/11.16 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 40.53/11.16 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 40.53/11.16 fst(mark(X)) -> mark(fst(X)) 40.53/11.16 natsFrom(mark(X)) -> mark(natsFrom(X)) 40.53/11.16 s(mark(X)) -> mark(s(X)) 40.53/11.16 sel(mark(X1), X2) -> mark(sel(X1, X2)) 40.53/11.16 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 40.53/11.16 tail(mark(X)) -> mark(tail(X)) 40.53/11.16 take(mark(X1), X2) -> mark(take(X1, X2)) 40.53/11.16 take(X1, mark(X2)) -> mark(take(X1, X2)) 40.53/11.16 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(snd(X)) -> snd(proper(X)) 40.53/11.16 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 40.53/11.16 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 40.53/11.16 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 40.53/11.16 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 40.53/11.16 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 40.53/11.16 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(head(X)) -> head(proper(X)) 40.53/11.16 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 40.53/11.16 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 40.53/11.16 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 40.53/11.16 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 40.53/11.16 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 40.53/11.16 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 40.53/11.16 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 40.53/11.16 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 40.53/11.16 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(fst(X)) -> fst(proper(X)) 40.53/11.16 proper(natsFrom(X)) -> natsFrom(proper(X)) 40.53/11.16 proper(s(X)) -> s(proper(X)) 40.53/11.16 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 proper(tail(X)) -> tail(proper(X)) 40.53/11.16 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 40.53/11.16 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 40.53/11.16 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 40.53/11.16 snd(ok(X)) -> ok(snd(X)) 40.53/11.16 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 40.53/11.16 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 40.53/11.16 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 40.53/11.16 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 40.53/11.16 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 40.53/11.16 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 40.53/11.16 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 40.53/11.16 head(ok(X)) -> ok(head(X)) 40.53/11.16 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 40.53/11.16 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 40.53/11.16 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 40.53/11.16 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 40.53/11.16 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 40.53/11.16 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 40.53/11.16 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 40.53/11.16 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 40.53/11.16 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 40.53/11.16 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 40.53/11.16 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 40.53/11.16 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 40.53/11.16 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 40.53/11.16 fst(ok(X)) -> ok(fst(X)) 40.53/11.16 natsFrom(ok(X)) -> ok(natsFrom(X)) 40.53/11.16 s(ok(X)) -> ok(s(X)) 40.53/11.16 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 40.53/11.16 tail(ok(X)) -> ok(tail(X)) 40.53/11.16 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 40.53/11.16 top(mark(X)) -> top(proper(X)) 40.53/11.16 top(ok(X)) -> top(active(X)) 40.53/11.16 40.53/11.16 S is empty. 40.53/11.16 Rewrite Strategy: FULL 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (21) DecreasingLoopProof (LOWER BOUND(ID)) 40.53/11.16 The following loop(s) give(s) rise to the lower bound Omega(n^1): 40.53/11.16 40.53/11.16 The rewrite sequence 40.53/11.16 40.53/11.16 U52(ok(X1), ok(X2)) ->^+ ok(U52(X1, X2)) 40.53/11.16 40.53/11.16 gives rise to a decreasing loop by considering the right hand sides subterm at position [0]. 40.53/11.16 40.53/11.16 The pumping substitution is [X1 / ok(X1), X2 / ok(X2)]. 40.53/11.16 40.53/11.16 The result substitution is [ ]. 40.53/11.16 40.53/11.16 40.53/11.16 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (22) 40.53/11.16 Complex Obligation (BEST) 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (23) 40.53/11.16 Obligation: 40.53/11.16 Proved the lower bound n^1 for the following obligation: 40.53/11.16 40.53/11.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 40.53/11.16 40.53/11.16 40.53/11.16 The TRS R consists of the following rules: 40.53/11.16 40.53/11.16 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 40.53/11.16 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 40.53/11.16 active(U21(tt, X)) -> mark(U22(tt, X)) 40.53/11.16 active(U22(tt, X)) -> mark(X) 40.53/11.16 active(U31(tt, N)) -> mark(U32(tt, N)) 40.53/11.16 active(U32(tt, N)) -> mark(N) 40.53/11.16 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 40.53/11.16 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 40.53/11.16 active(U51(tt, Y)) -> mark(U52(tt, Y)) 40.53/11.16 active(U52(tt, Y)) -> mark(Y) 40.53/11.16 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 40.53/11.16 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 40.53/11.16 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 40.53/11.16 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 40.53/11.16 active(U71(tt, XS)) -> mark(U72(tt, XS)) 40.53/11.16 active(U72(tt, XS)) -> mark(XS) 40.53/11.16 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 40.53/11.16 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 40.53/11.16 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 40.53/11.16 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 40.53/11.16 active(head(cons(N, XS))) -> mark(U31(tt, N)) 40.53/11.16 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 40.53/11.16 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 40.53/11.16 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 40.53/11.16 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 40.53/11.16 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 40.53/11.16 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 40.53/11.16 active(take(N, XS)) -> mark(U81(tt, N, XS)) 40.53/11.16 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 40.53/11.16 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 40.53/11.16 active(snd(X)) -> snd(active(X)) 40.53/11.16 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 40.53/11.16 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 40.53/11.16 active(U21(X1, X2)) -> U21(active(X1), X2) 40.53/11.16 active(U22(X1, X2)) -> U22(active(X1), X2) 40.53/11.16 active(U31(X1, X2)) -> U31(active(X1), X2) 40.53/11.16 active(U32(X1, X2)) -> U32(active(X1), X2) 40.53/11.16 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 40.53/11.16 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 40.53/11.16 active(head(X)) -> head(active(X)) 40.53/11.16 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 40.53/11.16 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 40.53/11.16 active(U51(X1, X2)) -> U51(active(X1), X2) 40.53/11.16 active(U52(X1, X2)) -> U52(active(X1), X2) 40.53/11.16 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 40.53/11.16 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 40.53/11.16 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 40.53/11.16 active(U64(X1, X2)) -> U64(active(X1), X2) 40.53/11.16 active(pair(X1, X2)) -> pair(active(X1), X2) 40.53/11.16 active(pair(X1, X2)) -> pair(X1, active(X2)) 40.53/11.16 active(cons(X1, X2)) -> cons(active(X1), X2) 40.53/11.16 active(U71(X1, X2)) -> U71(active(X1), X2) 40.53/11.16 active(U72(X1, X2)) -> U72(active(X1), X2) 40.53/11.16 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 40.53/11.16 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 40.53/11.16 active(fst(X)) -> fst(active(X)) 40.53/11.16 active(natsFrom(X)) -> natsFrom(active(X)) 40.53/11.16 active(s(X)) -> s(active(X)) 40.53/11.16 active(sel(X1, X2)) -> sel(active(X1), X2) 40.53/11.16 active(sel(X1, X2)) -> sel(X1, active(X2)) 40.53/11.16 active(tail(X)) -> tail(active(X)) 40.53/11.16 active(take(X1, X2)) -> take(active(X1), X2) 40.53/11.16 active(take(X1, X2)) -> take(X1, active(X2)) 40.53/11.16 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 40.53/11.16 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 40.53/11.16 snd(mark(X)) -> mark(snd(X)) 40.53/11.16 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 40.53/11.16 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 40.53/11.16 U21(mark(X1), X2) -> mark(U21(X1, X2)) 40.53/11.16 U22(mark(X1), X2) -> mark(U22(X1, X2)) 40.53/11.16 U31(mark(X1), X2) -> mark(U31(X1, X2)) 40.53/11.16 U32(mark(X1), X2) -> mark(U32(X1, X2)) 40.53/11.16 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 40.53/11.16 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 40.53/11.16 head(mark(X)) -> mark(head(X)) 40.53/11.16 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 40.53/11.16 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 40.53/11.16 U51(mark(X1), X2) -> mark(U51(X1, X2)) 40.53/11.16 U52(mark(X1), X2) -> mark(U52(X1, X2)) 40.53/11.16 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 40.53/11.16 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 40.53/11.16 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 40.53/11.16 U64(mark(X1), X2) -> mark(U64(X1, X2)) 40.53/11.16 pair(mark(X1), X2) -> mark(pair(X1, X2)) 40.53/11.16 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 40.53/11.16 cons(mark(X1), X2) -> mark(cons(X1, X2)) 40.53/11.16 U71(mark(X1), X2) -> mark(U71(X1, X2)) 40.53/11.16 U72(mark(X1), X2) -> mark(U72(X1, X2)) 40.53/11.16 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 40.53/11.16 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 40.53/11.16 fst(mark(X)) -> mark(fst(X)) 40.53/11.16 natsFrom(mark(X)) -> mark(natsFrom(X)) 40.53/11.16 s(mark(X)) -> mark(s(X)) 40.53/11.16 sel(mark(X1), X2) -> mark(sel(X1, X2)) 40.53/11.16 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 40.53/11.16 tail(mark(X)) -> mark(tail(X)) 40.53/11.16 take(mark(X1), X2) -> mark(take(X1, X2)) 40.53/11.16 take(X1, mark(X2)) -> mark(take(X1, X2)) 40.53/11.16 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(snd(X)) -> snd(proper(X)) 40.53/11.16 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 40.53/11.16 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 40.53/11.16 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 40.53/11.16 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 40.53/11.16 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 40.53/11.16 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(head(X)) -> head(proper(X)) 40.53/11.16 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 40.53/11.16 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 40.53/11.16 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 40.53/11.16 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 40.53/11.16 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 40.53/11.16 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 40.53/11.16 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 40.53/11.16 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 40.53/11.16 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(fst(X)) -> fst(proper(X)) 40.53/11.16 proper(natsFrom(X)) -> natsFrom(proper(X)) 40.53/11.16 proper(s(X)) -> s(proper(X)) 40.53/11.16 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 proper(tail(X)) -> tail(proper(X)) 40.53/11.16 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 40.53/11.16 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 40.53/11.16 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 40.53/11.16 snd(ok(X)) -> ok(snd(X)) 40.53/11.16 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 40.53/11.16 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 40.53/11.16 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 40.53/11.16 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 40.53/11.16 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 40.53/11.16 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 40.53/11.16 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 40.53/11.16 head(ok(X)) -> ok(head(X)) 40.53/11.16 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 40.53/11.16 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 40.53/11.16 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 40.53/11.16 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 40.53/11.16 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 40.53/11.16 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 40.53/11.16 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 40.53/11.16 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 40.53/11.16 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 40.53/11.16 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 40.53/11.16 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 40.53/11.16 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 40.53/11.16 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 40.53/11.16 fst(ok(X)) -> ok(fst(X)) 40.53/11.16 natsFrom(ok(X)) -> ok(natsFrom(X)) 40.53/11.16 s(ok(X)) -> ok(s(X)) 40.53/11.16 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 40.53/11.16 tail(ok(X)) -> ok(tail(X)) 40.53/11.16 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 40.53/11.16 top(mark(X)) -> top(proper(X)) 40.53/11.16 top(ok(X)) -> top(active(X)) 40.53/11.16 40.53/11.16 S is empty. 40.53/11.16 Rewrite Strategy: FULL 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (24) LowerBoundPropagationProof (FINISHED) 40.53/11.16 Propagated lower bound. 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (25) 40.53/11.16 BOUNDS(n^1, INF) 40.53/11.16 40.53/11.16 ---------------------------------------- 40.53/11.16 40.53/11.16 (26) 40.53/11.16 Obligation: 40.53/11.16 Analyzing the following TRS for decreasing loops: 40.53/11.16 40.53/11.16 The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(n^1, n^1). 40.53/11.16 40.53/11.16 40.53/11.16 The TRS R consists of the following rules: 40.53/11.16 40.53/11.16 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 40.53/11.16 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 40.53/11.16 active(U21(tt, X)) -> mark(U22(tt, X)) 40.53/11.16 active(U22(tt, X)) -> mark(X) 40.53/11.16 active(U31(tt, N)) -> mark(U32(tt, N)) 40.53/11.16 active(U32(tt, N)) -> mark(N) 40.53/11.16 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 40.53/11.16 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 40.53/11.16 active(U51(tt, Y)) -> mark(U52(tt, Y)) 40.53/11.16 active(U52(tt, Y)) -> mark(Y) 40.53/11.16 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 40.53/11.16 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 40.53/11.16 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 40.53/11.16 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 40.53/11.16 active(U71(tt, XS)) -> mark(U72(tt, XS)) 40.53/11.16 active(U72(tt, XS)) -> mark(XS) 40.53/11.16 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 40.53/11.16 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 40.53/11.16 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 40.53/11.16 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 40.53/11.16 active(head(cons(N, XS))) -> mark(U31(tt, N)) 40.53/11.16 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 40.53/11.16 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 40.53/11.16 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 40.53/11.16 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 40.53/11.16 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 40.53/11.16 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 40.53/11.16 active(take(N, XS)) -> mark(U81(tt, N, XS)) 40.53/11.16 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 40.53/11.16 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 40.53/11.16 active(snd(X)) -> snd(active(X)) 40.53/11.16 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 40.53/11.16 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 40.53/11.16 active(U21(X1, X2)) -> U21(active(X1), X2) 40.53/11.16 active(U22(X1, X2)) -> U22(active(X1), X2) 40.53/11.16 active(U31(X1, X2)) -> U31(active(X1), X2) 40.53/11.16 active(U32(X1, X2)) -> U32(active(X1), X2) 40.53/11.16 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 40.53/11.16 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 40.53/11.16 active(head(X)) -> head(active(X)) 40.53/11.16 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 40.53/11.16 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 40.53/11.16 active(U51(X1, X2)) -> U51(active(X1), X2) 40.53/11.16 active(U52(X1, X2)) -> U52(active(X1), X2) 40.53/11.16 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 40.53/11.16 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 40.53/11.16 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 40.53/11.16 active(U64(X1, X2)) -> U64(active(X1), X2) 40.53/11.16 active(pair(X1, X2)) -> pair(active(X1), X2) 40.53/11.16 active(pair(X1, X2)) -> pair(X1, active(X2)) 40.53/11.16 active(cons(X1, X2)) -> cons(active(X1), X2) 40.53/11.16 active(U71(X1, X2)) -> U71(active(X1), X2) 40.53/11.16 active(U72(X1, X2)) -> U72(active(X1), X2) 40.53/11.16 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 40.53/11.16 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 40.53/11.16 active(fst(X)) -> fst(active(X)) 40.53/11.16 active(natsFrom(X)) -> natsFrom(active(X)) 40.53/11.16 active(s(X)) -> s(active(X)) 40.53/11.16 active(sel(X1, X2)) -> sel(active(X1), X2) 40.53/11.16 active(sel(X1, X2)) -> sel(X1, active(X2)) 40.53/11.16 active(tail(X)) -> tail(active(X)) 40.53/11.16 active(take(X1, X2)) -> take(active(X1), X2) 40.53/11.16 active(take(X1, X2)) -> take(X1, active(X2)) 40.53/11.16 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 40.53/11.16 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 40.53/11.16 snd(mark(X)) -> mark(snd(X)) 40.53/11.16 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 40.53/11.16 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 40.53/11.16 U21(mark(X1), X2) -> mark(U21(X1, X2)) 40.53/11.16 U22(mark(X1), X2) -> mark(U22(X1, X2)) 40.53/11.16 U31(mark(X1), X2) -> mark(U31(X1, X2)) 40.53/11.16 U32(mark(X1), X2) -> mark(U32(X1, X2)) 40.53/11.16 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 40.53/11.16 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 40.53/11.16 head(mark(X)) -> mark(head(X)) 40.53/11.16 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 40.53/11.16 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 40.53/11.16 U51(mark(X1), X2) -> mark(U51(X1, X2)) 40.53/11.16 U52(mark(X1), X2) -> mark(U52(X1, X2)) 40.53/11.16 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 40.53/11.16 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 40.53/11.16 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 40.53/11.16 U64(mark(X1), X2) -> mark(U64(X1, X2)) 40.53/11.16 pair(mark(X1), X2) -> mark(pair(X1, X2)) 40.53/11.16 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 40.53/11.16 cons(mark(X1), X2) -> mark(cons(X1, X2)) 40.53/11.16 U71(mark(X1), X2) -> mark(U71(X1, X2)) 40.53/11.16 U72(mark(X1), X2) -> mark(U72(X1, X2)) 40.53/11.16 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 40.53/11.16 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 40.53/11.16 fst(mark(X)) -> mark(fst(X)) 40.53/11.16 natsFrom(mark(X)) -> mark(natsFrom(X)) 40.53/11.16 s(mark(X)) -> mark(s(X)) 40.53/11.16 sel(mark(X1), X2) -> mark(sel(X1, X2)) 40.53/11.16 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 40.53/11.16 tail(mark(X)) -> mark(tail(X)) 40.53/11.16 take(mark(X1), X2) -> mark(take(X1, X2)) 40.53/11.16 take(X1, mark(X2)) -> mark(take(X1, X2)) 40.53/11.16 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(tt) -> ok(tt) 40.53/11.16 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(snd(X)) -> snd(proper(X)) 40.53/11.16 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 40.53/11.16 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 40.53/11.16 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 40.53/11.16 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 40.53/11.16 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 40.53/11.16 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(head(X)) -> head(proper(X)) 40.53/11.16 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 40.53/11.16 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 40.53/11.16 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 40.53/11.16 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 40.53/11.16 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 40.53/11.16 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 40.53/11.16 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 40.53/11.16 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 40.53/11.16 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 40.53/11.16 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 40.53/11.16 proper(fst(X)) -> fst(proper(X)) 40.53/11.16 proper(natsFrom(X)) -> natsFrom(proper(X)) 40.53/11.16 proper(s(X)) -> s(proper(X)) 40.53/11.16 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 40.53/11.16 proper(0) -> ok(0) 40.53/11.16 proper(nil) -> ok(nil) 40.53/11.16 proper(tail(X)) -> tail(proper(X)) 40.53/11.16 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 40.53/11.16 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 40.53/11.16 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 40.53/11.16 snd(ok(X)) -> ok(snd(X)) 40.53/11.16 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 40.53/11.16 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 40.53/11.16 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 40.53/11.16 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 40.53/11.16 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 40.53/11.16 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 40.53/11.16 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 40.53/11.16 head(ok(X)) -> ok(head(X)) 40.53/11.16 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 40.53/11.16 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 40.53/11.16 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 40.53/11.16 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 40.53/11.16 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 40.53/11.16 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 40.53/11.16 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 40.53/11.16 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 40.53/11.16 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 40.53/11.16 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 40.53/11.16 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 40.53/11.16 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 40.53/11.16 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 40.53/11.16 fst(ok(X)) -> ok(fst(X)) 40.53/11.16 natsFrom(ok(X)) -> ok(natsFrom(X)) 40.53/11.16 s(ok(X)) -> ok(s(X)) 40.53/11.16 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 40.53/11.16 tail(ok(X)) -> ok(tail(X)) 40.53/11.16 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 40.53/11.16 top(mark(X)) -> top(proper(X)) 40.53/11.16 top(ok(X)) -> top(active(X)) 40.53/11.16 40.53/11.16 S is empty. 40.53/11.16 Rewrite Strategy: FULL 40.65/11.22 EOF