4.31/2.07 YES 4.67/2.09 proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml 4.67/2.09 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 4.67/2.09 4.67/2.09 4.67/2.09 Termination w.r.t. Q of the given QTRS could be proven: 4.67/2.09 4.67/2.09 (0) QTRS 4.67/2.09 (1) QTRSToCSRProof [SOUND, 0 ms] 4.67/2.09 (2) CSR 4.67/2.09 (3) CSRInnermostProof [EQUIVALENT, 0 ms] 4.67/2.09 (4) CSR 4.67/2.09 (5) CSDependencyPairsProof [EQUIVALENT, 7 ms] 4.67/2.09 (6) QCSDP 4.67/2.09 (7) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 4.67/2.09 (8) AND 4.67/2.09 (9) QCSDP 4.67/2.09 (10) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.67/2.09 (11) QCSDP 4.67/2.09 (12) PIsEmptyProof [EQUIVALENT, 0 ms] 4.67/2.09 (13) YES 4.67/2.09 (14) QCSDP 4.67/2.09 (15) QCSDPSubtermProof [EQUIVALENT, 0 ms] 4.67/2.09 (16) QCSDP 4.67/2.09 (17) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 4.67/2.09 (18) TRUE 4.67/2.09 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (0) 4.67/2.09 Obligation: 4.67/2.09 Q restricted rewrite system: 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 4.67/2.09 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 4.67/2.09 active(U21(tt, X)) -> mark(U22(tt, X)) 4.67/2.09 active(U22(tt, X)) -> mark(X) 4.67/2.09 active(U31(tt, N)) -> mark(U32(tt, N)) 4.67/2.09 active(U32(tt, N)) -> mark(N) 4.67/2.09 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 4.67/2.09 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 4.67/2.09 active(U51(tt, Y)) -> mark(U52(tt, Y)) 4.67/2.09 active(U52(tt, Y)) -> mark(Y) 4.67/2.09 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 4.67/2.09 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 4.67/2.09 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 4.67/2.09 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 4.67/2.09 active(U71(tt, XS)) -> mark(U72(tt, XS)) 4.67/2.09 active(U72(tt, XS)) -> mark(XS) 4.67/2.09 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 4.67/2.09 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 4.67/2.09 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 4.67/2.09 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 4.67/2.09 active(head(cons(N, XS))) -> mark(U31(tt, N)) 4.67/2.09 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 4.67/2.09 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 4.67/2.09 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 4.67/2.09 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 4.67/2.09 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 4.67/2.09 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 4.67/2.09 active(take(N, XS)) -> mark(U81(tt, N, XS)) 4.67/2.09 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 4.67/2.09 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 4.67/2.09 active(snd(X)) -> snd(active(X)) 4.67/2.09 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 4.67/2.09 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 4.67/2.09 active(U21(X1, X2)) -> U21(active(X1), X2) 4.67/2.09 active(U22(X1, X2)) -> U22(active(X1), X2) 4.67/2.09 active(U31(X1, X2)) -> U31(active(X1), X2) 4.67/2.09 active(U32(X1, X2)) -> U32(active(X1), X2) 4.67/2.09 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 4.67/2.09 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 4.67/2.09 active(head(X)) -> head(active(X)) 4.67/2.09 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 4.67/2.09 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 4.67/2.09 active(U51(X1, X2)) -> U51(active(X1), X2) 4.67/2.09 active(U52(X1, X2)) -> U52(active(X1), X2) 4.67/2.09 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 4.67/2.09 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 4.67/2.09 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 4.67/2.09 active(U64(X1, X2)) -> U64(active(X1), X2) 4.67/2.09 active(pair(X1, X2)) -> pair(active(X1), X2) 4.67/2.09 active(pair(X1, X2)) -> pair(X1, active(X2)) 4.67/2.09 active(cons(X1, X2)) -> cons(active(X1), X2) 4.67/2.09 active(U71(X1, X2)) -> U71(active(X1), X2) 4.67/2.09 active(U72(X1, X2)) -> U72(active(X1), X2) 4.67/2.09 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 4.67/2.09 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 4.67/2.09 active(fst(X)) -> fst(active(X)) 4.67/2.09 active(natsFrom(X)) -> natsFrom(active(X)) 4.67/2.09 active(s(X)) -> s(active(X)) 4.67/2.09 active(sel(X1, X2)) -> sel(active(X1), X2) 4.67/2.09 active(sel(X1, X2)) -> sel(X1, active(X2)) 4.67/2.09 active(tail(X)) -> tail(active(X)) 4.67/2.09 active(take(X1, X2)) -> take(active(X1), X2) 4.67/2.09 active(take(X1, X2)) -> take(X1, active(X2)) 4.67/2.09 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 4.67/2.09 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 4.67/2.09 snd(mark(X)) -> mark(snd(X)) 4.67/2.09 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 4.67/2.09 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 4.67/2.09 U21(mark(X1), X2) -> mark(U21(X1, X2)) 4.67/2.09 U22(mark(X1), X2) -> mark(U22(X1, X2)) 4.67/2.09 U31(mark(X1), X2) -> mark(U31(X1, X2)) 4.67/2.09 U32(mark(X1), X2) -> mark(U32(X1, X2)) 4.67/2.09 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 4.67/2.09 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 4.67/2.09 head(mark(X)) -> mark(head(X)) 4.67/2.09 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 4.67/2.09 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 4.67/2.09 U51(mark(X1), X2) -> mark(U51(X1, X2)) 4.67/2.09 U52(mark(X1), X2) -> mark(U52(X1, X2)) 4.67/2.09 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 4.67/2.09 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 4.67/2.09 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 4.67/2.09 U64(mark(X1), X2) -> mark(U64(X1, X2)) 4.67/2.09 pair(mark(X1), X2) -> mark(pair(X1, X2)) 4.67/2.09 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 4.67/2.09 cons(mark(X1), X2) -> mark(cons(X1, X2)) 4.67/2.09 U71(mark(X1), X2) -> mark(U71(X1, X2)) 4.67/2.09 U72(mark(X1), X2) -> mark(U72(X1, X2)) 4.67/2.09 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 4.67/2.09 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 4.67/2.09 fst(mark(X)) -> mark(fst(X)) 4.67/2.09 natsFrom(mark(X)) -> mark(natsFrom(X)) 4.67/2.09 s(mark(X)) -> mark(s(X)) 4.67/2.09 sel(mark(X1), X2) -> mark(sel(X1, X2)) 4.67/2.09 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 4.67/2.09 tail(mark(X)) -> mark(tail(X)) 4.67/2.09 take(mark(X1), X2) -> mark(take(X1, X2)) 4.67/2.09 take(X1, mark(X2)) -> mark(take(X1, X2)) 4.67/2.09 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(tt) -> ok(tt) 4.67/2.09 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(snd(X)) -> snd(proper(X)) 4.67/2.09 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 4.67/2.09 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 4.67/2.09 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 4.67/2.09 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 4.67/2.09 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 4.67/2.09 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(head(X)) -> head(proper(X)) 4.67/2.09 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 4.67/2.09 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 4.67/2.09 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 4.67/2.09 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 4.67/2.09 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 4.67/2.09 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 4.67/2.09 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 4.67/2.09 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 4.67/2.09 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 4.67/2.09 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 4.67/2.09 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 4.67/2.09 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(fst(X)) -> fst(proper(X)) 4.67/2.09 proper(natsFrom(X)) -> natsFrom(proper(X)) 4.67/2.09 proper(s(X)) -> s(proper(X)) 4.67/2.09 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 4.67/2.09 proper(0) -> ok(0) 4.67/2.09 proper(nil) -> ok(nil) 4.67/2.09 proper(tail(X)) -> tail(proper(X)) 4.67/2.09 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 4.67/2.09 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 4.67/2.09 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 4.67/2.09 snd(ok(X)) -> ok(snd(X)) 4.67/2.09 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 4.67/2.09 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 4.67/2.09 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 4.67/2.09 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 4.67/2.09 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 4.67/2.09 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 4.67/2.09 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 4.67/2.09 head(ok(X)) -> ok(head(X)) 4.67/2.09 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 4.67/2.09 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 4.67/2.09 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 4.67/2.09 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 4.67/2.09 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 4.67/2.09 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 4.67/2.09 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 4.67/2.09 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 4.67/2.09 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 4.67/2.09 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 4.67/2.09 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 4.67/2.09 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 4.67/2.09 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 4.67/2.09 fst(ok(X)) -> ok(fst(X)) 4.67/2.09 natsFrom(ok(X)) -> ok(natsFrom(X)) 4.67/2.09 s(ok(X)) -> ok(s(X)) 4.67/2.09 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 4.67/2.09 tail(ok(X)) -> ok(tail(X)) 4.67/2.09 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 4.67/2.09 top(mark(X)) -> top(proper(X)) 4.67/2.09 top(ok(X)) -> top(active(X)) 4.67/2.09 4.67/2.09 The set Q consists of the following terms: 4.67/2.09 4.67/2.09 active(afterNth(x0, x1)) 4.67/2.09 active(natsFrom(x0)) 4.67/2.09 active(sel(x0, x1)) 4.67/2.09 active(take(x0, x1)) 4.67/2.09 active(U11(x0, x1, x2)) 4.67/2.09 active(U12(x0, x1, x2)) 4.67/2.09 active(snd(x0)) 4.67/2.09 active(splitAt(x0, x1)) 4.67/2.09 active(U21(x0, x1)) 4.67/2.09 active(U22(x0, x1)) 4.67/2.09 active(U31(x0, x1)) 4.67/2.09 active(U32(x0, x1)) 4.67/2.09 active(U41(x0, x1, x2)) 4.67/2.09 active(U42(x0, x1, x2)) 4.67/2.09 active(head(x0)) 4.67/2.09 active(U51(x0, x1)) 4.67/2.09 active(U52(x0, x1)) 4.67/2.09 active(U61(x0, x1, x2, x3)) 4.67/2.09 active(U62(x0, x1, x2, x3)) 4.67/2.09 active(U63(x0, x1, x2, x3)) 4.67/2.09 active(U64(x0, x1)) 4.67/2.09 active(pair(x0, x1)) 4.67/2.09 active(cons(x0, x1)) 4.67/2.09 active(U71(x0, x1)) 4.67/2.09 active(U72(x0, x1)) 4.67/2.09 active(U81(x0, x1, x2)) 4.67/2.09 active(U82(x0, x1, x2)) 4.67/2.09 active(fst(x0)) 4.67/2.09 active(s(x0)) 4.67/2.09 active(tail(x0)) 4.67/2.09 U11(mark(x0), x1, x2) 4.67/2.09 U12(mark(x0), x1, x2) 4.67/2.09 snd(mark(x0)) 4.67/2.09 splitAt(mark(x0), x1) 4.67/2.09 splitAt(x0, mark(x1)) 4.67/2.09 U21(mark(x0), x1) 4.67/2.09 U22(mark(x0), x1) 4.67/2.09 U31(mark(x0), x1) 4.67/2.09 U32(mark(x0), x1) 4.67/2.09 U41(mark(x0), x1, x2) 4.67/2.09 U42(mark(x0), x1, x2) 4.67/2.09 head(mark(x0)) 4.67/2.09 afterNth(mark(x0), x1) 4.67/2.09 afterNth(x0, mark(x1)) 4.67/2.09 U51(mark(x0), x1) 4.67/2.09 U52(mark(x0), x1) 4.67/2.09 U61(mark(x0), x1, x2, x3) 4.67/2.09 U62(mark(x0), x1, x2, x3) 4.67/2.09 U63(mark(x0), x1, x2, x3) 4.67/2.09 U64(mark(x0), x1) 4.67/2.09 pair(mark(x0), x1) 4.67/2.09 pair(x0, mark(x1)) 4.67/2.09 cons(mark(x0), x1) 4.67/2.09 U71(mark(x0), x1) 4.67/2.09 U72(mark(x0), x1) 4.67/2.09 U81(mark(x0), x1, x2) 4.67/2.09 U82(mark(x0), x1, x2) 4.67/2.09 fst(mark(x0)) 4.67/2.09 natsFrom(mark(x0)) 4.67/2.09 s(mark(x0)) 4.67/2.09 sel(mark(x0), x1) 4.67/2.09 sel(x0, mark(x1)) 4.67/2.09 tail(mark(x0)) 4.67/2.09 take(mark(x0), x1) 4.67/2.09 take(x0, mark(x1)) 4.67/2.09 proper(U11(x0, x1, x2)) 4.67/2.09 proper(tt) 4.67/2.09 proper(U12(x0, x1, x2)) 4.67/2.09 proper(snd(x0)) 4.67/2.09 proper(splitAt(x0, x1)) 4.67/2.09 proper(U21(x0, x1)) 4.67/2.09 proper(U22(x0, x1)) 4.67/2.09 proper(U31(x0, x1)) 4.67/2.09 proper(U32(x0, x1)) 4.67/2.09 proper(U41(x0, x1, x2)) 4.67/2.09 proper(U42(x0, x1, x2)) 4.67/2.09 proper(head(x0)) 4.67/2.09 proper(afterNth(x0, x1)) 4.67/2.09 proper(U51(x0, x1)) 4.67/2.09 proper(U52(x0, x1)) 4.67/2.09 proper(U61(x0, x1, x2, x3)) 4.67/2.09 proper(U62(x0, x1, x2, x3)) 4.67/2.09 proper(U63(x0, x1, x2, x3)) 4.67/2.09 proper(U64(x0, x1)) 4.67/2.09 proper(pair(x0, x1)) 4.67/2.09 proper(cons(x0, x1)) 4.67/2.09 proper(U71(x0, x1)) 4.67/2.09 proper(U72(x0, x1)) 4.67/2.09 proper(U81(x0, x1, x2)) 4.67/2.09 proper(U82(x0, x1, x2)) 4.67/2.09 proper(fst(x0)) 4.67/2.09 proper(natsFrom(x0)) 4.67/2.09 proper(s(x0)) 4.67/2.09 proper(sel(x0, x1)) 4.67/2.09 proper(0) 4.67/2.09 proper(nil) 4.67/2.09 proper(tail(x0)) 4.67/2.09 proper(take(x0, x1)) 4.67/2.09 U11(ok(x0), ok(x1), ok(x2)) 4.67/2.09 U12(ok(x0), ok(x1), ok(x2)) 4.67/2.09 snd(ok(x0)) 4.67/2.09 splitAt(ok(x0), ok(x1)) 4.67/2.09 U21(ok(x0), ok(x1)) 4.67/2.09 U22(ok(x0), ok(x1)) 4.67/2.09 U31(ok(x0), ok(x1)) 4.67/2.09 U32(ok(x0), ok(x1)) 4.67/2.09 U41(ok(x0), ok(x1), ok(x2)) 4.67/2.09 U42(ok(x0), ok(x1), ok(x2)) 4.67/2.09 head(ok(x0)) 4.67/2.09 afterNth(ok(x0), ok(x1)) 4.67/2.09 U51(ok(x0), ok(x1)) 4.67/2.09 U52(ok(x0), ok(x1)) 4.67/2.09 U61(ok(x0), ok(x1), ok(x2), ok(x3)) 4.67/2.09 U62(ok(x0), ok(x1), ok(x2), ok(x3)) 4.67/2.09 U63(ok(x0), ok(x1), ok(x2), ok(x3)) 4.67/2.09 U64(ok(x0), ok(x1)) 4.67/2.09 pair(ok(x0), ok(x1)) 4.67/2.09 cons(ok(x0), ok(x1)) 4.67/2.09 U71(ok(x0), ok(x1)) 4.67/2.09 U72(ok(x0), ok(x1)) 4.67/2.09 U81(ok(x0), ok(x1), ok(x2)) 4.67/2.09 U82(ok(x0), ok(x1), ok(x2)) 4.67/2.09 fst(ok(x0)) 4.67/2.09 natsFrom(ok(x0)) 4.67/2.09 s(ok(x0)) 4.67/2.09 sel(ok(x0), ok(x1)) 4.67/2.09 tail(ok(x0)) 4.67/2.09 take(ok(x0), ok(x1)) 4.67/2.09 top(mark(x0)) 4.67/2.09 top(ok(x0)) 4.67/2.09 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (1) QTRSToCSRProof (SOUND) 4.67/2.09 The following Q TRS is given: Q restricted rewrite system: 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 active(U11(tt, N, XS)) -> mark(U12(tt, N, XS)) 4.67/2.09 active(U12(tt, N, XS)) -> mark(snd(splitAt(N, XS))) 4.67/2.09 active(U21(tt, X)) -> mark(U22(tt, X)) 4.67/2.09 active(U22(tt, X)) -> mark(X) 4.67/2.09 active(U31(tt, N)) -> mark(U32(tt, N)) 4.67/2.09 active(U32(tt, N)) -> mark(N) 4.67/2.09 active(U41(tt, N, XS)) -> mark(U42(tt, N, XS)) 4.67/2.09 active(U42(tt, N, XS)) -> mark(head(afterNth(N, XS))) 4.67/2.09 active(U51(tt, Y)) -> mark(U52(tt, Y)) 4.67/2.09 active(U52(tt, Y)) -> mark(Y) 4.67/2.09 active(U61(tt, N, X, XS)) -> mark(U62(tt, N, X, XS)) 4.67/2.09 active(U62(tt, N, X, XS)) -> mark(U63(tt, N, X, XS)) 4.67/2.09 active(U63(tt, N, X, XS)) -> mark(U64(splitAt(N, XS), X)) 4.67/2.09 active(U64(pair(YS, ZS), X)) -> mark(pair(cons(X, YS), ZS)) 4.67/2.09 active(U71(tt, XS)) -> mark(U72(tt, XS)) 4.67/2.09 active(U72(tt, XS)) -> mark(XS) 4.67/2.09 active(U81(tt, N, XS)) -> mark(U82(tt, N, XS)) 4.67/2.09 active(U82(tt, N, XS)) -> mark(fst(splitAt(N, XS))) 4.67/2.09 active(afterNth(N, XS)) -> mark(U11(tt, N, XS)) 4.67/2.09 active(fst(pair(X, Y))) -> mark(U21(tt, X)) 4.67/2.09 active(head(cons(N, XS))) -> mark(U31(tt, N)) 4.67/2.09 active(natsFrom(N)) -> mark(cons(N, natsFrom(s(N)))) 4.67/2.09 active(sel(N, XS)) -> mark(U41(tt, N, XS)) 4.67/2.09 active(snd(pair(X, Y))) -> mark(U51(tt, Y)) 4.67/2.09 active(splitAt(0, XS)) -> mark(pair(nil, XS)) 4.67/2.09 active(splitAt(s(N), cons(X, XS))) -> mark(U61(tt, N, X, XS)) 4.67/2.09 active(tail(cons(N, XS))) -> mark(U71(tt, XS)) 4.67/2.09 active(take(N, XS)) -> mark(U81(tt, N, XS)) 4.67/2.09 active(U11(X1, X2, X3)) -> U11(active(X1), X2, X3) 4.67/2.09 active(U12(X1, X2, X3)) -> U12(active(X1), X2, X3) 4.67/2.09 active(snd(X)) -> snd(active(X)) 4.67/2.09 active(splitAt(X1, X2)) -> splitAt(active(X1), X2) 4.67/2.09 active(splitAt(X1, X2)) -> splitAt(X1, active(X2)) 4.67/2.09 active(U21(X1, X2)) -> U21(active(X1), X2) 4.67/2.09 active(U22(X1, X2)) -> U22(active(X1), X2) 4.67/2.09 active(U31(X1, X2)) -> U31(active(X1), X2) 4.67/2.09 active(U32(X1, X2)) -> U32(active(X1), X2) 4.67/2.09 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 4.67/2.09 active(U42(X1, X2, X3)) -> U42(active(X1), X2, X3) 4.67/2.09 active(head(X)) -> head(active(X)) 4.67/2.09 active(afterNth(X1, X2)) -> afterNth(active(X1), X2) 4.67/2.09 active(afterNth(X1, X2)) -> afterNth(X1, active(X2)) 4.67/2.09 active(U51(X1, X2)) -> U51(active(X1), X2) 4.67/2.09 active(U52(X1, X2)) -> U52(active(X1), X2) 4.67/2.09 active(U61(X1, X2, X3, X4)) -> U61(active(X1), X2, X3, X4) 4.67/2.09 active(U62(X1, X2, X3, X4)) -> U62(active(X1), X2, X3, X4) 4.67/2.09 active(U63(X1, X2, X3, X4)) -> U63(active(X1), X2, X3, X4) 4.67/2.09 active(U64(X1, X2)) -> U64(active(X1), X2) 4.67/2.09 active(pair(X1, X2)) -> pair(active(X1), X2) 4.67/2.09 active(pair(X1, X2)) -> pair(X1, active(X2)) 4.67/2.09 active(cons(X1, X2)) -> cons(active(X1), X2) 4.67/2.09 active(U71(X1, X2)) -> U71(active(X1), X2) 4.67/2.09 active(U72(X1, X2)) -> U72(active(X1), X2) 4.67/2.09 active(U81(X1, X2, X3)) -> U81(active(X1), X2, X3) 4.67/2.09 active(U82(X1, X2, X3)) -> U82(active(X1), X2, X3) 4.67/2.09 active(fst(X)) -> fst(active(X)) 4.67/2.09 active(natsFrom(X)) -> natsFrom(active(X)) 4.67/2.09 active(s(X)) -> s(active(X)) 4.67/2.09 active(sel(X1, X2)) -> sel(active(X1), X2) 4.67/2.09 active(sel(X1, X2)) -> sel(X1, active(X2)) 4.67/2.09 active(tail(X)) -> tail(active(X)) 4.67/2.09 active(take(X1, X2)) -> take(active(X1), X2) 4.67/2.09 active(take(X1, X2)) -> take(X1, active(X2)) 4.67/2.09 U11(mark(X1), X2, X3) -> mark(U11(X1, X2, X3)) 4.67/2.09 U12(mark(X1), X2, X3) -> mark(U12(X1, X2, X3)) 4.67/2.09 snd(mark(X)) -> mark(snd(X)) 4.67/2.09 splitAt(mark(X1), X2) -> mark(splitAt(X1, X2)) 4.67/2.09 splitAt(X1, mark(X2)) -> mark(splitAt(X1, X2)) 4.67/2.09 U21(mark(X1), X2) -> mark(U21(X1, X2)) 4.67/2.09 U22(mark(X1), X2) -> mark(U22(X1, X2)) 4.67/2.09 U31(mark(X1), X2) -> mark(U31(X1, X2)) 4.67/2.09 U32(mark(X1), X2) -> mark(U32(X1, X2)) 4.67/2.09 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 4.67/2.09 U42(mark(X1), X2, X3) -> mark(U42(X1, X2, X3)) 4.67/2.09 head(mark(X)) -> mark(head(X)) 4.67/2.09 afterNth(mark(X1), X2) -> mark(afterNth(X1, X2)) 4.67/2.09 afterNth(X1, mark(X2)) -> mark(afterNth(X1, X2)) 4.67/2.09 U51(mark(X1), X2) -> mark(U51(X1, X2)) 4.67/2.09 U52(mark(X1), X2) -> mark(U52(X1, X2)) 4.67/2.09 U61(mark(X1), X2, X3, X4) -> mark(U61(X1, X2, X3, X4)) 4.67/2.09 U62(mark(X1), X2, X3, X4) -> mark(U62(X1, X2, X3, X4)) 4.67/2.09 U63(mark(X1), X2, X3, X4) -> mark(U63(X1, X2, X3, X4)) 4.67/2.09 U64(mark(X1), X2) -> mark(U64(X1, X2)) 4.67/2.09 pair(mark(X1), X2) -> mark(pair(X1, X2)) 4.67/2.09 pair(X1, mark(X2)) -> mark(pair(X1, X2)) 4.67/2.09 cons(mark(X1), X2) -> mark(cons(X1, X2)) 4.67/2.09 U71(mark(X1), X2) -> mark(U71(X1, X2)) 4.67/2.09 U72(mark(X1), X2) -> mark(U72(X1, X2)) 4.67/2.09 U81(mark(X1), X2, X3) -> mark(U81(X1, X2, X3)) 4.67/2.09 U82(mark(X1), X2, X3) -> mark(U82(X1, X2, X3)) 4.67/2.09 fst(mark(X)) -> mark(fst(X)) 4.67/2.09 natsFrom(mark(X)) -> mark(natsFrom(X)) 4.67/2.09 s(mark(X)) -> mark(s(X)) 4.67/2.09 sel(mark(X1), X2) -> mark(sel(X1, X2)) 4.67/2.09 sel(X1, mark(X2)) -> mark(sel(X1, X2)) 4.67/2.09 tail(mark(X)) -> mark(tail(X)) 4.67/2.09 take(mark(X1), X2) -> mark(take(X1, X2)) 4.67/2.09 take(X1, mark(X2)) -> mark(take(X1, X2)) 4.67/2.09 proper(U11(X1, X2, X3)) -> U11(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(tt) -> ok(tt) 4.67/2.09 proper(U12(X1, X2, X3)) -> U12(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(snd(X)) -> snd(proper(X)) 4.67/2.09 proper(splitAt(X1, X2)) -> splitAt(proper(X1), proper(X2)) 4.67/2.09 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 4.67/2.09 proper(U22(X1, X2)) -> U22(proper(X1), proper(X2)) 4.67/2.09 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 4.67/2.09 proper(U32(X1, X2)) -> U32(proper(X1), proper(X2)) 4.67/2.09 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(U42(X1, X2, X3)) -> U42(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(head(X)) -> head(proper(X)) 4.67/2.09 proper(afterNth(X1, X2)) -> afterNth(proper(X1), proper(X2)) 4.67/2.09 proper(U51(X1, X2)) -> U51(proper(X1), proper(X2)) 4.67/2.09 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 4.67/2.09 proper(U61(X1, X2, X3, X4)) -> U61(proper(X1), proper(X2), proper(X3), proper(X4)) 4.67/2.09 proper(U62(X1, X2, X3, X4)) -> U62(proper(X1), proper(X2), proper(X3), proper(X4)) 4.67/2.09 proper(U63(X1, X2, X3, X4)) -> U63(proper(X1), proper(X2), proper(X3), proper(X4)) 4.67/2.09 proper(U64(X1, X2)) -> U64(proper(X1), proper(X2)) 4.67/2.09 proper(pair(X1, X2)) -> pair(proper(X1), proper(X2)) 4.67/2.09 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 4.67/2.09 proper(U71(X1, X2)) -> U71(proper(X1), proper(X2)) 4.67/2.09 proper(U72(X1, X2)) -> U72(proper(X1), proper(X2)) 4.67/2.09 proper(U81(X1, X2, X3)) -> U81(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(U82(X1, X2, X3)) -> U82(proper(X1), proper(X2), proper(X3)) 4.67/2.09 proper(fst(X)) -> fst(proper(X)) 4.67/2.09 proper(natsFrom(X)) -> natsFrom(proper(X)) 4.67/2.09 proper(s(X)) -> s(proper(X)) 4.67/2.09 proper(sel(X1, X2)) -> sel(proper(X1), proper(X2)) 4.67/2.09 proper(0) -> ok(0) 4.67/2.09 proper(nil) -> ok(nil) 4.67/2.09 proper(tail(X)) -> tail(proper(X)) 4.67/2.09 proper(take(X1, X2)) -> take(proper(X1), proper(X2)) 4.67/2.09 U11(ok(X1), ok(X2), ok(X3)) -> ok(U11(X1, X2, X3)) 4.67/2.09 U12(ok(X1), ok(X2), ok(X3)) -> ok(U12(X1, X2, X3)) 4.67/2.09 snd(ok(X)) -> ok(snd(X)) 4.67/2.09 splitAt(ok(X1), ok(X2)) -> ok(splitAt(X1, X2)) 4.67/2.09 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 4.67/2.09 U22(ok(X1), ok(X2)) -> ok(U22(X1, X2)) 4.67/2.09 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 4.67/2.09 U32(ok(X1), ok(X2)) -> ok(U32(X1, X2)) 4.67/2.09 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 4.67/2.09 U42(ok(X1), ok(X2), ok(X3)) -> ok(U42(X1, X2, X3)) 4.67/2.09 head(ok(X)) -> ok(head(X)) 4.67/2.09 afterNth(ok(X1), ok(X2)) -> ok(afterNth(X1, X2)) 4.67/2.09 U51(ok(X1), ok(X2)) -> ok(U51(X1, X2)) 4.67/2.09 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 4.67/2.09 U61(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U61(X1, X2, X3, X4)) 4.67/2.09 U62(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U62(X1, X2, X3, X4)) 4.67/2.09 U63(ok(X1), ok(X2), ok(X3), ok(X4)) -> ok(U63(X1, X2, X3, X4)) 4.67/2.09 U64(ok(X1), ok(X2)) -> ok(U64(X1, X2)) 4.67/2.09 pair(ok(X1), ok(X2)) -> ok(pair(X1, X2)) 4.67/2.09 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 4.67/2.09 U71(ok(X1), ok(X2)) -> ok(U71(X1, X2)) 4.67/2.09 U72(ok(X1), ok(X2)) -> ok(U72(X1, X2)) 4.67/2.09 U81(ok(X1), ok(X2), ok(X3)) -> ok(U81(X1, X2, X3)) 4.67/2.09 U82(ok(X1), ok(X2), ok(X3)) -> ok(U82(X1, X2, X3)) 4.67/2.09 fst(ok(X)) -> ok(fst(X)) 4.67/2.09 natsFrom(ok(X)) -> ok(natsFrom(X)) 4.67/2.09 s(ok(X)) -> ok(s(X)) 4.67/2.09 sel(ok(X1), ok(X2)) -> ok(sel(X1, X2)) 4.67/2.09 tail(ok(X)) -> ok(tail(X)) 4.67/2.09 take(ok(X1), ok(X2)) -> ok(take(X1, X2)) 4.67/2.09 top(mark(X)) -> top(proper(X)) 4.67/2.09 top(ok(X)) -> top(active(X)) 4.67/2.09 4.67/2.09 The set Q consists of the following terms: 4.67/2.09 4.67/2.09 active(afterNth(x0, x1)) 4.67/2.09 active(natsFrom(x0)) 4.67/2.09 active(sel(x0, x1)) 4.67/2.09 active(take(x0, x1)) 4.67/2.09 active(U11(x0, x1, x2)) 4.67/2.09 active(U12(x0, x1, x2)) 4.67/2.09 active(snd(x0)) 4.67/2.09 active(splitAt(x0, x1)) 4.67/2.09 active(U21(x0, x1)) 4.67/2.09 active(U22(x0, x1)) 4.67/2.09 active(U31(x0, x1)) 4.67/2.09 active(U32(x0, x1)) 4.67/2.09 active(U41(x0, x1, x2)) 4.67/2.09 active(U42(x0, x1, x2)) 4.67/2.09 active(head(x0)) 4.67/2.09 active(U51(x0, x1)) 4.67/2.09 active(U52(x0, x1)) 4.67/2.09 active(U61(x0, x1, x2, x3)) 4.67/2.09 active(U62(x0, x1, x2, x3)) 4.67/2.09 active(U63(x0, x1, x2, x3)) 4.67/2.09 active(U64(x0, x1)) 4.67/2.09 active(pair(x0, x1)) 4.67/2.09 active(cons(x0, x1)) 4.67/2.09 active(U71(x0, x1)) 4.67/2.09 active(U72(x0, x1)) 4.67/2.09 active(U81(x0, x1, x2)) 4.67/2.09 active(U82(x0, x1, x2)) 4.67/2.09 active(fst(x0)) 4.67/2.09 active(s(x0)) 4.67/2.09 active(tail(x0)) 4.67/2.09 U11(mark(x0), x1, x2) 4.67/2.09 U12(mark(x0), x1, x2) 4.67/2.09 snd(mark(x0)) 4.67/2.09 splitAt(mark(x0), x1) 4.67/2.09 splitAt(x0, mark(x1)) 4.67/2.09 U21(mark(x0), x1) 4.67/2.09 U22(mark(x0), x1) 4.67/2.09 U31(mark(x0), x1) 4.67/2.09 U32(mark(x0), x1) 4.67/2.09 U41(mark(x0), x1, x2) 4.67/2.09 U42(mark(x0), x1, x2) 4.67/2.09 head(mark(x0)) 4.67/2.09 afterNth(mark(x0), x1) 4.67/2.09 afterNth(x0, mark(x1)) 4.67/2.09 U51(mark(x0), x1) 4.67/2.09 U52(mark(x0), x1) 4.67/2.09 U61(mark(x0), x1, x2, x3) 4.67/2.09 U62(mark(x0), x1, x2, x3) 4.67/2.09 U63(mark(x0), x1, x2, x3) 4.67/2.09 U64(mark(x0), x1) 4.67/2.09 pair(mark(x0), x1) 4.67/2.09 pair(x0, mark(x1)) 4.67/2.09 cons(mark(x0), x1) 4.67/2.09 U71(mark(x0), x1) 4.67/2.09 U72(mark(x0), x1) 4.67/2.09 U81(mark(x0), x1, x2) 4.67/2.09 U82(mark(x0), x1, x2) 4.67/2.09 fst(mark(x0)) 4.67/2.09 natsFrom(mark(x0)) 4.67/2.09 s(mark(x0)) 4.67/2.09 sel(mark(x0), x1) 4.67/2.09 sel(x0, mark(x1)) 4.67/2.09 tail(mark(x0)) 4.67/2.09 take(mark(x0), x1) 4.67/2.09 take(x0, mark(x1)) 4.67/2.09 proper(U11(x0, x1, x2)) 4.67/2.09 proper(tt) 4.67/2.09 proper(U12(x0, x1, x2)) 4.67/2.09 proper(snd(x0)) 4.67/2.09 proper(splitAt(x0, x1)) 4.67/2.09 proper(U21(x0, x1)) 4.67/2.09 proper(U22(x0, x1)) 4.67/2.09 proper(U31(x0, x1)) 4.67/2.09 proper(U32(x0, x1)) 4.67/2.09 proper(U41(x0, x1, x2)) 4.67/2.09 proper(U42(x0, x1, x2)) 4.67/2.09 proper(head(x0)) 4.67/2.09 proper(afterNth(x0, x1)) 4.67/2.09 proper(U51(x0, x1)) 4.67/2.09 proper(U52(x0, x1)) 4.67/2.09 proper(U61(x0, x1, x2, x3)) 4.67/2.09 proper(U62(x0, x1, x2, x3)) 4.67/2.09 proper(U63(x0, x1, x2, x3)) 4.67/2.09 proper(U64(x0, x1)) 4.67/2.09 proper(pair(x0, x1)) 4.67/2.09 proper(cons(x0, x1)) 4.67/2.09 proper(U71(x0, x1)) 4.67/2.09 proper(U72(x0, x1)) 4.67/2.09 proper(U81(x0, x1, x2)) 4.67/2.09 proper(U82(x0, x1, x2)) 4.67/2.09 proper(fst(x0)) 4.67/2.09 proper(natsFrom(x0)) 4.67/2.09 proper(s(x0)) 4.67/2.09 proper(sel(x0, x1)) 4.67/2.09 proper(0) 4.67/2.09 proper(nil) 4.67/2.09 proper(tail(x0)) 4.67/2.09 proper(take(x0, x1)) 4.67/2.09 U11(ok(x0), ok(x1), ok(x2)) 4.67/2.09 U12(ok(x0), ok(x1), ok(x2)) 4.67/2.09 snd(ok(x0)) 4.67/2.09 splitAt(ok(x0), ok(x1)) 4.67/2.09 U21(ok(x0), ok(x1)) 4.67/2.09 U22(ok(x0), ok(x1)) 4.67/2.09 U31(ok(x0), ok(x1)) 4.67/2.09 U32(ok(x0), ok(x1)) 4.67/2.09 U41(ok(x0), ok(x1), ok(x2)) 4.67/2.09 U42(ok(x0), ok(x1), ok(x2)) 4.67/2.09 head(ok(x0)) 4.67/2.09 afterNth(ok(x0), ok(x1)) 4.67/2.09 U51(ok(x0), ok(x1)) 4.67/2.09 U52(ok(x0), ok(x1)) 4.67/2.09 U61(ok(x0), ok(x1), ok(x2), ok(x3)) 4.67/2.09 U62(ok(x0), ok(x1), ok(x2), ok(x3)) 4.67/2.09 U63(ok(x0), ok(x1), ok(x2), ok(x3)) 4.67/2.09 U64(ok(x0), ok(x1)) 4.67/2.09 pair(ok(x0), ok(x1)) 4.67/2.09 cons(ok(x0), ok(x1)) 4.67/2.09 U71(ok(x0), ok(x1)) 4.67/2.09 U72(ok(x0), ok(x1)) 4.67/2.09 U81(ok(x0), ok(x1), ok(x2)) 4.67/2.09 U82(ok(x0), ok(x1), ok(x2)) 4.67/2.09 fst(ok(x0)) 4.67/2.09 natsFrom(ok(x0)) 4.67/2.09 s(ok(x0)) 4.67/2.09 sel(ok(x0), ok(x1)) 4.67/2.09 tail(ok(x0)) 4.67/2.09 take(ok(x0), ok(x1)) 4.67/2.09 top(mark(x0)) 4.67/2.09 top(ok(x0)) 4.67/2.09 4.67/2.09 Special symbols used for the transformation (see [GM04]): 4.67/2.09 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 4.67/2.09 The replacement map contains the following entries: 4.67/2.09 4.67/2.09 U11: {1} 4.67/2.09 tt: empty set 4.67/2.09 U12: {1} 4.67/2.09 snd: {1} 4.67/2.09 splitAt: {1, 2} 4.67/2.09 U21: {1} 4.67/2.09 U22: {1} 4.67/2.09 U31: {1} 4.67/2.09 U32: {1} 4.67/2.09 U41: {1} 4.67/2.09 U42: {1} 4.67/2.09 head: {1} 4.67/2.09 afterNth: {1, 2} 4.67/2.09 U51: {1} 4.67/2.09 U52: {1} 4.67/2.09 U61: {1} 4.67/2.09 U62: {1} 4.67/2.09 U63: {1} 4.67/2.09 U64: {1} 4.67/2.09 pair: {1, 2} 4.67/2.09 cons: {1} 4.67/2.09 U71: {1} 4.67/2.09 U72: {1} 4.67/2.09 U81: {1} 4.67/2.09 U82: {1} 4.67/2.09 fst: {1} 4.67/2.09 natsFrom: {1} 4.67/2.09 s: {1} 4.67/2.09 sel: {1, 2} 4.67/2.09 0: empty set 4.67/2.09 nil: empty set 4.67/2.09 tail: {1} 4.67/2.09 take: {1, 2} 4.67/2.09 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (2) 4.67/2.09 Obligation: 4.67/2.09 Context-sensitive rewrite system: 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.67/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.67/2.09 U21(tt, X) -> U22(tt, X) 4.67/2.09 U22(tt, X) -> X 4.67/2.09 U31(tt, N) -> U32(tt, N) 4.67/2.09 U32(tt, N) -> N 4.67/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.67/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.67/2.09 U51(tt, Y) -> U52(tt, Y) 4.67/2.09 U52(tt, Y) -> Y 4.67/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.67/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.67/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.67/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.67/2.09 U71(tt, XS) -> U72(tt, XS) 4.67/2.09 U72(tt, XS) -> XS 4.67/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.67/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.67/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.67/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.67/2.09 head(cons(N, XS)) -> U31(tt, N) 4.67/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.67/2.09 sel(N, XS) -> U41(tt, N, XS) 4.67/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.67/2.09 splitAt(0, XS) -> pair(nil, XS) 4.67/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.67/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.67/2.09 take(N, XS) -> U81(tt, N, XS) 4.67/2.09 4.67/2.09 The replacement map contains the following entries: 4.67/2.09 4.67/2.09 U11: {1} 4.67/2.09 tt: empty set 4.67/2.09 U12: {1} 4.67/2.09 snd: {1} 4.67/2.09 splitAt: {1, 2} 4.67/2.09 U21: {1} 4.67/2.09 U22: {1} 4.67/2.09 U31: {1} 4.67/2.09 U32: {1} 4.67/2.09 U41: {1} 4.67/2.09 U42: {1} 4.67/2.09 head: {1} 4.67/2.09 afterNth: {1, 2} 4.67/2.09 U51: {1} 4.67/2.09 U52: {1} 4.67/2.09 U61: {1} 4.67/2.09 U62: {1} 4.67/2.09 U63: {1} 4.67/2.09 U64: {1} 4.67/2.09 pair: {1, 2} 4.67/2.09 cons: {1} 4.67/2.09 U71: {1} 4.67/2.09 U72: {1} 4.67/2.09 U81: {1} 4.67/2.09 U82: {1} 4.67/2.09 fst: {1} 4.67/2.09 natsFrom: {1} 4.67/2.09 s: {1} 4.67/2.09 sel: {1, 2} 4.67/2.09 0: empty set 4.67/2.09 nil: empty set 4.67/2.09 tail: {1} 4.67/2.09 take: {1, 2} 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (3) CSRInnermostProof (EQUIVALENT) 4.67/2.09 The CSR is orthogonal. By [CS_Inn] we can switch to innermost. 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (4) 4.67/2.09 Obligation: 4.67/2.09 Context-sensitive rewrite system: 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.67/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.67/2.09 U21(tt, X) -> U22(tt, X) 4.67/2.09 U22(tt, X) -> X 4.67/2.09 U31(tt, N) -> U32(tt, N) 4.67/2.09 U32(tt, N) -> N 4.67/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.67/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.67/2.09 U51(tt, Y) -> U52(tt, Y) 4.67/2.09 U52(tt, Y) -> Y 4.67/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.67/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.67/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.67/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.67/2.09 U71(tt, XS) -> U72(tt, XS) 4.67/2.09 U72(tt, XS) -> XS 4.67/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.67/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.67/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.67/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.67/2.09 head(cons(N, XS)) -> U31(tt, N) 4.67/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.67/2.09 sel(N, XS) -> U41(tt, N, XS) 4.67/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.67/2.09 splitAt(0, XS) -> pair(nil, XS) 4.67/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.67/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.67/2.09 take(N, XS) -> U81(tt, N, XS) 4.67/2.09 4.67/2.09 The replacement map contains the following entries: 4.67/2.09 4.67/2.09 U11: {1} 4.67/2.09 tt: empty set 4.67/2.09 U12: {1} 4.67/2.09 snd: {1} 4.67/2.09 splitAt: {1, 2} 4.67/2.09 U21: {1} 4.67/2.09 U22: {1} 4.67/2.09 U31: {1} 4.67/2.09 U32: {1} 4.67/2.09 U41: {1} 4.67/2.09 U42: {1} 4.67/2.09 head: {1} 4.67/2.09 afterNth: {1, 2} 4.67/2.09 U51: {1} 4.67/2.09 U52: {1} 4.67/2.09 U61: {1} 4.67/2.09 U62: {1} 4.67/2.09 U63: {1} 4.67/2.09 U64: {1} 4.67/2.09 pair: {1, 2} 4.67/2.09 cons: {1} 4.67/2.09 U71: {1} 4.67/2.09 U72: {1} 4.67/2.09 U81: {1} 4.67/2.09 U82: {1} 4.67/2.09 fst: {1} 4.67/2.09 natsFrom: {1} 4.67/2.09 s: {1} 4.67/2.09 sel: {1, 2} 4.67/2.09 0: empty set 4.67/2.09 nil: empty set 4.67/2.09 tail: {1} 4.67/2.09 take: {1, 2} 4.67/2.09 4.67/2.09 4.67/2.09 Innermost Strategy. 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (5) CSDependencyPairsProof (EQUIVALENT) 4.67/2.09 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (6) 4.67/2.09 Obligation: 4.67/2.09 Q-restricted context-sensitive dependency pair problem: 4.67/2.09 The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, SND_1, SPLITAT_2, HEAD_1, AFTERNTH_2, FST_1, SEL_2, TAIL_1, TAKE_2, NATSFROM_1} are replacing on all positions. 4.67/2.09 For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3, U12'_3, U11'_3, U22'_2, U21'_2, U32'_2, U31'_2, U42'_3, U41'_3, U52'_2, U51'_2, U62'_4, U61'_4, U63'_4, U64'_2, U72'_2, U71'_2, U82'_3, U81'_3} we have mu(f) = {1}. 4.67/2.09 The symbols in {U_1} are not replacing on any position. 4.67/2.09 4.67/2.09 The ordinary context-sensitive dependency pairs DP_o are: 4.67/2.09 U11'(tt, N, XS) -> U12'(tt, N, XS) 4.67/2.09 U12'(tt, N, XS) -> SND(splitAt(N, XS)) 4.67/2.09 U12'(tt, N, XS) -> SPLITAT(N, XS) 4.67/2.09 U21'(tt, X) -> U22'(tt, X) 4.67/2.09 U31'(tt, N) -> U32'(tt, N) 4.67/2.09 U41'(tt, N, XS) -> U42'(tt, N, XS) 4.67/2.09 U42'(tt, N, XS) -> HEAD(afterNth(N, XS)) 4.67/2.09 U42'(tt, N, XS) -> AFTERNTH(N, XS) 4.67/2.09 U51'(tt, Y) -> U52'(tt, Y) 4.67/2.09 U61'(tt, N, X, XS) -> U62'(tt, N, X, XS) 4.67/2.09 U62'(tt, N, X, XS) -> U63'(tt, N, X, XS) 4.67/2.09 U63'(tt, N, X, XS) -> U64'(splitAt(N, XS), X) 4.67/2.09 U63'(tt, N, X, XS) -> SPLITAT(N, XS) 4.67/2.09 U71'(tt, XS) -> U72'(tt, XS) 4.67/2.09 U81'(tt, N, XS) -> U82'(tt, N, XS) 4.67/2.09 U82'(tt, N, XS) -> FST(splitAt(N, XS)) 4.67/2.09 U82'(tt, N, XS) -> SPLITAT(N, XS) 4.67/2.09 AFTERNTH(N, XS) -> U11'(tt, N, XS) 4.67/2.09 FST(pair(X, Y)) -> U21'(tt, X) 4.67/2.09 HEAD(cons(N, XS)) -> U31'(tt, N) 4.67/2.09 SEL(N, XS) -> U41'(tt, N, XS) 4.67/2.09 SND(pair(X, Y)) -> U51'(tt, Y) 4.67/2.09 SPLITAT(s(N), cons(X, XS)) -> U61'(tt, N, X, XS) 4.67/2.09 TAIL(cons(N, XS)) -> U71'(tt, XS) 4.67/2.09 TAKE(N, XS) -> U81'(tt, N, XS) 4.67/2.09 4.67/2.09 The collapsing dependency pairs are DP_c: 4.67/2.09 U12'(tt, N, XS) -> N 4.67/2.09 U12'(tt, N, XS) -> XS 4.67/2.09 U22'(tt, X) -> X 4.67/2.09 U32'(tt, N) -> N 4.67/2.09 U42'(tt, N, XS) -> N 4.67/2.09 U42'(tt, N, XS) -> XS 4.67/2.09 U52'(tt, Y) -> Y 4.67/2.09 U63'(tt, N, X, XS) -> N 4.67/2.09 U63'(tt, N, X, XS) -> XS 4.67/2.09 U64'(pair(YS, ZS), X) -> X 4.67/2.09 U72'(tt, XS) -> XS 4.67/2.09 U82'(tt, N, XS) -> N 4.67/2.09 U82'(tt, N, XS) -> XS 4.67/2.09 4.67/2.09 4.67/2.09 The hidden terms of R are: 4.67/2.09 4.67/2.09 natsFrom(s(x0)) 4.67/2.09 4.67/2.09 Every hiding context is built from: 4.67/2.09 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@6aaee89d 4.67/2.09 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@6d6d1865 4.67/2.09 4.67/2.09 Hence, the new unhiding pairs DP_u are : 4.67/2.09 U12'(tt, N, XS) -> U(N) 4.67/2.09 U12'(tt, N, XS) -> U(XS) 4.67/2.09 U22'(tt, X) -> U(X) 4.67/2.09 U32'(tt, N) -> U(N) 4.67/2.09 U42'(tt, N, XS) -> U(N) 4.67/2.09 U42'(tt, N, XS) -> U(XS) 4.67/2.09 U52'(tt, Y) -> U(Y) 4.67/2.09 U63'(tt, N, X, XS) -> U(N) 4.67/2.09 U63'(tt, N, X, XS) -> U(XS) 4.67/2.09 U64'(pair(YS, ZS), X) -> U(X) 4.67/2.09 U72'(tt, XS) -> U(XS) 4.67/2.09 U82'(tt, N, XS) -> U(N) 4.67/2.09 U82'(tt, N, XS) -> U(XS) 4.67/2.09 U(s(x_0)) -> U(x_0) 4.67/2.09 U(natsFrom(x_0)) -> U(x_0) 4.67/2.09 U(natsFrom(s(x0))) -> NATSFROM(s(x0)) 4.67/2.09 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.67/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.67/2.09 U21(tt, X) -> U22(tt, X) 4.67/2.09 U22(tt, X) -> X 4.67/2.09 U31(tt, N) -> U32(tt, N) 4.67/2.09 U32(tt, N) -> N 4.67/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.67/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.67/2.09 U51(tt, Y) -> U52(tt, Y) 4.67/2.09 U52(tt, Y) -> Y 4.67/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.67/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.67/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.67/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.67/2.09 U71(tt, XS) -> U72(tt, XS) 4.67/2.09 U72(tt, XS) -> XS 4.67/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.67/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.67/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.67/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.67/2.09 head(cons(N, XS)) -> U31(tt, N) 4.67/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.67/2.09 sel(N, XS) -> U41(tt, N, XS) 4.67/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.67/2.09 splitAt(0, XS) -> pair(nil, XS) 4.67/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.67/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.67/2.09 take(N, XS) -> U81(tt, N, XS) 4.67/2.09 4.67/2.09 The set Q consists of the following terms: 4.67/2.09 4.67/2.09 U11(tt, x0, x1) 4.67/2.09 U12(tt, x0, x1) 4.67/2.09 U21(tt, x0) 4.67/2.09 U22(tt, x0) 4.67/2.09 U31(tt, x0) 4.67/2.09 U32(tt, x0) 4.67/2.09 U41(tt, x0, x1) 4.67/2.09 U42(tt, x0, x1) 4.67/2.09 U51(tt, x0) 4.67/2.09 U52(tt, x0) 4.67/2.09 U61(tt, x0, x1, x2) 4.67/2.09 U62(tt, x0, x1, x2) 4.67/2.09 U63(tt, x0, x1, x2) 4.67/2.09 U64(pair(x0, x1), x2) 4.67/2.09 U71(tt, x0) 4.67/2.09 U72(tt, x0) 4.67/2.09 U81(tt, x0, x1) 4.67/2.09 U82(tt, x0, x1) 4.67/2.09 afterNth(x0, x1) 4.67/2.09 fst(pair(x0, x1)) 4.67/2.09 head(cons(x0, x1)) 4.67/2.09 natsFrom(x0) 4.67/2.09 sel(x0, x1) 4.67/2.09 snd(pair(x0, x1)) 4.67/2.09 splitAt(0, x0) 4.67/2.09 splitAt(s(x0), cons(x1, x2)) 4.67/2.09 tail(cons(x0, x1)) 4.67/2.09 take(x0, x1) 4.67/2.09 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (7) QCSDependencyGraphProof (EQUIVALENT) 4.67/2.09 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs with 35 less nodes. 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (8) 4.67/2.09 Complex Obligation (AND) 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (9) 4.67/2.09 Obligation: 4.67/2.09 Q-restricted context-sensitive dependency pair problem: 4.67/2.09 The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2} are replacing on all positions. 4.67/2.09 For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3} we have mu(f) = {1}. 4.67/2.09 The symbols in {U_1} are not replacing on any position. 4.67/2.09 4.67/2.09 The TRS P consists of the following rules: 4.67/2.09 4.67/2.09 U(s(x_0)) -> U(x_0) 4.67/2.09 U(natsFrom(x_0)) -> U(x_0) 4.67/2.09 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.67/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.67/2.09 U21(tt, X) -> U22(tt, X) 4.67/2.09 U22(tt, X) -> X 4.67/2.09 U31(tt, N) -> U32(tt, N) 4.67/2.09 U32(tt, N) -> N 4.67/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.67/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.67/2.09 U51(tt, Y) -> U52(tt, Y) 4.67/2.09 U52(tt, Y) -> Y 4.67/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.67/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.67/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.67/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.67/2.09 U71(tt, XS) -> U72(tt, XS) 4.67/2.09 U72(tt, XS) -> XS 4.67/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.67/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.67/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.67/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.67/2.09 head(cons(N, XS)) -> U31(tt, N) 4.67/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.67/2.09 sel(N, XS) -> U41(tt, N, XS) 4.67/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.67/2.09 splitAt(0, XS) -> pair(nil, XS) 4.67/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.67/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.67/2.09 take(N, XS) -> U81(tt, N, XS) 4.67/2.09 4.67/2.09 The set Q consists of the following terms: 4.67/2.09 4.67/2.09 U11(tt, x0, x1) 4.67/2.09 U12(tt, x0, x1) 4.67/2.09 U21(tt, x0) 4.67/2.09 U22(tt, x0) 4.67/2.09 U31(tt, x0) 4.67/2.09 U32(tt, x0) 4.67/2.09 U41(tt, x0, x1) 4.67/2.09 U42(tt, x0, x1) 4.67/2.09 U51(tt, x0) 4.67/2.09 U52(tt, x0) 4.67/2.09 U61(tt, x0, x1, x2) 4.67/2.09 U62(tt, x0, x1, x2) 4.67/2.09 U63(tt, x0, x1, x2) 4.67/2.09 U64(pair(x0, x1), x2) 4.67/2.09 U71(tt, x0) 4.67/2.09 U72(tt, x0) 4.67/2.09 U81(tt, x0, x1) 4.67/2.09 U82(tt, x0, x1) 4.67/2.09 afterNth(x0, x1) 4.67/2.09 fst(pair(x0, x1)) 4.67/2.09 head(cons(x0, x1)) 4.67/2.09 natsFrom(x0) 4.67/2.09 sel(x0, x1) 4.67/2.09 snd(pair(x0, x1)) 4.67/2.09 splitAt(0, x0) 4.67/2.09 splitAt(s(x0), cons(x1, x2)) 4.67/2.09 tail(cons(x0, x1)) 4.67/2.09 take(x0, x1) 4.67/2.09 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (10) QCSDPSubtermProof (EQUIVALENT) 4.67/2.09 We use the subterm processor [DA_EMMES]. 4.67/2.09 4.67/2.09 4.67/2.09 The following pairs can be oriented strictly and are deleted. 4.67/2.09 4.67/2.09 U(s(x_0)) -> U(x_0) 4.67/2.09 U(natsFrom(x_0)) -> U(x_0) 4.67/2.09 The remaining pairs can at least be oriented weakly. 4.67/2.09 none 4.67/2.09 Used ordering: Combined order from the following AFS and order. 4.67/2.09 U(x1) = x1 4.67/2.09 4.67/2.09 4.67/2.09 Subterm Order 4.67/2.09 4.67/2.09 ---------------------------------------- 4.67/2.09 4.67/2.09 (11) 4.67/2.09 Obligation: 4.67/2.09 Q-restricted context-sensitive dependency pair problem: 4.67/2.09 The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2} are replacing on all positions. 4.67/2.09 For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3} we have mu(f) = {1}. 4.67/2.09 4.67/2.09 The TRS P consists of the following rules: 4.67/2.09 none 4.67/2.09 4.67/2.09 The TRS R consists of the following rules: 4.67/2.09 4.67/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.67/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.67/2.09 U21(tt, X) -> U22(tt, X) 4.67/2.09 U22(tt, X) -> X 4.67/2.09 U31(tt, N) -> U32(tt, N) 4.67/2.09 U32(tt, N) -> N 4.67/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.67/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.67/2.09 U51(tt, Y) -> U52(tt, Y) 4.67/2.09 U52(tt, Y) -> Y 4.67/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.67/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.67/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.67/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.67/2.09 U71(tt, XS) -> U72(tt, XS) 4.67/2.09 U72(tt, XS) -> XS 4.67/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.67/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.67/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.67/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.67/2.09 head(cons(N, XS)) -> U31(tt, N) 4.67/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.67/2.09 sel(N, XS) -> U41(tt, N, XS) 4.67/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.67/2.09 splitAt(0, XS) -> pair(nil, XS) 4.67/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.67/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.67/2.09 take(N, XS) -> U81(tt, N, XS) 4.67/2.09 4.67/2.09 The set Q consists of the following terms: 4.67/2.09 4.67/2.09 U11(tt, x0, x1) 4.67/2.09 U12(tt, x0, x1) 4.67/2.09 U21(tt, x0) 4.67/2.09 U22(tt, x0) 4.72/2.09 U31(tt, x0) 4.72/2.09 U32(tt, x0) 4.72/2.09 U41(tt, x0, x1) 4.72/2.09 U42(tt, x0, x1) 4.72/2.09 U51(tt, x0) 4.72/2.09 U52(tt, x0) 4.72/2.09 U61(tt, x0, x1, x2) 4.72/2.09 U62(tt, x0, x1, x2) 4.72/2.09 U63(tt, x0, x1, x2) 4.72/2.09 U64(pair(x0, x1), x2) 4.72/2.09 U71(tt, x0) 4.72/2.09 U72(tt, x0) 4.72/2.09 U81(tt, x0, x1) 4.72/2.09 U82(tt, x0, x1) 4.72/2.09 afterNth(x0, x1) 4.72/2.09 fst(pair(x0, x1)) 4.72/2.09 head(cons(x0, x1)) 4.72/2.09 natsFrom(x0) 4.72/2.09 sel(x0, x1) 4.72/2.09 snd(pair(x0, x1)) 4.72/2.09 splitAt(0, x0) 4.72/2.09 splitAt(s(x0), cons(x1, x2)) 4.72/2.09 tail(cons(x0, x1)) 4.72/2.09 take(x0, x1) 4.72/2.09 4.72/2.09 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (12) PIsEmptyProof (EQUIVALENT) 4.72/2.09 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (13) 4.72/2.09 YES 4.72/2.09 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (14) 4.72/2.09 Obligation: 4.72/2.09 Q-restricted context-sensitive dependency pair problem: 4.72/2.09 The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, SPLITAT_2} are replacing on all positions. 4.72/2.09 For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3, U62'_4, U61'_4, U63'_4} we have mu(f) = {1}. 4.72/2.09 4.72/2.09 The TRS P consists of the following rules: 4.72/2.09 4.72/2.09 U61'(tt, N, X, XS) -> U62'(tt, N, X, XS) 4.72/2.09 U62'(tt, N, X, XS) -> U63'(tt, N, X, XS) 4.72/2.09 U63'(tt, N, X, XS) -> SPLITAT(N, XS) 4.72/2.09 SPLITAT(s(N), cons(X, XS)) -> U61'(tt, N, X, XS) 4.72/2.09 4.72/2.09 The TRS R consists of the following rules: 4.72/2.09 4.72/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.72/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.72/2.09 U21(tt, X) -> U22(tt, X) 4.72/2.09 U22(tt, X) -> X 4.72/2.09 U31(tt, N) -> U32(tt, N) 4.72/2.09 U32(tt, N) -> N 4.72/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.72/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.72/2.09 U51(tt, Y) -> U52(tt, Y) 4.72/2.09 U52(tt, Y) -> Y 4.72/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.72/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.72/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.72/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.72/2.09 U71(tt, XS) -> U72(tt, XS) 4.72/2.09 U72(tt, XS) -> XS 4.72/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.72/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.72/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.72/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.72/2.09 head(cons(N, XS)) -> U31(tt, N) 4.72/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.72/2.09 sel(N, XS) -> U41(tt, N, XS) 4.72/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.72/2.09 splitAt(0, XS) -> pair(nil, XS) 4.72/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.72/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.72/2.09 take(N, XS) -> U81(tt, N, XS) 4.72/2.09 4.72/2.09 The set Q consists of the following terms: 4.72/2.09 4.72/2.09 U11(tt, x0, x1) 4.72/2.09 U12(tt, x0, x1) 4.72/2.09 U21(tt, x0) 4.72/2.09 U22(tt, x0) 4.72/2.09 U31(tt, x0) 4.72/2.09 U32(tt, x0) 4.72/2.09 U41(tt, x0, x1) 4.72/2.09 U42(tt, x0, x1) 4.72/2.09 U51(tt, x0) 4.72/2.09 U52(tt, x0) 4.72/2.09 U61(tt, x0, x1, x2) 4.72/2.09 U62(tt, x0, x1, x2) 4.72/2.09 U63(tt, x0, x1, x2) 4.72/2.09 U64(pair(x0, x1), x2) 4.72/2.09 U71(tt, x0) 4.72/2.09 U72(tt, x0) 4.72/2.09 U81(tt, x0, x1) 4.72/2.09 U82(tt, x0, x1) 4.72/2.09 afterNth(x0, x1) 4.72/2.09 fst(pair(x0, x1)) 4.72/2.09 head(cons(x0, x1)) 4.72/2.09 natsFrom(x0) 4.72/2.09 sel(x0, x1) 4.72/2.09 snd(pair(x0, x1)) 4.72/2.09 splitAt(0, x0) 4.72/2.09 splitAt(s(x0), cons(x1, x2)) 4.72/2.09 tail(cons(x0, x1)) 4.72/2.09 take(x0, x1) 4.72/2.09 4.72/2.09 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (15) QCSDPSubtermProof (EQUIVALENT) 4.72/2.09 We use the subterm processor [DA_EMMES]. 4.72/2.09 4.72/2.09 4.72/2.09 The following pairs can be oriented strictly and are deleted. 4.72/2.09 4.72/2.09 SPLITAT(s(N), cons(X, XS)) -> U61'(tt, N, X, XS) 4.72/2.09 The remaining pairs can at least be oriented weakly. 4.72/2.09 4.72/2.09 U61'(tt, N, X, XS) -> U62'(tt, N, X, XS) 4.72/2.09 U62'(tt, N, X, XS) -> U63'(tt, N, X, XS) 4.72/2.09 U63'(tt, N, X, XS) -> SPLITAT(N, XS) 4.72/2.09 Used ordering: Combined order from the following AFS and order. 4.72/2.09 U62'(x1, x2, x3, x4) = x2 4.72/2.09 4.72/2.09 U61'(x1, x2, x3, x4) = x2 4.72/2.09 4.72/2.09 U63'(x1, x2, x3, x4) = x2 4.72/2.09 4.72/2.09 SPLITAT(x1, x2) = x1 4.72/2.09 4.72/2.09 4.72/2.09 Subterm Order 4.72/2.09 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (16) 4.72/2.09 Obligation: 4.72/2.09 Q-restricted context-sensitive dependency pair problem: 4.72/2.09 The symbols in {snd_1, splitAt_2, head_1, afterNth_2, pair_2, fst_1, natsFrom_1, s_1, sel_2, tail_1, take_2, SPLITAT_2} are replacing on all positions. 4.72/2.09 For all symbols f in {U11_3, U12_3, U21_2, U22_2, U31_2, U32_2, U41_3, U42_3, U51_2, U52_2, U61_4, U62_4, U63_4, U64_2, cons_2, U71_2, U72_2, U81_3, U82_3, U62'_4, U61'_4, U63'_4} we have mu(f) = {1}. 4.72/2.09 4.72/2.09 The TRS P consists of the following rules: 4.72/2.09 4.72/2.09 U61'(tt, N, X, XS) -> U62'(tt, N, X, XS) 4.72/2.09 U62'(tt, N, X, XS) -> U63'(tt, N, X, XS) 4.72/2.09 U63'(tt, N, X, XS) -> SPLITAT(N, XS) 4.72/2.09 4.72/2.09 The TRS R consists of the following rules: 4.72/2.09 4.72/2.09 U11(tt, N, XS) -> U12(tt, N, XS) 4.72/2.09 U12(tt, N, XS) -> snd(splitAt(N, XS)) 4.72/2.09 U21(tt, X) -> U22(tt, X) 4.72/2.09 U22(tt, X) -> X 4.72/2.09 U31(tt, N) -> U32(tt, N) 4.72/2.09 U32(tt, N) -> N 4.72/2.09 U41(tt, N, XS) -> U42(tt, N, XS) 4.72/2.09 U42(tt, N, XS) -> head(afterNth(N, XS)) 4.72/2.09 U51(tt, Y) -> U52(tt, Y) 4.72/2.09 U52(tt, Y) -> Y 4.72/2.09 U61(tt, N, X, XS) -> U62(tt, N, X, XS) 4.72/2.09 U62(tt, N, X, XS) -> U63(tt, N, X, XS) 4.72/2.09 U63(tt, N, X, XS) -> U64(splitAt(N, XS), X) 4.72/2.09 U64(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 4.72/2.09 U71(tt, XS) -> U72(tt, XS) 4.72/2.09 U72(tt, XS) -> XS 4.72/2.09 U81(tt, N, XS) -> U82(tt, N, XS) 4.72/2.09 U82(tt, N, XS) -> fst(splitAt(N, XS)) 4.72/2.09 afterNth(N, XS) -> U11(tt, N, XS) 4.72/2.09 fst(pair(X, Y)) -> U21(tt, X) 4.72/2.09 head(cons(N, XS)) -> U31(tt, N) 4.72/2.09 natsFrom(N) -> cons(N, natsFrom(s(N))) 4.72/2.09 sel(N, XS) -> U41(tt, N, XS) 4.72/2.09 snd(pair(X, Y)) -> U51(tt, Y) 4.72/2.09 splitAt(0, XS) -> pair(nil, XS) 4.72/2.09 splitAt(s(N), cons(X, XS)) -> U61(tt, N, X, XS) 4.72/2.09 tail(cons(N, XS)) -> U71(tt, XS) 4.72/2.09 take(N, XS) -> U81(tt, N, XS) 4.72/2.09 4.72/2.09 The set Q consists of the following terms: 4.72/2.09 4.72/2.09 U11(tt, x0, x1) 4.72/2.09 U12(tt, x0, x1) 4.72/2.09 U21(tt, x0) 4.72/2.09 U22(tt, x0) 4.72/2.09 U31(tt, x0) 4.72/2.09 U32(tt, x0) 4.72/2.09 U41(tt, x0, x1) 4.72/2.09 U42(tt, x0, x1) 4.72/2.09 U51(tt, x0) 4.72/2.09 U52(tt, x0) 4.72/2.09 U61(tt, x0, x1, x2) 4.72/2.09 U62(tt, x0, x1, x2) 4.72/2.09 U63(tt, x0, x1, x2) 4.72/2.09 U64(pair(x0, x1), x2) 4.72/2.09 U71(tt, x0) 4.72/2.09 U72(tt, x0) 4.72/2.09 U81(tt, x0, x1) 4.72/2.09 U82(tt, x0, x1) 4.72/2.09 afterNth(x0, x1) 4.72/2.09 fst(pair(x0, x1)) 4.72/2.09 head(cons(x0, x1)) 4.72/2.09 natsFrom(x0) 4.72/2.09 sel(x0, x1) 4.72/2.09 snd(pair(x0, x1)) 4.72/2.09 splitAt(0, x0) 4.72/2.09 splitAt(s(x0), cons(x1, x2)) 4.72/2.09 tail(cons(x0, x1)) 4.72/2.09 take(x0, x1) 4.72/2.09 4.72/2.09 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (17) QCSDependencyGraphProof (EQUIVALENT) 4.72/2.09 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes. 4.72/2.09 4.72/2.09 ---------------------------------------- 4.72/2.09 4.72/2.09 (18) 4.72/2.09 TRUE 4.74/2.12 EOF