5.69/2.12 YES 5.69/2.14 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 5.69/2.14 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 5.69/2.14 5.69/2.14 5.69/2.14 Termination of the given CSR could be proven: 5.69/2.14 5.69/2.14 (0) CSR 5.69/2.14 (1) CSDependencyPairsProof [EQUIVALENT, 123 ms] 5.69/2.14 (2) QCSDP 5.69/2.14 (3) QCSDependencyGraphProof [EQUIVALENT, 3 ms] 5.69/2.14 (4) AND 5.69/2.14 (5) QCSDP 5.69/2.14 (6) QCSUsableRulesProof [EQUIVALENT, 0 ms] 5.69/2.14 (7) QCSDP 5.69/2.14 (8) QCSDPMuMonotonicPoloProof [EQUIVALENT, 61 ms] 5.69/2.14 (9) QCSDP 5.69/2.14 (10) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.69/2.14 (11) AND 5.69/2.14 (12) QCSDP 5.69/2.14 (13) QCSDPSubtermProof [EQUIVALENT, 0 ms] 5.69/2.14 (14) QCSDP 5.69/2.14 (15) PIsEmptyProof [EQUIVALENT, 0 ms] 5.69/2.14 (16) YES 5.69/2.14 (17) QCSDP 5.69/2.14 (18) QCSDPSubtermProof [EQUIVALENT, 0 ms] 5.69/2.14 (19) QCSDP 5.69/2.14 (20) PIsEmptyProof [EQUIVALENT, 0 ms] 5.69/2.14 (21) YES 5.69/2.14 (22) QCSDP 5.69/2.14 (23) QCSDPSubtermProof [EQUIVALENT, 0 ms] 5.69/2.14 (24) QCSDP 5.69/2.14 (25) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.69/2.14 (26) TRUE 5.69/2.14 (27) QCSDP 5.69/2.14 (28) QCSDPSubtermProof [EQUIVALENT, 0 ms] 5.69/2.14 (29) QCSDP 5.69/2.14 (30) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 5.69/2.14 (31) TRUE 5.69/2.14 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (0) 5.69/2.14 Obligation: 5.69/2.14 Context-sensitive rewrite system: 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.14 U102(tt) -> tt 5.69/2.14 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.14 U111(tt) -> tt 5.69/2.14 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.14 U121(tt) -> tt 5.69/2.14 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.14 U132(tt) -> tt 5.69/2.14 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.14 U142(tt) -> tt 5.69/2.14 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.14 U152(tt) -> tt 5.69/2.14 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.14 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.14 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.14 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.14 U182(tt, Y) -> Y 5.69/2.14 U191(tt, XS) -> pair(nil, XS) 5.69/2.14 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.14 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.14 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.14 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.14 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.14 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.14 U212(tt, XS) -> XS 5.69/2.14 U22(tt, X) -> X 5.69/2.14 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.14 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.14 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.14 U32(tt, N) -> N 5.69/2.14 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.14 U42(tt) -> tt 5.69/2.14 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.14 U52(tt) -> tt 5.69/2.14 U61(tt) -> tt 5.69/2.14 U71(tt) -> tt 5.69/2.14 U81(tt) -> tt 5.69/2.14 U91(tt) -> tt 5.69/2.14 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.14 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.14 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.14 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.14 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.14 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.14 isNatural(0) -> tt 5.69/2.14 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.14 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.14 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.14 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.14 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.14 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.14 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.14 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.14 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.14 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.14 5.69/2.14 The replacement map contains the following entries: 5.69/2.14 5.69/2.14 U101: {1} 5.69/2.14 tt: empty set 5.69/2.14 U102: {1} 5.69/2.14 isLNat: empty set 5.69/2.14 U11: {1} 5.69/2.14 U12: {1} 5.69/2.14 U111: {1} 5.69/2.14 snd: {1} 5.69/2.14 splitAt: {1, 2} 5.69/2.14 U121: {1} 5.69/2.14 U131: {1} 5.69/2.14 U132: {1} 5.69/2.14 U141: {1} 5.69/2.14 U142: {1} 5.69/2.14 U151: {1} 5.69/2.14 U152: {1} 5.69/2.14 U161: {1} 5.69/2.14 cons: {1} 5.69/2.14 natsFrom: {1} 5.69/2.14 s: {1} 5.69/2.14 U171: {1} 5.69/2.14 U172: {1} 5.69/2.14 head: {1} 5.69/2.14 afterNth: {1, 2} 5.69/2.14 U181: {1} 5.69/2.14 U182: {1} 5.69/2.14 U191: {1} 5.69/2.14 pair: {1, 2} 5.69/2.14 nil: empty set 5.69/2.14 U201: {1} 5.69/2.14 U202: {1} 5.69/2.14 isNatural: empty set 5.69/2.14 U203: {1} 5.69/2.14 U204: {1} 5.69/2.14 U21: {1} 5.69/2.14 U22: {1} 5.69/2.14 U211: {1} 5.69/2.14 U212: {1} 5.69/2.14 U221: {1} 5.69/2.14 U222: {1} 5.69/2.14 fst: {1} 5.69/2.14 U31: {1} 5.69/2.14 U32: {1} 5.69/2.14 U41: {1} 5.69/2.14 U42: {1} 5.69/2.14 U51: {1} 5.69/2.14 U52: {1} 5.69/2.14 U61: {1} 5.69/2.14 U71: {1} 5.69/2.14 U81: {1} 5.69/2.14 U91: {1} 5.69/2.14 isPLNat: empty set 5.69/2.14 tail: {1} 5.69/2.14 take: {1, 2} 5.69/2.14 0: empty set 5.69/2.14 sel: {1, 2} 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (1) CSDependencyPairsProof (EQUIVALENT) 5.69/2.14 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (2) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, U102'_1, SND_1, SPLITAT_2, U132'_1, U142'_1, U152'_1, HEAD_1, AFTERNTH_2, FST_1, U42'_1, U52'_1, U61'_1, U71'_1, U81'_1, U91'_1, U111'_1, U121'_1, NATSFROM_1, SEL_2, TAIL_1, TAKE_2} are replacing on all positions. 5.69/2.14 For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U101'_2, U12'_3, U11'_3, U131'_2, U141'_2, U151'_2, U172'_3, U171'_3, U182'_2, U181'_2, U202'_4, U201'_4, U203'_4, U204'_2, U22'_2, U21'_3, U212'_2, U211'_2, U222'_3, U221'_3, U32'_2, U31'_3, U41'_2, U51'_2, U161'_2, U191'_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1, isPLNat_1, ISLNAT_1, ISNATURAL_1, ISPLNAT_1, U_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The ordinary context-sensitive dependency pairs DP_o are: 5.69/2.14 U101'(tt, V2) -> U102'(isLNat(V2)) 5.69/2.14 U101'(tt, V2) -> ISLNAT(V2) 5.69/2.14 U11'(tt, N, XS) -> U12'(isLNat(XS), N, XS) 5.69/2.14 U11'(tt, N, XS) -> ISLNAT(XS) 5.69/2.14 U12'(tt, N, XS) -> SND(splitAt(N, XS)) 5.69/2.14 U12'(tt, N, XS) -> SPLITAT(N, XS) 5.69/2.14 U131'(tt, V2) -> U132'(isLNat(V2)) 5.69/2.14 U131'(tt, V2) -> ISLNAT(V2) 5.69/2.14 U141'(tt, V2) -> U142'(isLNat(V2)) 5.69/2.14 U141'(tt, V2) -> ISLNAT(V2) 5.69/2.14 U151'(tt, V2) -> U152'(isLNat(V2)) 5.69/2.14 U151'(tt, V2) -> ISLNAT(V2) 5.69/2.14 U171'(tt, N, XS) -> U172'(isLNat(XS), N, XS) 5.69/2.14 U171'(tt, N, XS) -> ISLNAT(XS) 5.69/2.14 U172'(tt, N, XS) -> HEAD(afterNth(N, XS)) 5.69/2.14 U172'(tt, N, XS) -> AFTERNTH(N, XS) 5.69/2.14 U181'(tt, Y) -> U182'(isLNat(Y), Y) 5.69/2.14 U181'(tt, Y) -> ISLNAT(Y) 5.69/2.14 U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS) 5.69/2.14 U201'(tt, N, X, XS) -> ISNATURAL(X) 5.69/2.14 U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS) 5.69/2.14 U202'(tt, N, X, XS) -> ISLNAT(XS) 5.69/2.14 U203'(tt, N, X, XS) -> U204'(splitAt(N, XS), X) 5.69/2.14 U203'(tt, N, X, XS) -> SPLITAT(N, XS) 5.69/2.14 U21'(tt, X, Y) -> U22'(isLNat(Y), X) 5.69/2.14 U21'(tt, X, Y) -> ISLNAT(Y) 5.69/2.14 U211'(tt, XS) -> U212'(isLNat(XS), XS) 5.69/2.14 U211'(tt, XS) -> ISLNAT(XS) 5.69/2.14 U221'(tt, N, XS) -> U222'(isLNat(XS), N, XS) 5.69/2.14 U221'(tt, N, XS) -> ISLNAT(XS) 5.69/2.14 U222'(tt, N, XS) -> FST(splitAt(N, XS)) 5.69/2.14 U222'(tt, N, XS) -> SPLITAT(N, XS) 5.69/2.14 U31'(tt, N, XS) -> U32'(isLNat(XS), N) 5.69/2.14 U31'(tt, N, XS) -> ISLNAT(XS) 5.69/2.14 U41'(tt, V2) -> U42'(isLNat(V2)) 5.69/2.14 U41'(tt, V2) -> ISLNAT(V2) 5.69/2.14 U51'(tt, V2) -> U52'(isLNat(V2)) 5.69/2.14 U51'(tt, V2) -> ISLNAT(V2) 5.69/2.14 AFTERNTH(N, XS) -> U11'(isNatural(N), N, XS) 5.69/2.14 AFTERNTH(N, XS) -> ISNATURAL(N) 5.69/2.14 FST(pair(X, Y)) -> U21'(isLNat(X), X, Y) 5.69/2.14 FST(pair(X, Y)) -> ISLNAT(X) 5.69/2.14 HEAD(cons(N, XS)) -> U31'(isNatural(N), N, XS) 5.69/2.14 HEAD(cons(N, XS)) -> ISNATURAL(N) 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2) 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2) 5.69/2.14 ISLNAT(cons(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(fst(V1)) -> U61'(isPLNat(V1)) 5.69/2.14 ISLNAT(fst(V1)) -> ISPLNAT(V1) 5.69/2.14 ISLNAT(natsFrom(V1)) -> U71'(isNatural(V1)) 5.69/2.14 ISLNAT(natsFrom(V1)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(snd(V1)) -> U81'(isPLNat(V1)) 5.69/2.14 ISLNAT(snd(V1)) -> ISPLNAT(V1) 5.69/2.14 ISLNAT(tail(V1)) -> U91'(isLNat(V1)) 5.69/2.14 ISLNAT(tail(V1)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2) 5.69/2.14 ISLNAT(take(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(head(V1)) -> U111'(isLNat(V1)) 5.69/2.14 ISNATURAL(head(V1)) -> ISLNAT(V1) 5.69/2.14 ISNATURAL(s(V1)) -> U121'(isNatural(V1)) 5.69/2.14 ISNATURAL(s(V1)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> ISLNAT(V1) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 NATSFROM(N) -> U161'(isNatural(N), N) 5.69/2.14 NATSFROM(N) -> ISNATURAL(N) 5.69/2.14 SEL(N, XS) -> U171'(isNatural(N), N, XS) 5.69/2.14 SEL(N, XS) -> ISNATURAL(N) 5.69/2.14 SND(pair(X, Y)) -> U181'(isLNat(X), Y) 5.69/2.14 SND(pair(X, Y)) -> ISLNAT(X) 5.69/2.14 SPLITAT(0, XS) -> U191'(isLNat(XS), XS) 5.69/2.14 SPLITAT(0, XS) -> ISLNAT(XS) 5.69/2.14 SPLITAT(s(N), cons(X, XS)) -> U201'(isNatural(N), N, X, XS) 5.69/2.14 SPLITAT(s(N), cons(X, XS)) -> ISNATURAL(N) 5.69/2.14 TAIL(cons(N, XS)) -> U211'(isNatural(N), XS) 5.69/2.14 TAIL(cons(N, XS)) -> ISNATURAL(N) 5.69/2.14 TAKE(N, XS) -> U221'(isNatural(N), N, XS) 5.69/2.14 TAKE(N, XS) -> ISNATURAL(N) 5.69/2.14 5.69/2.14 The collapsing dependency pairs are DP_c: 5.69/2.14 U12'(tt, N, XS) -> N 5.69/2.14 U12'(tt, N, XS) -> XS 5.69/2.14 U161'(tt, N) -> N 5.69/2.14 U172'(tt, N, XS) -> N 5.69/2.14 U172'(tt, N, XS) -> XS 5.69/2.14 U182'(tt, Y) -> Y 5.69/2.14 U191'(tt, XS) -> XS 5.69/2.14 U203'(tt, N, X, XS) -> N 5.69/2.14 U203'(tt, N, X, XS) -> XS 5.69/2.14 U204'(pair(YS, ZS), X) -> X 5.69/2.14 U212'(tt, XS) -> XS 5.69/2.14 U22'(tt, X) -> X 5.69/2.14 U222'(tt, N, XS) -> N 5.69/2.14 U222'(tt, N, XS) -> XS 5.69/2.14 U32'(tt, N) -> N 5.69/2.14 5.69/2.14 5.69/2.14 The hidden terms of R are: 5.69/2.14 5.69/2.14 natsFrom(s(x0)) 5.69/2.14 5.69/2.14 Every hiding context is built from: 5.69/2.14 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@5fcf6ecb 5.69/2.14 aprove.DPFramework.CSDPProblem.QCSDPProblem$1@3bc0476b 5.69/2.14 5.69/2.14 Hence, the new unhiding pairs DP_u are : 5.69/2.14 U12'(tt, N, XS) -> U(N) 5.69/2.14 U12'(tt, N, XS) -> U(XS) 5.69/2.14 U161'(tt, N) -> U(N) 5.69/2.14 U172'(tt, N, XS) -> U(N) 5.69/2.14 U172'(tt, N, XS) -> U(XS) 5.69/2.14 U182'(tt, Y) -> U(Y) 5.69/2.14 U191'(tt, XS) -> U(XS) 5.69/2.14 U203'(tt, N, X, XS) -> U(N) 5.69/2.14 U203'(tt, N, X, XS) -> U(XS) 5.69/2.14 U204'(pair(YS, ZS), X) -> U(X) 5.69/2.14 U212'(tt, XS) -> U(XS) 5.69/2.14 U22'(tt, X) -> U(X) 5.69/2.14 U222'(tt, N, XS) -> U(N) 5.69/2.14 U222'(tt, N, XS) -> U(XS) 5.69/2.14 U32'(tt, N) -> U(N) 5.69/2.14 U(s(x_0)) -> U(x_0) 5.69/2.14 U(natsFrom(x_0)) -> U(x_0) 5.69/2.14 U(natsFrom(s(x0))) -> NATSFROM(s(x0)) 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.14 U102(tt) -> tt 5.69/2.14 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.14 U111(tt) -> tt 5.69/2.14 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.14 U121(tt) -> tt 5.69/2.14 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.14 U132(tt) -> tt 5.69/2.14 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.14 U142(tt) -> tt 5.69/2.14 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.14 U152(tt) -> tt 5.69/2.14 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.14 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.14 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.14 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.14 U182(tt, Y) -> Y 5.69/2.14 U191(tt, XS) -> pair(nil, XS) 5.69/2.14 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.14 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.14 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.14 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.14 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.14 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.14 U212(tt, XS) -> XS 5.69/2.14 U22(tt, X) -> X 5.69/2.14 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.14 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.14 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.14 U32(tt, N) -> N 5.69/2.14 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.14 U42(tt) -> tt 5.69/2.14 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.14 U52(tt) -> tt 5.69/2.14 U61(tt) -> tt 5.69/2.14 U71(tt) -> tt 5.69/2.14 U81(tt) -> tt 5.69/2.14 U91(tt) -> tt 5.69/2.14 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.14 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.14 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.14 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.14 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.14 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.14 isNatural(0) -> tt 5.69/2.14 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.14 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.14 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.14 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.14 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.14 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.14 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.14 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.14 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.14 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (3) QCSDependencyGraphProof (EQUIVALENT) 5.69/2.14 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 67 less nodes. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (4) 5.69/2.14 Complex Obligation (AND) 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (5) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2} are replacing on all positions. 5.69/2.14 For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U41'_2, U51'_2, U131'_2, U141'_2, U101'_2, U151'_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1, isPLNat_1, ISLNAT_1, ISNATURAL_1, ISPLNAT_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2) 5.69/2.14 U41'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(head(V1)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2) 5.69/2.14 U51'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(cons(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(s(V1)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2) 5.69/2.14 U131'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(fst(V1)) -> ISPLNAT(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2) 5.69/2.14 U141'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(natsFrom(V1)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(snd(V1)) -> ISPLNAT(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(tail(V1)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2) 5.69/2.14 U101'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(take(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2) 5.69/2.14 U151'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.14 U102(tt) -> tt 5.69/2.14 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.14 U111(tt) -> tt 5.69/2.14 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.14 U121(tt) -> tt 5.69/2.14 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.14 U132(tt) -> tt 5.69/2.14 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.14 U142(tt) -> tt 5.69/2.14 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.14 U152(tt) -> tt 5.69/2.14 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.14 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.14 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.14 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.14 U182(tt, Y) -> Y 5.69/2.14 U191(tt, XS) -> pair(nil, XS) 5.69/2.14 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.14 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.14 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.14 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.14 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.14 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.14 U212(tt, XS) -> XS 5.69/2.14 U22(tt, X) -> X 5.69/2.14 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.14 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.14 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.14 U32(tt, N) -> N 5.69/2.14 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.14 U42(tt) -> tt 5.69/2.14 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.14 U52(tt) -> tt 5.69/2.14 U61(tt) -> tt 5.69/2.14 U71(tt) -> tt 5.69/2.14 U81(tt) -> tt 5.69/2.14 U91(tt) -> tt 5.69/2.14 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.14 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.14 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.14 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.14 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.14 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.14 isNatural(0) -> tt 5.69/2.14 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.14 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.14 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.14 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.14 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.14 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.14 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.14 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.14 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.14 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (6) QCSUsableRulesProof (EQUIVALENT) 5.69/2.14 The following rules are not useable [DA_EMMES] and can be deleted: 5.69/2.14 5.69/2.14 U11(tt, x0, x1) -> U12(isLNat(x1), x0, x1) 5.69/2.14 U12(tt, x0, x1) -> snd(splitAt(x0, x1)) 5.69/2.14 U161(tt, x0) -> cons(x0, natsFrom(s(x0))) 5.69/2.14 U171(tt, x0, x1) -> U172(isLNat(x1), x0, x1) 5.69/2.14 U172(tt, x0, x1) -> head(afterNth(x0, x1)) 5.69/2.14 U181(tt, x0) -> U182(isLNat(x0), x0) 5.69/2.14 U182(tt, x0) -> x0 5.69/2.14 U191(tt, x0) -> pair(nil, x0) 5.69/2.14 U201(tt, x0, x1, x2) -> U202(isNatural(x1), x0, x1, x2) 5.69/2.14 U202(tt, x0, x1, x2) -> U203(isLNat(x2), x0, x1, x2) 5.69/2.14 U203(tt, x0, x1, x2) -> U204(splitAt(x0, x2), x1) 5.69/2.14 U204(pair(x0, x1), x2) -> pair(cons(x2, x0), x1) 5.69/2.14 U21(tt, x0, x1) -> U22(isLNat(x1), x0) 5.69/2.14 U211(tt, x0) -> U212(isLNat(x0), x0) 5.69/2.14 U212(tt, x0) -> x0 5.69/2.14 U22(tt, x0) -> x0 5.69/2.14 U221(tt, x0, x1) -> U222(isLNat(x1), x0, x1) 5.69/2.14 U222(tt, x0, x1) -> fst(splitAt(x0, x1)) 5.69/2.14 U31(tt, x0, x1) -> U32(isLNat(x1), x0) 5.69/2.14 U32(tt, x0) -> x0 5.69/2.14 afterNth(x0, x1) -> U11(isNatural(x0), x0, x1) 5.69/2.14 fst(pair(x0, x1)) -> U21(isLNat(x0), x0, x1) 5.69/2.14 head(cons(x0, x1)) -> U31(isNatural(x0), x0, x1) 5.69/2.14 natsFrom(x0) -> U161(isNatural(x0), x0) 5.69/2.14 sel(x0, x1) -> U171(isNatural(x0), x0, x1) 5.69/2.14 snd(pair(x0, x1)) -> U181(isLNat(x0), x1) 5.69/2.14 splitAt(0, x0) -> U191(isLNat(x0), x0) 5.69/2.14 splitAt(s(x0), cons(x1, x2)) -> U201(isNatural(x0), x0, x1, x2) 5.69/2.14 tail(cons(x0, x1)) -> U211(isNatural(x0), x1) 5.69/2.14 take(x0, x1) -> U221(isNatural(x0), x0, x1) 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (7) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {head_1, U111_1, afterNth_2, s_1, U121_1, sel_2, U132_1, U52_1, fst_1, U61_1, pair_2, natsFrom_1, U71_1, snd_1, U81_1, splitAt_2, U152_1, tail_1, U91_1, take_2, U102_1, U142_1, U42_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U41_2, U131_2, cons_2, U51_2, U141_2, U151_2, U101_2, U41'_2, U51'_2, U131'_2, U141'_2, U101'_2, U151'_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isNatural_1, isLNat_1, isPLNat_1, ISLNAT_1, ISNATURAL_1, ISPLNAT_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2) 5.69/2.14 U41'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(head(V1)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2) 5.69/2.14 U51'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(cons(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(s(V1)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2) 5.69/2.14 U131'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(fst(V1)) -> ISPLNAT(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2) 5.69/2.14 U141'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(natsFrom(V1)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(snd(V1)) -> ISPLNAT(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(tail(V1)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2) 5.69/2.14 U101'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(take(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2) 5.69/2.14 U151'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 isNatural(0) -> tt 5.69/2.14 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.14 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.14 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.14 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.14 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.14 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.14 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.14 U71(tt) -> tt 5.69/2.14 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.14 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.14 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.14 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.14 U102(tt) -> tt 5.69/2.14 U91(tt) -> tt 5.69/2.14 U152(tt) -> tt 5.69/2.14 U81(tt) -> tt 5.69/2.14 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.14 U142(tt) -> tt 5.69/2.14 U61(tt) -> tt 5.69/2.14 U52(tt) -> tt 5.69/2.14 U132(tt) -> tt 5.69/2.14 U121(tt) -> tt 5.69/2.14 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.14 U42(tt) -> tt 5.69/2.14 U111(tt) -> tt 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (8) QCSDPMuMonotonicPoloProof (EQUIVALENT) 5.69/2.14 By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted. 5.69/2.14 5.69/2.14 Strictly oriented dependency pairs: 5.69/2.14 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> U41'(isNatural(V1), V2) 5.69/2.14 U41'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(afterNth(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(head(V1)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(cons(V1, V2)) -> U51'(isNatural(V1), V2) 5.69/2.14 U51'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(cons(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> U131'(isNatural(V1), V2) 5.69/2.14 U131'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(fst(V1)) -> ISPLNAT(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> U141'(isLNat(V1), V2) 5.69/2.14 U141'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(natsFrom(V1)) -> ISNATURAL(V1) 5.69/2.14 ISNATURAL(sel(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(snd(V1)) -> ISPLNAT(V1) 5.69/2.14 ISPLNAT(pair(V1, V2)) -> ISLNAT(V1) 5.69/2.14 ISLNAT(take(V1, V2)) -> U101'(isNatural(V1), V2) 5.69/2.14 U101'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISLNAT(take(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> U151'(isNatural(V1), V2) 5.69/2.14 U151'(tt, V2) -> ISLNAT(V2) 5.69/2.14 ISPLNAT(splitAt(V1, V2)) -> ISNATURAL(V1) 5.69/2.14 5.69/2.14 Strictly oriented rules of the TRS R: 5.69/2.14 5.69/2.14 isNatural(0) -> tt 5.69/2.14 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.14 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.14 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.14 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.14 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.14 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.14 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.14 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.14 U71(tt) -> tt 5.69/2.14 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.14 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.14 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.14 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.14 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.14 U102(tt) -> tt 5.69/2.14 U91(tt) -> tt 5.69/2.14 U152(tt) -> tt 5.69/2.14 U81(tt) -> tt 5.69/2.14 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.14 U142(tt) -> tt 5.69/2.14 U61(tt) -> tt 5.69/2.14 U52(tt) -> tt 5.69/2.14 U132(tt) -> tt 5.69/2.14 U121(tt) -> tt 5.69/2.14 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.14 U42(tt) -> tt 5.69/2.14 U111(tt) -> tt 5.69/2.14 5.69/2.14 Used ordering: POLO with Polynomial interpretation [POLO]: 5.69/2.14 5.69/2.14 POL(0) = 2 5.69/2.14 POL(ISLNAT(x_1)) = 1 + 2*x_1 5.69/2.14 POL(ISNATURAL(x_1)) = 2 + 2*x_1 5.69/2.14 POL(ISPLNAT(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U101(x_1, x_2)) = x_1 + 2*x_2 5.69/2.14 POL(U101'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(U102(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U111(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U121(x_1)) = 2*x_1 5.69/2.14 POL(U131(x_1, x_2)) = 1 + x_1 + 2*x_2 5.69/2.14 POL(U131'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(U132(x_1)) = 2*x_1 5.69/2.14 POL(U141(x_1, x_2)) = x_1 + 2*x_2 5.69/2.14 POL(U141'(x_1, x_2)) = x_1 + 2*x_2 5.69/2.14 POL(U142(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U151(x_1, x_2)) = x_1 + 2*x_2 5.69/2.14 POL(U151'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(U152(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U41(x_1, x_2)) = 2 + x_1 + 2*x_2 5.69/2.14 POL(U41'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(U42(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U51(x_1, x_2)) = x_1 + 2*x_2 5.69/2.14 POL(U51'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(U52(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U61(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U71(x_1)) = 1 + x_1 5.69/2.14 POL(U81(x_1)) = 1 + 2*x_1 5.69/2.14 POL(U91(x_1)) = 2*x_1 5.69/2.14 POL(afterNth(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(fst(x_1)) = 2 + 2*x_1 5.69/2.14 POL(head(x_1)) = 2 + 2*x_1 5.69/2.14 POL(isLNat(x_1)) = x_1 5.69/2.14 POL(isNatural(x_1)) = 2*x_1 5.69/2.14 POL(isPLNat(x_1)) = x_1 5.69/2.14 POL(natsFrom(x_1)) = 2 + 2*x_1 5.69/2.14 POL(nil) = 2 5.69/2.14 POL(pair(x_1, x_2)) = 1 + x_1 + 2*x_2 5.69/2.14 POL(s(x_1)) = 2*x_1 5.69/2.14 POL(sel(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 5.69/2.14 POL(snd(x_1)) = 2 + 2*x_1 5.69/2.14 POL(splitAt(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(tail(x_1)) = 2*x_1 5.69/2.14 POL(take(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 5.69/2.14 POL(tt) = 2 5.69/2.14 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (9) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U41_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1, ISNATURAL_1, ISLNAT_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 5.69/2.14 ISNATURAL(s(V1)) -> ISNATURAL(V1) 5.69/2.14 ISLNAT(tail(V1)) -> ISLNAT(V1) 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (10) QCSDependencyGraphProof (EQUIVALENT) 5.69/2.14 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 2 SCCs. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (11) 5.69/2.14 Complex Obligation (AND) 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (12) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U41_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1, ISLNAT_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 5.69/2.14 ISLNAT(tail(V1)) -> ISLNAT(V1) 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (13) QCSDPSubtermProof (EQUIVALENT) 5.69/2.14 We use the subterm processor [DA_EMMES]. 5.69/2.14 5.69/2.14 5.69/2.14 The following pairs can be oriented strictly and are deleted. 5.69/2.14 5.69/2.14 ISLNAT(tail(V1)) -> ISLNAT(V1) 5.69/2.14 The remaining pairs can at least be oriented weakly. 5.69/2.14 none 5.69/2.14 Used ordering: Combined order from the following AFS and order. 5.69/2.14 ISLNAT(x1) = x1 5.69/2.14 5.69/2.14 5.69/2.14 Subterm Order 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (14) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U41_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 none 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (15) PIsEmptyProof (EQUIVALENT) 5.69/2.14 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (16) 5.69/2.14 YES 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (17) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U41_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1, ISNATURAL_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 5.69/2.14 ISNATURAL(s(V1)) -> ISNATURAL(V1) 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (18) QCSDPSubtermProof (EQUIVALENT) 5.69/2.14 We use the subterm processor [DA_EMMES]. 5.69/2.14 5.69/2.14 5.69/2.14 The following pairs can be oriented strictly and are deleted. 5.69/2.14 5.69/2.14 ISNATURAL(s(V1)) -> ISNATURAL(V1) 5.69/2.14 The remaining pairs can at least be oriented weakly. 5.69/2.14 none 5.69/2.14 Used ordering: Combined order from the following AFS and order. 5.69/2.14 ISNATURAL(x1) = x1 5.69/2.14 5.69/2.14 5.69/2.14 Subterm Order 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (19) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {afterNth_2, s_1, U121_1, tail_1, U91_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U41_2} we have mu(f) = {1}. 5.69/2.14 The symbols in {isLNat_1, isNatural_1} are not replacing on any position. 5.69/2.14 5.69/2.14 The TRS P consists of the following rules: 5.69/2.14 none 5.69/2.14 5.69/2.14 The TRS R consists of the following rules: 5.69/2.14 5.69/2.14 isLNat(nil) -> tt 5.69/2.14 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.14 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.14 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.14 5.69/2.14 Q is empty. 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (20) PIsEmptyProof (EQUIVALENT) 5.69/2.14 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (21) 5.69/2.14 YES 5.69/2.14 5.69/2.14 ---------------------------------------- 5.69/2.14 5.69/2.14 (22) 5.69/2.14 Obligation: 5.69/2.14 Q-restricted context-sensitive dependency pair problem: 5.69/2.14 The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, NATSFROM_1} are replacing on all positions. 5.69/2.14 For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U161'_2} we have mu(f) = {1}. 5.69/2.15 The symbols in {isLNat_1, isNatural_1, isPLNat_1, U_1} are not replacing on any position. 5.69/2.15 5.69/2.15 The TRS P consists of the following rules: 5.69/2.15 5.69/2.15 NATSFROM(N) -> U161'(isNatural(N), N) 5.69/2.15 U161'(tt, N) -> U(N) 5.69/2.15 U(s(x_0)) -> U(x_0) 5.69/2.15 U(natsFrom(x_0)) -> U(x_0) 5.69/2.15 U(natsFrom(s(x0))) -> NATSFROM(s(x0)) 5.69/2.15 5.69/2.15 The TRS R consists of the following rules: 5.69/2.15 5.69/2.15 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.15 U102(tt) -> tt 5.69/2.15 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.15 U111(tt) -> tt 5.69/2.15 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.15 U121(tt) -> tt 5.69/2.15 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.15 U132(tt) -> tt 5.69/2.15 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.15 U142(tt) -> tt 5.69/2.15 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.15 U152(tt) -> tt 5.69/2.15 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.15 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.15 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.15 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.15 U182(tt, Y) -> Y 5.69/2.15 U191(tt, XS) -> pair(nil, XS) 5.69/2.15 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.15 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.15 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.15 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.15 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.15 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.15 U212(tt, XS) -> XS 5.69/2.15 U22(tt, X) -> X 5.69/2.15 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.15 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.15 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.15 U32(tt, N) -> N 5.69/2.15 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.15 U42(tt) -> tt 5.69/2.15 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.15 U52(tt) -> tt 5.69/2.15 U61(tt) -> tt 5.69/2.15 U71(tt) -> tt 5.69/2.15 U81(tt) -> tt 5.69/2.15 U91(tt) -> tt 5.69/2.15 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.15 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.15 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.15 isLNat(nil) -> tt 5.69/2.15 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.15 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.15 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.15 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.15 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.15 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.15 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.15 isNatural(0) -> tt 5.69/2.15 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.15 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.15 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.15 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.15 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.15 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.15 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.15 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.15 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.15 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.15 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.15 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.15 5.69/2.15 Q is empty. 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (23) QCSDPSubtermProof (EQUIVALENT) 5.69/2.15 We use the subterm processor [DA_EMMES]. 5.69/2.15 5.69/2.15 5.69/2.15 The following pairs can be oriented strictly and are deleted. 5.69/2.15 5.69/2.15 U(s(x_0)) -> U(x_0) 5.69/2.15 U(natsFrom(x_0)) -> U(x_0) 5.69/2.15 U(natsFrom(s(x0))) -> NATSFROM(s(x0)) 5.69/2.15 The remaining pairs can at least be oriented weakly. 5.69/2.15 5.69/2.15 NATSFROM(N) -> U161'(isNatural(N), N) 5.69/2.15 U161'(tt, N) -> U(N) 5.69/2.15 Used ordering: Combined order from the following AFS and order. 5.69/2.15 U161'(x1, x2) = x2 5.69/2.15 5.69/2.15 NATSFROM(x1) = x1 5.69/2.15 5.69/2.15 U(x1) = x1 5.69/2.15 5.69/2.15 5.69/2.15 Subterm Order 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (24) 5.69/2.15 Obligation: 5.69/2.15 Q-restricted context-sensitive dependency pair problem: 5.69/2.15 The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, NATSFROM_1} are replacing on all positions. 5.69/2.15 For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U161'_2} we have mu(f) = {1}. 5.69/2.15 The symbols in {isLNat_1, isNatural_1, isPLNat_1, U_1} are not replacing on any position. 5.69/2.15 5.69/2.15 The TRS P consists of the following rules: 5.69/2.15 5.69/2.15 NATSFROM(N) -> U161'(isNatural(N), N) 5.69/2.15 U161'(tt, N) -> U(N) 5.69/2.15 5.69/2.15 The TRS R consists of the following rules: 5.69/2.15 5.69/2.15 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.15 U102(tt) -> tt 5.69/2.15 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.15 U111(tt) -> tt 5.69/2.15 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.15 U121(tt) -> tt 5.69/2.15 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.15 U132(tt) -> tt 5.69/2.15 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.15 U142(tt) -> tt 5.69/2.15 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.15 U152(tt) -> tt 5.69/2.15 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.15 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.15 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.15 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.15 U182(tt, Y) -> Y 5.69/2.15 U191(tt, XS) -> pair(nil, XS) 5.69/2.15 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.15 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.15 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.15 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.15 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.15 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.15 U212(tt, XS) -> XS 5.69/2.15 U22(tt, X) -> X 5.69/2.15 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.15 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.15 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.15 U32(tt, N) -> N 5.69/2.15 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.15 U42(tt) -> tt 5.69/2.15 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.15 U52(tt) -> tt 5.69/2.15 U61(tt) -> tt 5.69/2.15 U71(tt) -> tt 5.69/2.15 U81(tt) -> tt 5.69/2.15 U91(tt) -> tt 5.69/2.15 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.15 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.15 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.15 isLNat(nil) -> tt 5.69/2.15 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.15 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.15 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.15 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.15 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.15 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.15 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.15 isNatural(0) -> tt 5.69/2.15 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.15 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.15 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.15 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.15 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.15 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.15 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.15 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.15 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.15 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.15 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.15 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.15 5.69/2.15 Q is empty. 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (25) QCSDependencyGraphProof (EQUIVALENT) 5.69/2.15 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (26) 5.69/2.15 TRUE 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (27) 5.69/2.15 Obligation: 5.69/2.15 Q-restricted context-sensitive dependency pair problem: 5.69/2.15 The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, SPLITAT_2} are replacing on all positions. 5.69/2.15 For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U202'_4, U201'_4, U203'_4} we have mu(f) = {1}. 5.69/2.15 The symbols in {isLNat_1, isNatural_1, isPLNat_1} are not replacing on any position. 5.69/2.15 5.69/2.15 The TRS P consists of the following rules: 5.69/2.15 5.69/2.15 U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS) 5.69/2.15 U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS) 5.69/2.15 U203'(tt, N, X, XS) -> SPLITAT(N, XS) 5.69/2.15 SPLITAT(s(N), cons(X, XS)) -> U201'(isNatural(N), N, X, XS) 5.69/2.15 5.69/2.15 The TRS R consists of the following rules: 5.69/2.15 5.69/2.15 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.15 U102(tt) -> tt 5.69/2.15 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.15 U111(tt) -> tt 5.69/2.15 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.15 U121(tt) -> tt 5.69/2.15 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.15 U132(tt) -> tt 5.69/2.15 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.15 U142(tt) -> tt 5.69/2.15 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.15 U152(tt) -> tt 5.69/2.15 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.15 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.15 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.15 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.15 U182(tt, Y) -> Y 5.69/2.15 U191(tt, XS) -> pair(nil, XS) 5.69/2.15 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.15 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.15 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.15 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.15 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.15 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.15 U212(tt, XS) -> XS 5.69/2.15 U22(tt, X) -> X 5.69/2.15 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.15 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.15 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.15 U32(tt, N) -> N 5.69/2.15 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.15 U42(tt) -> tt 5.69/2.15 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.15 U52(tt) -> tt 5.69/2.15 U61(tt) -> tt 5.69/2.15 U71(tt) -> tt 5.69/2.15 U81(tt) -> tt 5.69/2.15 U91(tt) -> tt 5.69/2.15 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.15 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.15 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.15 isLNat(nil) -> tt 5.69/2.15 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.15 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.15 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.15 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.15 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.15 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.15 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.15 isNatural(0) -> tt 5.69/2.15 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.15 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.15 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.15 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.15 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.15 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.15 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.15 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.15 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.15 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.15 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.15 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.15 5.69/2.15 Q is empty. 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (28) QCSDPSubtermProof (EQUIVALENT) 5.69/2.15 We use the subterm processor [DA_EMMES]. 5.69/2.15 5.69/2.15 5.69/2.15 The following pairs can be oriented strictly and are deleted. 5.69/2.15 5.69/2.15 SPLITAT(s(N), cons(X, XS)) -> U201'(isNatural(N), N, X, XS) 5.69/2.15 The remaining pairs can at least be oriented weakly. 5.69/2.15 5.69/2.15 U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS) 5.69/2.15 U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS) 5.69/2.15 U203'(tt, N, X, XS) -> SPLITAT(N, XS) 5.69/2.15 Used ordering: Combined order from the following AFS and order. 5.69/2.15 U202'(x1, x2, x3, x4) = x2 5.69/2.15 5.69/2.15 U201'(x1, x2, x3, x4) = x2 5.69/2.15 5.69/2.15 U203'(x1, x2, x3, x4) = x2 5.69/2.15 5.69/2.15 SPLITAT(x1, x2) = x1 5.69/2.15 5.69/2.15 5.69/2.15 Subterm Order 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (29) 5.69/2.15 Obligation: 5.69/2.15 Q-restricted context-sensitive dependency pair problem: 5.69/2.15 The symbols in {U102_1, U111_1, snd_1, splitAt_2, U121_1, U132_1, U142_1, U152_1, natsFrom_1, s_1, head_1, afterNth_2, pair_2, fst_1, U42_1, U52_1, U61_1, U71_1, U81_1, U91_1, tail_1, take_2, sel_2, SPLITAT_2} are replacing on all positions. 5.69/2.15 For all symbols f in {U101_2, U11_3, U12_3, U131_2, U141_2, U151_2, U161_2, cons_2, U171_3, U172_3, U181_2, U182_2, U191_2, U201_4, U202_4, U203_4, U204_2, U21_3, U22_2, U211_2, U212_2, U221_3, U222_3, U31_3, U32_2, U41_2, U51_2, U202'_4, U201'_4, U203'_4} we have mu(f) = {1}. 5.69/2.15 The symbols in {isLNat_1, isNatural_1, isPLNat_1} are not replacing on any position. 5.69/2.15 5.69/2.15 The TRS P consists of the following rules: 5.69/2.15 5.69/2.15 U201'(tt, N, X, XS) -> U202'(isNatural(X), N, X, XS) 5.69/2.15 U202'(tt, N, X, XS) -> U203'(isLNat(XS), N, X, XS) 5.69/2.15 U203'(tt, N, X, XS) -> SPLITAT(N, XS) 5.69/2.15 5.69/2.15 The TRS R consists of the following rules: 5.69/2.15 5.69/2.15 U101(tt, V2) -> U102(isLNat(V2)) 5.69/2.15 U102(tt) -> tt 5.69/2.15 U11(tt, N, XS) -> U12(isLNat(XS), N, XS) 5.69/2.15 U111(tt) -> tt 5.69/2.15 U12(tt, N, XS) -> snd(splitAt(N, XS)) 5.69/2.15 U121(tt) -> tt 5.69/2.15 U131(tt, V2) -> U132(isLNat(V2)) 5.69/2.15 U132(tt) -> tt 5.69/2.15 U141(tt, V2) -> U142(isLNat(V2)) 5.69/2.15 U142(tt) -> tt 5.69/2.15 U151(tt, V2) -> U152(isLNat(V2)) 5.69/2.15 U152(tt) -> tt 5.69/2.15 U161(tt, N) -> cons(N, natsFrom(s(N))) 5.69/2.15 U171(tt, N, XS) -> U172(isLNat(XS), N, XS) 5.69/2.15 U172(tt, N, XS) -> head(afterNth(N, XS)) 5.69/2.15 U181(tt, Y) -> U182(isLNat(Y), Y) 5.69/2.15 U182(tt, Y) -> Y 5.69/2.15 U191(tt, XS) -> pair(nil, XS) 5.69/2.15 U201(tt, N, X, XS) -> U202(isNatural(X), N, X, XS) 5.69/2.15 U202(tt, N, X, XS) -> U203(isLNat(XS), N, X, XS) 5.69/2.15 U203(tt, N, X, XS) -> U204(splitAt(N, XS), X) 5.69/2.15 U204(pair(YS, ZS), X) -> pair(cons(X, YS), ZS) 5.69/2.15 U21(tt, X, Y) -> U22(isLNat(Y), X) 5.69/2.15 U211(tt, XS) -> U212(isLNat(XS), XS) 5.69/2.15 U212(tt, XS) -> XS 5.69/2.15 U22(tt, X) -> X 5.69/2.15 U221(tt, N, XS) -> U222(isLNat(XS), N, XS) 5.69/2.15 U222(tt, N, XS) -> fst(splitAt(N, XS)) 5.69/2.15 U31(tt, N, XS) -> U32(isLNat(XS), N) 5.69/2.15 U32(tt, N) -> N 5.69/2.15 U41(tt, V2) -> U42(isLNat(V2)) 5.69/2.15 U42(tt) -> tt 5.69/2.15 U51(tt, V2) -> U52(isLNat(V2)) 5.69/2.15 U52(tt) -> tt 5.69/2.15 U61(tt) -> tt 5.69/2.15 U71(tt) -> tt 5.69/2.15 U81(tt) -> tt 5.69/2.15 U91(tt) -> tt 5.69/2.15 afterNth(N, XS) -> U11(isNatural(N), N, XS) 5.69/2.15 fst(pair(X, Y)) -> U21(isLNat(X), X, Y) 5.69/2.15 head(cons(N, XS)) -> U31(isNatural(N), N, XS) 5.69/2.15 isLNat(nil) -> tt 5.69/2.15 isLNat(afterNth(V1, V2)) -> U41(isNatural(V1), V2) 5.69/2.15 isLNat(cons(V1, V2)) -> U51(isNatural(V1), V2) 5.69/2.15 isLNat(fst(V1)) -> U61(isPLNat(V1)) 5.69/2.15 isLNat(natsFrom(V1)) -> U71(isNatural(V1)) 5.69/2.15 isLNat(snd(V1)) -> U81(isPLNat(V1)) 5.69/2.15 isLNat(tail(V1)) -> U91(isLNat(V1)) 5.69/2.15 isLNat(take(V1, V2)) -> U101(isNatural(V1), V2) 5.69/2.15 isNatural(0) -> tt 5.69/2.15 isNatural(head(V1)) -> U111(isLNat(V1)) 5.69/2.15 isNatural(s(V1)) -> U121(isNatural(V1)) 5.69/2.15 isNatural(sel(V1, V2)) -> U131(isNatural(V1), V2) 5.69/2.15 isPLNat(pair(V1, V2)) -> U141(isLNat(V1), V2) 5.69/2.15 isPLNat(splitAt(V1, V2)) -> U151(isNatural(V1), V2) 5.69/2.15 natsFrom(N) -> U161(isNatural(N), N) 5.69/2.15 sel(N, XS) -> U171(isNatural(N), N, XS) 5.69/2.15 snd(pair(X, Y)) -> U181(isLNat(X), Y) 5.69/2.15 splitAt(0, XS) -> U191(isLNat(XS), XS) 5.69/2.15 splitAt(s(N), cons(X, XS)) -> U201(isNatural(N), N, X, XS) 5.69/2.15 tail(cons(N, XS)) -> U211(isNatural(N), XS) 5.69/2.15 take(N, XS) -> U221(isNatural(N), N, XS) 5.69/2.15 5.69/2.15 Q is empty. 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (30) QCSDependencyGraphProof (EQUIVALENT) 5.69/2.15 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes. 5.69/2.15 5.69/2.15 ---------------------------------------- 5.69/2.15 5.69/2.15 (31) 5.69/2.15 TRUE 5.80/2.20 EOF