8.98/3.12 YES 9.02/3.15 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 9.02/3.15 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 9.02/3.15 9.02/3.15 9.02/3.15 Termination of the given CSR could be proven: 9.02/3.15 9.02/3.15 (0) CSR 9.02/3.15 (1) CSRRRRProof [EQUIVALENT, 126 ms] 9.02/3.15 (2) CSR 9.02/3.15 (3) CSRRRRProof [EQUIVALENT, 27 ms] 9.02/3.15 (4) CSR 9.02/3.15 (5) CSRRRRProof [EQUIVALENT, 21 ms] 9.02/3.15 (6) CSR 9.02/3.15 (7) CSRRRRProof [EQUIVALENT, 0 ms] 9.02/3.15 (8) CSR 9.02/3.15 (9) CSRRRRProof [EQUIVALENT, 4 ms] 9.02/3.15 (10) CSR 9.02/3.15 (11) CSRRRRProof [EQUIVALENT, 17 ms] 9.02/3.15 (12) CSR 9.02/3.15 (13) CSRRRRProof [EQUIVALENT, 19 ms] 9.02/3.15 (14) CSR 9.02/3.15 (15) CSRRRRProof [EQUIVALENT, 13 ms] 9.02/3.15 (16) CSR 9.02/3.15 (17) CSRRRRProof [EQUIVALENT, 20 ms] 9.02/3.15 (18) CSR 9.02/3.15 (19) CSDependencyPairsProof [EQUIVALENT, 0 ms] 9.02/3.15 (20) QCSDP 9.02/3.15 (21) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.02/3.15 (22) AND 9.02/3.15 (23) QCSDP 9.02/3.15 (24) QCSUsableRulesProof [EQUIVALENT, 0 ms] 9.02/3.15 (25) QCSDP 9.02/3.15 (26) QCSDPMuMonotonicPoloProof [EQUIVALENT, 0 ms] 9.02/3.15 (27) QCSDP 9.02/3.15 (28) QCSDPSubtermProof [EQUIVALENT, 0 ms] 9.02/3.15 (29) QCSDP 9.02/3.15 (30) PIsEmptyProof [EQUIVALENT, 0 ms] 9.02/3.15 (31) YES 9.02/3.15 (32) QCSDP 9.02/3.15 (33) QCSDPSubtermProof [EQUIVALENT, 0 ms] 9.02/3.15 (34) QCSDP 9.02/3.15 (35) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.02/3.15 (36) TRUE 9.02/3.15 (37) QCSDP 9.02/3.15 (38) QCSUsableRulesProof [EQUIVALENT, 0 ms] 9.02/3.15 (39) QCSDP 9.02/3.15 (40) QCSDPMuMonotonicPoloProof [EQUIVALENT, 0 ms] 9.02/3.15 (41) QCSDP 9.02/3.15 (42) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.02/3.15 (43) TRUE 9.02/3.15 (44) QCSDP 9.02/3.15 (45) QCSDPReductionPairProof [EQUIVALENT, 24 ms] 9.02/3.15 (46) QCSDP 9.02/3.15 (47) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.02/3.15 (48) TRUE 9.02/3.15 (49) QCSDP 9.02/3.15 (50) QCSUsableRulesProof [EQUIVALENT, 0 ms] 9.02/3.15 (51) QCSDP 9.02/3.15 (52) QCSDPMuMonotonicPoloProof [EQUIVALENT, 11 ms] 9.02/3.15 (53) QCSDP 9.02/3.15 (54) QCSDependencyGraphProof [EQUIVALENT, 0 ms] 9.02/3.15 (55) TRUE 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (0) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U31(tt, V) -> U32(isNatIListKind(V), V) 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(zeros) -> tt 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(nil) -> 0 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U32: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (1) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U31(tt, V) -> U32(isNatIListKind(V), V) 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(zeros) -> tt 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(nil) -> 0 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U32: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 Used ordering: 9.02/3.15 Polynomial interpretation [POLO]: 9.02/3.15 9.02/3.15 POL(0) = 0 9.02/3.15 POL(U11(x_1, x_2)) = x_1 9.02/3.15 POL(U12(x_1, x_2)) = x_1 9.02/3.15 POL(U13(x_1)) = x_1 9.02/3.15 POL(U21(x_1, x_2)) = x_1 9.02/3.15 POL(U22(x_1, x_2)) = x_1 9.02/3.15 POL(U23(x_1)) = x_1 9.02/3.15 POL(U31(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U32(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U33(x_1)) = x_1 9.02/3.15 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U45(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U46(x_1)) = x_1 9.02/3.15 POL(U51(x_1, x_2)) = x_1 9.02/3.15 POL(U52(x_1)) = x_1 9.02/3.15 POL(U61(x_1)) = x_1 9.02/3.15 POL(U71(x_1)) = x_1 9.02/3.15 POL(U81(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U82(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U83(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U84(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U85(x_1, x_2)) = x_1 9.02/3.15 POL(U86(x_1)) = x_1 9.02/3.15 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(cons(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(isNat(x_1)) = 1 9.02/3.15 POL(isNatIList(x_1)) = 1 + x_1 9.02/3.15 POL(isNatIListKind(x_1)) = 1 9.02/3.15 POL(isNatKind(x_1)) = 1 9.02/3.15 POL(isNatList(x_1)) = 1 9.02/3.15 POL(length(x_1)) = 1 + x_1 9.02/3.15 POL(nil) = 1 9.02/3.15 POL(s(x_1)) = x_1 9.02/3.15 POL(tt) = 1 9.02/3.15 POL(zeros) = 1 9.02/3.15 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.15 9.02/3.15 isNatIList(zeros) -> tt 9.02/3.15 length(nil) -> 0 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (2) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U31(tt, V) -> U32(isNatIListKind(V), V) 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U32: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (3) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U31(tt, V) -> U32(isNatIListKind(V), V) 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U32: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 Used ordering: 9.02/3.15 Polynomial interpretation [POLO]: 9.02/3.15 9.02/3.15 POL(0) = 0 9.02/3.15 POL(U11(x_1, x_2)) = x_1 9.02/3.15 POL(U12(x_1, x_2)) = x_1 9.02/3.15 POL(U13(x_1)) = x_1 9.02/3.15 POL(U21(x_1, x_2)) = x_1 9.02/3.15 POL(U22(x_1, x_2)) = x_1 9.02/3.15 POL(U23(x_1)) = x_1 9.02/3.15 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 9.02/3.15 POL(U32(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U33(x_1)) = x_1 9.02/3.15 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U43(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U45(x_1, x_2)) = 1 + x_1 + x_2 9.02/3.15 POL(U46(x_1)) = x_1 9.02/3.15 POL(U51(x_1, x_2)) = x_1 9.02/3.15 POL(U52(x_1)) = x_1 9.02/3.15 POL(U61(x_1)) = x_1 9.02/3.15 POL(U71(x_1)) = x_1 9.02/3.15 POL(U81(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U82(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U83(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U84(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U85(x_1, x_2)) = x_1 9.02/3.15 POL(U86(x_1)) = x_1 9.02/3.15 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(cons(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(isNat(x_1)) = 0 9.02/3.15 POL(isNatIList(x_1)) = 1 + x_1 9.02/3.15 POL(isNatIListKind(x_1)) = 0 9.02/3.15 POL(isNatKind(x_1)) = 0 9.02/3.15 POL(isNatList(x_1)) = 0 9.02/3.15 POL(length(x_1)) = x_1 9.02/3.15 POL(nil) = 1 9.02/3.15 POL(s(x_1)) = x_1 9.02/3.15 POL(tt) = 0 9.02/3.15 POL(zeros) = 1 9.02/3.15 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.15 9.02/3.15 U31(tt, V) -> U32(isNatIListKind(V), V) 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (4) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U32: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (5) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U32: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 Used ordering: 9.02/3.15 Polynomial interpretation [POLO]: 9.02/3.15 9.02/3.15 POL(0) = 0 9.02/3.15 POL(U11(x_1, x_2)) = x_1 9.02/3.15 POL(U12(x_1, x_2)) = x_1 9.02/3.15 POL(U13(x_1)) = x_1 9.02/3.15 POL(U21(x_1, x_2)) = x_1 9.02/3.15 POL(U22(x_1, x_2)) = x_1 9.02/3.15 POL(U23(x_1)) = x_1 9.02/3.15 POL(U31(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U32(x_1, x_2)) = 1 + x_1 9.02/3.15 POL(U33(x_1)) = x_1 9.02/3.15 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U45(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U46(x_1)) = x_1 9.02/3.15 POL(U51(x_1, x_2)) = x_1 9.02/3.15 POL(U52(x_1)) = x_1 9.02/3.15 POL(U61(x_1)) = x_1 9.02/3.15 POL(U71(x_1)) = x_1 9.02/3.15 POL(U81(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U82(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U83(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U84(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U85(x_1, x_2)) = x_1 9.02/3.15 POL(U86(x_1)) = x_1 9.02/3.15 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(cons(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(isNat(x_1)) = 0 9.02/3.15 POL(isNatIList(x_1)) = x_1 9.02/3.15 POL(isNatIListKind(x_1)) = 0 9.02/3.15 POL(isNatKind(x_1)) = 0 9.02/3.15 POL(isNatList(x_1)) = 0 9.02/3.15 POL(length(x_1)) = x_1 9.02/3.15 POL(nil) = 1 9.02/3.15 POL(s(x_1)) = x_1 9.02/3.15 POL(tt) = 0 9.02/3.15 POL(zeros) = 1 9.02/3.15 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.15 9.02/3.15 U32(tt, V) -> U33(isNatList(V)) 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (6) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (7) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U33(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U33: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 Used ordering: 9.02/3.15 Polynomial interpretation [POLO]: 9.02/3.15 9.02/3.15 POL(0) = 0 9.02/3.15 POL(U11(x_1, x_2)) = x_1 9.02/3.15 POL(U12(x_1, x_2)) = x_1 9.02/3.15 POL(U13(x_1)) = x_1 9.02/3.15 POL(U21(x_1, x_2)) = x_1 9.02/3.15 POL(U22(x_1, x_2)) = x_1 9.02/3.15 POL(U23(x_1)) = x_1 9.02/3.15 POL(U31(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U33(x_1)) = 1 + x_1 9.02/3.15 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U45(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U46(x_1)) = x_1 9.02/3.15 POL(U51(x_1, x_2)) = x_1 9.02/3.15 POL(U52(x_1)) = x_1 9.02/3.15 POL(U61(x_1)) = x_1 9.02/3.15 POL(U71(x_1)) = x_1 9.02/3.15 POL(U81(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U82(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U83(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U84(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U85(x_1, x_2)) = x_1 9.02/3.15 POL(U86(x_1)) = x_1 9.02/3.15 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(cons(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(isNat(x_1)) = 1 9.02/3.15 POL(isNatIList(x_1)) = 1 + x_1 9.02/3.15 POL(isNatIListKind(x_1)) = 1 9.02/3.15 POL(isNatKind(x_1)) = 1 9.02/3.15 POL(isNatList(x_1)) = 1 9.02/3.15 POL(length(x_1)) = 1 + x_1 9.02/3.15 POL(nil) = 1 9.02/3.15 POL(s(x_1)) = x_1 9.02/3.15 POL(tt) = 1 9.02/3.15 POL(zeros) = 1 9.02/3.15 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.15 9.02/3.15 U33(tt) -> tt 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (8) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (9) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U31: {1} 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 Used ordering: 9.02/3.15 Polynomial interpretation [POLO]: 9.02/3.15 9.02/3.15 POL(0) = 0 9.02/3.15 POL(U11(x_1, x_2)) = x_1 9.02/3.15 POL(U12(x_1, x_2)) = x_1 9.02/3.15 POL(U13(x_1)) = x_1 9.02/3.15 POL(U21(x_1, x_2)) = x_1 9.02/3.15 POL(U22(x_1, x_2)) = x_1 9.02/3.15 POL(U23(x_1)) = x_1 9.02/3.15 POL(U31(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U42(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U43(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U44(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.15 POL(U45(x_1, x_2)) = 1 + x_1 + x_2 9.02/3.15 POL(U46(x_1)) = x_1 9.02/3.15 POL(U51(x_1, x_2)) = x_1 9.02/3.15 POL(U52(x_1)) = x_1 9.02/3.15 POL(U61(x_1)) = x_1 9.02/3.15 POL(U71(x_1)) = x_1 9.02/3.15 POL(U81(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U82(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U83(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U84(x_1, x_2, x_3)) = x_1 9.02/3.15 POL(U85(x_1, x_2)) = x_1 9.02/3.15 POL(U86(x_1)) = x_1 9.02/3.15 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(cons(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(isNat(x_1)) = 0 9.02/3.15 POL(isNatIList(x_1)) = 1 + x_1 9.02/3.15 POL(isNatIListKind(x_1)) = 0 9.02/3.15 POL(isNatKind(x_1)) = 0 9.02/3.15 POL(isNatList(x_1)) = 0 9.02/3.15 POL(length(x_1)) = x_1 9.02/3.15 POL(nil) = 1 9.02/3.15 POL(s(x_1)) = x_1 9.02/3.15 POL(tt) = 0 9.02/3.15 POL(zeros) = 1 9.02/3.15 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.15 9.02/3.15 isNatIList(V) -> U31(isNatIListKind(V), V) 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (10) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (11) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 Used ordering: 9.02/3.15 Polynomial interpretation [POLO]: 9.02/3.15 9.02/3.15 POL(0) = 0 9.02/3.15 POL(U11(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U12(x_1, x_2)) = 2*x_1 + x_2 9.02/3.15 POL(U13(x_1)) = x_1 9.02/3.15 POL(U21(x_1, x_2)) = 2*x_1 + x_2 9.02/3.15 POL(U22(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(U23(x_1)) = x_1 9.02/3.15 POL(U41(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U42(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U43(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U44(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U45(x_1, x_2)) = x_1 + 2*x_2 9.02/3.15 POL(U46(x_1)) = 2*x_1 9.02/3.15 POL(U51(x_1, x_2)) = 2*x_1 9.02/3.15 POL(U52(x_1)) = 2*x_1 9.02/3.15 POL(U61(x_1)) = 2*x_1 9.02/3.15 POL(U71(x_1)) = 2*x_1 9.02/3.15 POL(U81(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U82(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.02/3.15 POL(U83(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U84(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.15 POL(U85(x_1, x_2)) = x_1 + 2*x_2 9.02/3.15 POL(U86(x_1)) = 2*x_1 9.02/3.15 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.02/3.15 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.15 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 9.02/3.15 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.15 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 9.02/3.15 POL(isNat(x_1)) = x_1 9.02/3.15 POL(isNatIList(x_1)) = x_1 9.02/3.15 POL(isNatIListKind(x_1)) = 0 9.02/3.15 POL(isNatKind(x_1)) = 0 9.02/3.15 POL(isNatList(x_1)) = x_1 9.02/3.15 POL(length(x_1)) = x_1 9.02/3.15 POL(nil) = 2 9.02/3.15 POL(s(x_1)) = x_1 9.02/3.15 POL(tt) = 0 9.02/3.15 POL(zeros) = 0 9.02/3.15 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.15 9.02/3.15 isNatList(nil) -> tt 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (12) 9.02/3.15 Obligation: 9.02/3.15 Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.15 U13(tt) -> tt 9.02/3.15 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.15 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.15 U23(tt) -> tt 9.02/3.15 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.15 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.15 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.15 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.15 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.15 U46(tt) -> tt 9.02/3.15 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.15 U52(tt) -> tt 9.02/3.15 U61(tt) -> tt 9.02/3.15 U71(tt) -> tt 9.02/3.15 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.15 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.15 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.15 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.15 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.15 U86(tt) -> tt 9.02/3.15 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.15 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.15 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.15 U94(tt, L) -> s(length(L)) 9.02/3.15 isNat(0) -> tt 9.02/3.15 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.15 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.15 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.15 isNatIListKind(nil) -> tt 9.02/3.15 isNatIListKind(zeros) -> tt 9.02/3.15 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.15 isNatKind(0) -> tt 9.02/3.15 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.15 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.15 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.15 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.15 9.02/3.15 The replacement map contains the following entries: 9.02/3.15 9.02/3.15 zeros: empty set 9.02/3.15 cons: {1} 9.02/3.15 0: empty set 9.02/3.15 U11: {1} 9.02/3.15 tt: empty set 9.02/3.15 U12: {1} 9.02/3.15 isNatIListKind: empty set 9.02/3.15 U13: {1} 9.02/3.15 isNatList: empty set 9.02/3.15 U21: {1} 9.02/3.15 U22: {1} 9.02/3.15 isNatKind: empty set 9.02/3.15 U23: {1} 9.02/3.15 isNat: empty set 9.02/3.15 U41: {1} 9.02/3.15 U42: {1} 9.02/3.15 U43: {1} 9.02/3.15 U44: {1} 9.02/3.15 U45: {1} 9.02/3.15 U46: {1} 9.02/3.15 isNatIList: empty set 9.02/3.15 U51: {1} 9.02/3.15 U52: {1} 9.02/3.15 U61: {1} 9.02/3.15 U71: {1} 9.02/3.15 U81: {1} 9.02/3.15 U82: {1} 9.02/3.15 U83: {1} 9.02/3.15 U84: {1} 9.02/3.15 U85: {1} 9.02/3.15 U86: {1} 9.02/3.15 U91: {1} 9.02/3.15 U92: {1} 9.02/3.15 U93: {1} 9.02/3.15 U94: {1} 9.02/3.15 s: {1} 9.02/3.15 length: {1} 9.02/3.15 nil: empty set 9.02/3.15 9.02/3.15 ---------------------------------------- 9.02/3.15 9.02/3.15 (13) CSRRRRProof (EQUIVALENT) 9.02/3.15 The following CSR is given: Context-sensitive rewrite system: 9.02/3.15 The TRS R consists of the following rules: 9.02/3.15 9.02/3.15 zeros -> cons(0, zeros) 9.02/3.15 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.15 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.16 U13(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 The replacement map contains the following entries: 9.02/3.16 9.02/3.16 zeros: empty set 9.02/3.16 cons: {1} 9.02/3.16 0: empty set 9.02/3.16 U11: {1} 9.02/3.16 tt: empty set 9.02/3.16 U12: {1} 9.02/3.16 isNatIListKind: empty set 9.02/3.16 U13: {1} 9.02/3.16 isNatList: empty set 9.02/3.16 U21: {1} 9.02/3.16 U22: {1} 9.02/3.16 isNatKind: empty set 9.02/3.16 U23: {1} 9.02/3.16 isNat: empty set 9.02/3.16 U41: {1} 9.02/3.16 U42: {1} 9.02/3.16 U43: {1} 9.02/3.16 U44: {1} 9.02/3.16 U45: {1} 9.02/3.16 U46: {1} 9.02/3.16 isNatIList: empty set 9.02/3.16 U51: {1} 9.02/3.16 U52: {1} 9.02/3.16 U61: {1} 9.02/3.16 U71: {1} 9.02/3.16 U81: {1} 9.02/3.16 U82: {1} 9.02/3.16 U83: {1} 9.02/3.16 U84: {1} 9.02/3.16 U85: {1} 9.02/3.16 U86: {1} 9.02/3.16 U91: {1} 9.02/3.16 U92: {1} 9.02/3.16 U93: {1} 9.02/3.16 U94: {1} 9.02/3.16 s: {1} 9.02/3.16 length: {1} 9.02/3.16 nil: empty set 9.02/3.16 Used ordering: 9.02/3.16 Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 0 9.02/3.16 POL(U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 9.02/3.16 POL(U12(x_1, x_2)) = 1 + x_1 + 2*x_2 9.02/3.16 POL(U13(x_1)) = x_1 9.02/3.16 POL(U21(x_1, x_2)) = 2*x_1 + 2*x_2 9.02/3.16 POL(U22(x_1, x_2)) = 2*x_1 + 2*x_2 9.02/3.16 POL(U23(x_1)) = x_1 9.02/3.16 POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U42(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U43(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U44(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U45(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(U46(x_1)) = 2*x_1 9.02/3.16 POL(U51(x_1, x_2)) = 2*x_1 9.02/3.16 POL(U52(x_1)) = x_1 9.02/3.16 POL(U61(x_1)) = x_1 9.02/3.16 POL(U71(x_1)) = x_1 9.02/3.16 POL(U81(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U82(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 9.02/3.16 POL(U83(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + x_3 9.02/3.16 POL(U84(x_1, x_2, x_3)) = x_1 + 2*x_2 + x_3 9.02/3.16 POL(U85(x_1, x_2)) = x_1 + x_2 9.02/3.16 POL(U86(x_1)) = x_1 9.02/3.16 POL(U91(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U92(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3 9.02/3.16 POL(U93(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 9.02/3.16 POL(U94(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 9.02/3.16 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 9.02/3.16 POL(isNat(x_1)) = 2*x_1 9.02/3.16 POL(isNatIList(x_1)) = x_1 9.02/3.16 POL(isNatIListKind(x_1)) = 0 9.02/3.16 POL(isNatKind(x_1)) = 0 9.02/3.16 POL(isNatList(x_1)) = x_1 9.02/3.16 POL(length(x_1)) = 1 + 2*x_1 9.02/3.16 POL(nil) = 2 9.02/3.16 POL(s(x_1)) = x_1 9.02/3.16 POL(tt) = 0 9.02/3.16 POL(zeros) = 0 9.02/3.16 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.16 9.02/3.16 U11(tt, V1) -> U12(isNatIListKind(V1), V1) 9.02/3.16 U12(tt, V1) -> U13(isNatList(V1)) 9.02/3.16 9.02/3.16 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (14) 9.02/3.16 Obligation: 9.02/3.16 Context-sensitive rewrite system: 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U13(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 The replacement map contains the following entries: 9.02/3.16 9.02/3.16 zeros: empty set 9.02/3.16 cons: {1} 9.02/3.16 0: empty set 9.02/3.16 U11: {1} 9.02/3.16 tt: empty set 9.02/3.16 isNatIListKind: empty set 9.02/3.16 U13: {1} 9.02/3.16 isNatList: empty set 9.02/3.16 U21: {1} 9.02/3.16 U22: {1} 9.02/3.16 isNatKind: empty set 9.02/3.16 U23: {1} 9.02/3.16 isNat: empty set 9.02/3.16 U41: {1} 9.02/3.16 U42: {1} 9.02/3.16 U43: {1} 9.02/3.16 U44: {1} 9.02/3.16 U45: {1} 9.02/3.16 U46: {1} 9.02/3.16 isNatIList: empty set 9.02/3.16 U51: {1} 9.02/3.16 U52: {1} 9.02/3.16 U61: {1} 9.02/3.16 U71: {1} 9.02/3.16 U81: {1} 9.02/3.16 U82: {1} 9.02/3.16 U83: {1} 9.02/3.16 U84: {1} 9.02/3.16 U85: {1} 9.02/3.16 U86: {1} 9.02/3.16 U91: {1} 9.02/3.16 U92: {1} 9.02/3.16 U93: {1} 9.02/3.16 U94: {1} 9.02/3.16 s: {1} 9.02/3.16 length: {1} 9.02/3.16 nil: empty set 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (15) CSRRRRProof (EQUIVALENT) 9.02/3.16 The following CSR is given: Context-sensitive rewrite system: 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U13(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 The replacement map contains the following entries: 9.02/3.16 9.02/3.16 zeros: empty set 9.02/3.16 cons: {1} 9.02/3.16 0: empty set 9.02/3.16 U11: {1} 9.02/3.16 tt: empty set 9.02/3.16 isNatIListKind: empty set 9.02/3.16 U13: {1} 9.02/3.16 isNatList: empty set 9.02/3.16 U21: {1} 9.02/3.16 U22: {1} 9.02/3.16 isNatKind: empty set 9.02/3.16 U23: {1} 9.02/3.16 isNat: empty set 9.02/3.16 U41: {1} 9.02/3.16 U42: {1} 9.02/3.16 U43: {1} 9.02/3.16 U44: {1} 9.02/3.16 U45: {1} 9.02/3.16 U46: {1} 9.02/3.16 isNatIList: empty set 9.02/3.16 U51: {1} 9.02/3.16 U52: {1} 9.02/3.16 U61: {1} 9.02/3.16 U71: {1} 9.02/3.16 U81: {1} 9.02/3.16 U82: {1} 9.02/3.16 U83: {1} 9.02/3.16 U84: {1} 9.02/3.16 U85: {1} 9.02/3.16 U86: {1} 9.02/3.16 U91: {1} 9.02/3.16 U92: {1} 9.02/3.16 U93: {1} 9.02/3.16 U94: {1} 9.02/3.16 s: {1} 9.02/3.16 length: {1} 9.02/3.16 nil: empty set 9.02/3.16 Used ordering: 9.02/3.16 Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 0 9.02/3.16 POL(U11(x_1, x_2)) = x_1 9.02/3.16 POL(U13(x_1)) = 1 + x_1 9.02/3.16 POL(U21(x_1, x_2)) = x_1 9.02/3.16 POL(U22(x_1, x_2)) = x_1 9.02/3.16 POL(U23(x_1)) = x_1 9.02/3.16 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U43(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U44(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U45(x_1, x_2)) = x_1 + x_2 9.02/3.16 POL(U46(x_1)) = x_1 9.02/3.16 POL(U51(x_1, x_2)) = x_1 9.02/3.16 POL(U52(x_1)) = x_1 9.02/3.16 POL(U61(x_1)) = x_1 9.02/3.16 POL(U71(x_1)) = x_1 9.02/3.16 POL(U81(x_1, x_2, x_3)) = x_1 9.02/3.16 POL(U82(x_1, x_2, x_3)) = x_1 9.02/3.16 POL(U83(x_1, x_2, x_3)) = x_1 9.02/3.16 POL(U84(x_1, x_2, x_3)) = x_1 9.02/3.16 POL(U85(x_1, x_2)) = x_1 9.02/3.16 POL(U86(x_1)) = x_1 9.02/3.16 POL(U91(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U92(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U93(x_1, x_2, x_3)) = x_1 + x_2 + x_3 9.02/3.16 POL(U94(x_1, x_2)) = x_1 + x_2 9.02/3.16 POL(cons(x_1, x_2)) = x_1 + x_2 9.02/3.16 POL(isNat(x_1)) = 1 9.02/3.16 POL(isNatIList(x_1)) = 1 + x_1 9.02/3.16 POL(isNatIListKind(x_1)) = 1 9.02/3.16 POL(isNatKind(x_1)) = 1 9.02/3.16 POL(isNatList(x_1)) = 1 9.02/3.16 POL(length(x_1)) = 1 + x_1 9.02/3.16 POL(nil) = 1 9.02/3.16 POL(s(x_1)) = x_1 9.02/3.16 POL(tt) = 1 9.02/3.16 POL(zeros) = 1 9.02/3.16 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.16 9.02/3.16 U13(tt) -> tt 9.02/3.16 9.02/3.16 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (16) 9.02/3.16 Obligation: 9.02/3.16 Context-sensitive rewrite system: 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 The replacement map contains the following entries: 9.02/3.16 9.02/3.16 zeros: empty set 9.02/3.16 cons: {1} 9.02/3.16 0: empty set 9.02/3.16 U11: {1} 9.02/3.16 tt: empty set 9.02/3.16 isNatIListKind: empty set 9.02/3.16 isNatList: empty set 9.02/3.16 U21: {1} 9.02/3.16 U22: {1} 9.02/3.16 isNatKind: empty set 9.02/3.16 U23: {1} 9.02/3.16 isNat: empty set 9.02/3.16 U41: {1} 9.02/3.16 U42: {1} 9.02/3.16 U43: {1} 9.02/3.16 U44: {1} 9.02/3.16 U45: {1} 9.02/3.16 U46: {1} 9.02/3.16 isNatIList: empty set 9.02/3.16 U51: {1} 9.02/3.16 U52: {1} 9.02/3.16 U61: {1} 9.02/3.16 U71: {1} 9.02/3.16 U81: {1} 9.02/3.16 U82: {1} 9.02/3.16 U83: {1} 9.02/3.16 U84: {1} 9.02/3.16 U85: {1} 9.02/3.16 U86: {1} 9.02/3.16 U91: {1} 9.02/3.16 U92: {1} 9.02/3.16 U93: {1} 9.02/3.16 U94: {1} 9.02/3.16 s: {1} 9.02/3.16 length: {1} 9.02/3.16 nil: empty set 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (17) CSRRRRProof (EQUIVALENT) 9.02/3.16 The following CSR is given: Context-sensitive rewrite system: 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 The replacement map contains the following entries: 9.02/3.16 9.02/3.16 zeros: empty set 9.02/3.16 cons: {1} 9.02/3.16 0: empty set 9.02/3.16 U11: {1} 9.02/3.16 tt: empty set 9.02/3.16 isNatIListKind: empty set 9.02/3.16 isNatList: empty set 9.02/3.16 U21: {1} 9.02/3.16 U22: {1} 9.02/3.16 isNatKind: empty set 9.02/3.16 U23: {1} 9.02/3.16 isNat: empty set 9.02/3.16 U41: {1} 9.02/3.16 U42: {1} 9.02/3.16 U43: {1} 9.02/3.16 U44: {1} 9.02/3.16 U45: {1} 9.02/3.16 U46: {1} 9.02/3.16 isNatIList: empty set 9.02/3.16 U51: {1} 9.02/3.16 U52: {1} 9.02/3.16 U61: {1} 9.02/3.16 U71: {1} 9.02/3.16 U81: {1} 9.02/3.16 U82: {1} 9.02/3.16 U83: {1} 9.02/3.16 U84: {1} 9.02/3.16 U85: {1} 9.02/3.16 U86: {1} 9.02/3.16 U91: {1} 9.02/3.16 U92: {1} 9.02/3.16 U93: {1} 9.02/3.16 U94: {1} 9.02/3.16 s: {1} 9.02/3.16 length: {1} 9.02/3.16 nil: empty set 9.02/3.16 Used ordering: 9.02/3.16 Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 0 9.02/3.16 POL(U11(x_1, x_2)) = 2*x_1 9.02/3.16 POL(U21(x_1, x_2)) = x_1 + x_2 9.02/3.16 POL(U22(x_1, x_2)) = 2*x_1 + x_2 9.02/3.16 POL(U23(x_1)) = x_1 9.02/3.16 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.02/3.16 POL(U42(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.02/3.16 POL(U43(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.16 POL(U44(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.16 POL(U45(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(U46(x_1)) = 2*x_1 9.02/3.16 POL(U51(x_1, x_2)) = 2*x_1 9.02/3.16 POL(U52(x_1)) = 2*x_1 9.02/3.16 POL(U61(x_1)) = 2*x_1 9.02/3.16 POL(U71(x_1)) = x_1 9.02/3.16 POL(U81(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 9.02/3.16 POL(U82(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.16 POL(U83(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.16 POL(U84(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 9.02/3.16 POL(U85(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(U86(x_1)) = x_1 9.02/3.16 POL(U91(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 9.02/3.16 POL(U92(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + x_3 9.02/3.16 POL(U93(x_1, x_2, x_3)) = 1 + x_1 + x_2 9.02/3.16 POL(U94(x_1, x_2)) = 1 + 2*x_1 + x_2 9.02/3.16 POL(cons(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(isNat(x_1)) = x_1 9.02/3.16 POL(isNatIList(x_1)) = x_1 9.02/3.16 POL(isNatIListKind(x_1)) = 0 9.02/3.16 POL(isNatKind(x_1)) = 0 9.02/3.16 POL(isNatList(x_1)) = x_1 9.02/3.16 POL(length(x_1)) = 1 + x_1 9.02/3.16 POL(nil) = 2 9.02/3.16 POL(s(x_1)) = x_1 9.02/3.16 POL(tt) = 0 9.02/3.16 POL(zeros) = 0 9.02/3.16 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 9.02/3.16 9.02/3.16 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 9.02/3.16 9.02/3.16 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (18) 9.02/3.16 Obligation: 9.02/3.16 Context-sensitive rewrite system: 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 The replacement map contains the following entries: 9.02/3.16 9.02/3.16 zeros: empty set 9.02/3.16 cons: {1} 9.02/3.16 0: empty set 9.02/3.16 tt: empty set 9.02/3.16 isNatIListKind: empty set 9.02/3.16 isNatList: empty set 9.02/3.16 U21: {1} 9.02/3.16 U22: {1} 9.02/3.16 isNatKind: empty set 9.02/3.16 U23: {1} 9.02/3.16 isNat: empty set 9.02/3.16 U41: {1} 9.02/3.16 U42: {1} 9.02/3.16 U43: {1} 9.02/3.16 U44: {1} 9.02/3.16 U45: {1} 9.02/3.16 U46: {1} 9.02/3.16 isNatIList: empty set 9.02/3.16 U51: {1} 9.02/3.16 U52: {1} 9.02/3.16 U61: {1} 9.02/3.16 U71: {1} 9.02/3.16 U81: {1} 9.02/3.16 U82: {1} 9.02/3.16 U83: {1} 9.02/3.16 U84: {1} 9.02/3.16 U85: {1} 9.02/3.16 U86: {1} 9.02/3.16 U91: {1} 9.02/3.16 U92: {1} 9.02/3.16 U93: {1} 9.02/3.16 U94: {1} 9.02/3.16 s: {1} 9.02/3.16 length: {1} 9.02/3.16 nil: empty set 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (19) CSDependencyPairsProof (EQUIVALENT) 9.02/3.16 Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem. 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (20) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1, U23'_1, U46'_1, U52'_1, U86'_1, LENGTH_1, U61'_1, U71'_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U22'_2, U21'_2, U42'_3, U41'_3, U43'_3, U44'_3, U45'_2, U51'_2, U82'_3, U81'_3, U83'_3, U84'_3, U85'_2, U92'_3, U91'_3, U93'_3, U94'_2} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATKIND_1, ISNAT_1, ISNATILISTKIND_1, ISNATILIST_1, ISNATLIST_1, U_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The ordinary context-sensitive dependency pairs DP_o are: 9.02/3.16 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.02/3.16 U21'(tt, V1) -> ISNATKIND(V1) 9.02/3.16 U22'(tt, V1) -> U23'(isNat(V1)) 9.02/3.16 U22'(tt, V1) -> ISNAT(V1) 9.02/3.16 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.02/3.16 U41'(tt, V1, V2) -> ISNATKIND(V1) 9.02/3.16 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.02/3.16 U42'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.02/3.16 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.02/3.16 U43'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.02/3.16 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.02/3.16 U44'(tt, V1, V2) -> ISNAT(V1) 9.02/3.16 U45'(tt, V2) -> U46'(isNatIList(V2)) 9.02/3.16 U45'(tt, V2) -> ISNATILIST(V2) 9.02/3.16 U51'(tt, V2) -> U52'(isNatIListKind(V2)) 9.02/3.16 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.02/3.16 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.02/3.16 U81'(tt, V1, V2) -> ISNATKIND(V1) 9.02/3.16 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.02/3.16 U82'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.02/3.16 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.02/3.16 U83'(tt, V1, V2) -> ISNATILISTKIND(V2) 9.02/3.16 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.02/3.16 U84'(tt, V1, V2) -> ISNAT(V1) 9.02/3.16 U85'(tt, V2) -> U86'(isNatList(V2)) 9.02/3.16 U85'(tt, V2) -> ISNATLIST(V2) 9.02/3.16 U91'(tt, L, N) -> U92'(isNatIListKind(L), L, N) 9.02/3.16 U91'(tt, L, N) -> ISNATILISTKIND(L) 9.02/3.16 U92'(tt, L, N) -> U93'(isNat(N), L, N) 9.02/3.16 U92'(tt, L, N) -> ISNAT(N) 9.02/3.16 U93'(tt, L, N) -> U94'(isNatKind(N), L) 9.02/3.16 U93'(tt, L, N) -> ISNATKIND(N) 9.02/3.16 U94'(tt, L) -> LENGTH(L) 9.02/3.16 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 9.02/3.16 ISNAT(s(V1)) -> ISNATKIND(V1) 9.02/3.16 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.02/3.16 ISNATILIST(cons(V1, V2)) -> ISNATKIND(V1) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.02/3.16 ISNATKIND(length(V1)) -> U61'(isNatIListKind(V1)) 9.02/3.16 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.02/3.16 ISNATKIND(s(V1)) -> U71'(isNatKind(V1)) 9.02/3.16 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.02/3.16 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.02/3.16 ISNATLIST(cons(V1, V2)) -> ISNATKIND(V1) 9.02/3.16 LENGTH(cons(N, L)) -> U91'(isNatList(L), L, N) 9.02/3.16 LENGTH(cons(N, L)) -> ISNATLIST(L) 9.02/3.16 9.02/3.16 The collapsing dependency pairs are DP_c: 9.02/3.16 U94'(tt, L) -> L 9.02/3.16 9.02/3.16 9.02/3.16 The hidden terms of R are: 9.02/3.16 9.02/3.16 zeros 9.02/3.16 9.02/3.16 Every hiding context is built from:none 9.02/3.16 9.02/3.16 Hence, the new unhiding pairs DP_u are : 9.02/3.16 U94'(tt, L) -> U(L) 9.02/3.16 U(zeros) -> ZEROS 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (21) QCSDependencyGraphProof (EQUIVALENT) 9.02/3.16 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 5 SCCs with 24 less nodes. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (22) 9.02/3.16 Complex Obligation (AND) 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (23) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U51'_2} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATILISTKIND_1, ISNATKIND_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.02/3.16 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.02/3.16 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (24) QCSUsableRulesProof (EQUIVALENT) 9.02/3.16 The following rules are not useable [DA_EMMES] and can be deleted: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, x0) -> U22(isNatKind(x0), x0) 9.02/3.16 U22(tt, x0) -> U23(isNat(x0)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, x0, x1) -> U42(isNatKind(x0), x0, x1) 9.02/3.16 U42(tt, x0, x1) -> U43(isNatIListKind(x1), x0, x1) 9.02/3.16 U43(tt, x0, x1) -> U44(isNatIListKind(x1), x0, x1) 9.02/3.16 U44(tt, x0, x1) -> U45(isNat(x0), x1) 9.02/3.16 U45(tt, x0) -> U46(isNatIList(x0)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 9.02/3.16 U82(tt, x0, x1) -> U83(isNatIListKind(x1), x0, x1) 9.02/3.16 U83(tt, x0, x1) -> U84(isNatIListKind(x1), x0, x1) 9.02/3.16 U84(tt, x0, x1) -> U85(isNat(x0), x1) 9.02/3.16 U85(tt, x0) -> U86(isNatList(x0)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, x0, x1) -> U92(isNatIListKind(x0), x0, x1) 9.02/3.16 U92(tt, x0, x1) -> U93(isNat(x1), x0, x1) 9.02/3.16 U93(tt, x0, x1) -> U94(isNatKind(x1), x0) 9.02/3.16 U94(tt, x0) -> s(length(x0)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(x0)) -> U21(isNatKind(x0), x0) 9.02/3.16 isNatIList(cons(x0, x1)) -> U41(isNatKind(x0), x0, x1) 9.02/3.16 isNatList(cons(x0, x1)) -> U81(isNatKind(x0), x0, x1) 9.02/3.16 length(cons(x0, x1)) -> U91(isNatList(x1), x1, x0) 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (25) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {length_1, U61_1, s_1, U71_1, U52_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U51_2, U51'_2} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNatIListKind_1, ISNATILISTKIND_1, ISNATKIND_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.02/3.16 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.02/3.16 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U71(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (26) QCSDPMuMonotonicPoloProof (EQUIVALENT) 9.02/3.16 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. 9.02/3.16 9.02/3.16 Strictly oriented dependency pairs: 9.02/3.16 9.02/3.16 ISNATKIND(length(V1)) -> ISNATILISTKIND(V1) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> U51'(isNatKind(V1), V2) 9.02/3.16 U51'(tt, V2) -> ISNATILISTKIND(V2) 9.02/3.16 ISNATILISTKIND(cons(V1, V2)) -> ISNATKIND(V1) 9.02/3.16 9.02/3.16 Strictly oriented rules of the TRS R: 9.02/3.16 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 U71(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 9.02/3.16 Used ordering: POLO with Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 2 9.02/3.16 POL(ISNATILISTKIND(x_1)) = 1 + 2*x_1 9.02/3.16 POL(ISNATKIND(x_1)) = 2 + 2*x_1 9.02/3.16 POL(U51(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(U51'(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 9.02/3.16 POL(U52(x_1)) = x_1 9.02/3.16 POL(U61(x_1)) = x_1 9.02/3.16 POL(U71(x_1)) = 2*x_1 9.02/3.16 POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 9.02/3.16 POL(isNatIListKind(x_1)) = 1 + x_1 9.02/3.16 POL(isNatKind(x_1)) = 2*x_1 9.02/3.16 POL(length(x_1)) = 1 + x_1 9.02/3.16 POL(nil) = 2 9.02/3.16 POL(s(x_1)) = 2*x_1 9.02/3.16 POL(tt) = 2 9.02/3.16 POL(zeros) = 2 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (27) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {s_1, U71_1, U52_1, U61_1} are replacing on all positions. 9.02/3.16 The symbols in {isNatKind_1, ISNATKIND_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (28) QCSDPSubtermProof (EQUIVALENT) 9.02/3.16 We use the subterm processor [DA_EMMES]. 9.02/3.16 9.02/3.16 9.02/3.16 The following pairs can be oriented strictly and are deleted. 9.02/3.16 9.02/3.16 ISNATKIND(s(V1)) -> ISNATKIND(V1) 9.02/3.16 The remaining pairs can at least be oriented weakly. 9.02/3.16 none 9.02/3.16 Used ordering: Combined order from the following AFS and order. 9.02/3.16 ISNATKIND(x1) = x1 9.02/3.16 9.02/3.16 9.02/3.16 Subterm Order 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (29) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {s_1, U71_1, U52_1, U61_1} are replacing on all positions. 9.02/3.16 The symbols in {isNatKind_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 none 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (30) PIsEmptyProof (EQUIVALENT) 9.02/3.16 The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain. 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (31) 9.02/3.16 YES 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (32) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U22'_2, U21'_2} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNAT_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U22'(tt, V1) -> ISNAT(V1) 9.02/3.16 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 9.02/3.16 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (33) QCSDPSubtermProof (EQUIVALENT) 9.02/3.16 We use the subterm processor [DA_EMMES]. 9.02/3.16 9.02/3.16 9.02/3.16 The following pairs can be oriented strictly and are deleted. 9.02/3.16 9.02/3.16 ISNAT(s(V1)) -> U21'(isNatKind(V1), V1) 9.02/3.16 The remaining pairs can at least be oriented weakly. 9.02/3.16 9.02/3.16 U22'(tt, V1) -> ISNAT(V1) 9.02/3.16 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.02/3.16 Used ordering: Combined order from the following AFS and order. 9.02/3.16 ISNAT(x1) = x1 9.02/3.16 9.02/3.16 U22'(x1, x2) = x2 9.02/3.16 9.02/3.16 U21'(x1, x2) = x2 9.02/3.16 9.02/3.16 9.02/3.16 Subterm Order 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (34) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U22'_2, U21'_2} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNAT_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U22'(tt, V1) -> ISNAT(V1) 9.02/3.16 U21'(tt, V1) -> U22'(isNatKind(V1), V1) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (35) QCSDependencyGraphProof (EQUIVALENT) 9.02/3.16 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (36) 9.02/3.16 TRUE 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (37) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U85'_2, U84'_3, U81'_3, U82'_3, U83'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATLIST_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.02/3.16 U85'(tt, V2) -> ISNATLIST(V2) 9.02/3.16 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.02/3.16 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.02/3.16 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.02/3.16 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (38) QCSUsableRulesProof (EQUIVALENT) 9.02/3.16 The following rules are not useable [DA_EMMES] and can be deleted: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U41(tt, x0, x1) -> U42(isNatKind(x0), x0, x1) 9.02/3.16 U42(tt, x0, x1) -> U43(isNatIListKind(x1), x0, x1) 9.02/3.16 U43(tt, x0, x1) -> U44(isNatIListKind(x1), x0, x1) 9.02/3.16 U44(tt, x0, x1) -> U45(isNat(x0), x1) 9.02/3.16 U45(tt, x0) -> U46(isNatIList(x0)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 9.02/3.16 U82(tt, x0, x1) -> U83(isNatIListKind(x1), x0, x1) 9.02/3.16 U83(tt, x0, x1) -> U84(isNatIListKind(x1), x0, x1) 9.02/3.16 U84(tt, x0, x1) -> U85(isNat(x0), x1) 9.02/3.16 U85(tt, x0) -> U86(isNatList(x0)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, x0, x1) -> U92(isNatIListKind(x0), x0, x1) 9.02/3.16 U92(tt, x0, x1) -> U93(isNat(x1), x0, x1) 9.02/3.16 U93(tt, x0, x1) -> U94(isNatKind(x1), x0) 9.02/3.16 U94(tt, x0) -> s(length(x0)) 9.02/3.16 isNatIList(cons(x0, x1)) -> U41(isNatKind(x0), x0, x1) 9.02/3.16 isNatList(cons(x0, x1)) -> U81(isNatKind(x0), x0, x1) 9.02/3.16 length(cons(x0, x1)) -> U91(isNatList(x1), x1, x0) 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (39) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.02/3.16 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U85'_2, U84'_3, U81'_3, U82'_3, U83'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATLIST_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.02/3.16 U85'(tt, V2) -> ISNATLIST(V2) 9.02/3.16 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.02/3.16 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.02/3.16 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.02/3.16 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U71(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (40) QCSDPMuMonotonicPoloProof (EQUIVALENT) 9.02/3.16 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. 9.02/3.16 9.02/3.16 Strictly oriented dependency pairs: 9.02/3.16 9.02/3.16 U85'(tt, V2) -> ISNATLIST(V2) 9.02/3.16 U83'(tt, V1, V2) -> U84'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 9.02/3.16 Used ordering: POLO with Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 0 9.02/3.16 POL(ISNATLIST(x_1)) = 1 + 2*x_1 9.02/3.16 POL(U21(x_1, x_2)) = x_1 9.02/3.16 POL(U22(x_1, x_2)) = x_1 9.02/3.16 POL(U23(x_1)) = x_1 9.02/3.16 POL(U51(x_1, x_2)) = x_1 9.02/3.16 POL(U52(x_1)) = x_1 9.02/3.16 POL(U61(x_1)) = x_1 9.02/3.16 POL(U71(x_1)) = x_1 9.02/3.16 POL(U81'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.02/3.16 POL(U82'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.02/3.16 POL(U83'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.02/3.16 POL(U84'(x_1, x_2, x_3)) = x_1 + 2*x_3 9.02/3.16 POL(U85'(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 9.02/3.16 POL(isNat(x_1)) = 2 9.02/3.16 POL(isNatIListKind(x_1)) = 2 9.02/3.16 POL(isNatKind(x_1)) = 2 9.02/3.16 POL(length(x_1)) = 2 + 2*x_1 9.02/3.16 POL(nil) = 2 9.02/3.16 POL(s(x_1)) = x_1 9.02/3.16 POL(tt) = 2 9.02/3.16 POL(zeros) = 2 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (41) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.02/3.16 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U85'_2, U84'_3, U81'_3, U82'_3, U83'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATLIST_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U84'(tt, V1, V2) -> U85'(isNat(V1), V2) 9.02/3.16 ISNATLIST(cons(V1, V2)) -> U81'(isNatKind(V1), V1, V2) 9.02/3.16 U81'(tt, V1, V2) -> U82'(isNatKind(V1), V1, V2) 9.02/3.16 U82'(tt, V1, V2) -> U83'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U71(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (42) QCSDependencyGraphProof (EQUIVALENT) 9.02/3.16 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 4 less nodes. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (43) 9.02/3.16 TRUE 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (44) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1, LENGTH_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U91'_3, U92'_3, U93'_3, U94'_2} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 LENGTH(cons(N, L)) -> U91'(isNatList(L), L, N) 9.02/3.16 U91'(tt, L, N) -> U92'(isNatIListKind(L), L, N) 9.02/3.16 U92'(tt, L, N) -> U93'(isNat(N), L, N) 9.02/3.16 U93'(tt, L, N) -> U94'(isNatKind(N), L) 9.02/3.16 U94'(tt, L) -> LENGTH(L) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (45) QCSDPReductionPairProof (EQUIVALENT) 9.02/3.16 Using the order 9.02/3.16 9.02/3.16 Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 2 9.02/3.16 POL(LENGTH(x_1)) = 1 9.02/3.16 POL(U21(x_1, x_2)) = 2 9.02/3.16 POL(U22(x_1, x_2)) = 2 9.02/3.16 POL(U23(x_1)) = 2 9.02/3.16 POL(U51(x_1, x_2)) = 2 9.02/3.16 POL(U52(x_1)) = 2 9.02/3.16 POL(U61(x_1)) = 2 9.02/3.16 POL(U71(x_1)) = 2 9.02/3.16 POL(U81(x_1, x_2, x_3)) = 0 9.02/3.16 POL(U82(x_1, x_2, x_3)) = 0 9.02/3.16 POL(U83(x_1, x_2, x_3)) = 0 9.02/3.16 POL(U84(x_1, x_2, x_3)) = 0 9.02/3.16 POL(U85(x_1, x_2)) = 0 9.02/3.16 POL(U86(x_1)) = 2*x_1 9.02/3.16 POL(U91(x_1, x_2, x_3)) = x_1 9.02/3.16 POL(U91'(x_1, x_2, x_3)) = 1 + 2*x_1 9.02/3.16 POL(U92(x_1, x_2, x_3)) = 1 9.02/3.16 POL(U92'(x_1, x_2, x_3)) = 1 + 2*x_1 9.02/3.16 POL(U93(x_1, x_2, x_3)) = 1 9.02/3.16 POL(U93'(x_1, x_2, x_3)) = 1 + 2*x_1 9.02/3.16 POL(U94(x_1, x_2)) = 1 9.02/3.16 POL(U94'(x_1, x_2)) = 2 9.02/3.16 POL(cons(x_1, x_2)) = 0 9.02/3.16 POL(isNat(x_1)) = 2 9.02/3.16 POL(isNatIListKind(x_1)) = 2 9.02/3.16 POL(isNatKind(x_1)) = 2*x_1 9.02/3.16 POL(isNatList(x_1)) = 0 9.02/3.16 POL(length(x_1)) = 2 9.02/3.16 POL(nil) = 2 9.02/3.16 POL(s(x_1)) = 1 9.02/3.16 POL(tt) = 2 9.02/3.16 POL(zeros) = 0 9.02/3.16 9.02/3.16 9.02/3.16 the following usable rules 9.02/3.16 9.02/3.16 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 9.02/3.16 9.02/3.16 could all be oriented weakly. 9.02/3.16 9.02/3.16 Furthermore, the pairs 9.02/3.16 9.02/3.16 9.02/3.16 U93'(tt, L, N) -> U94'(isNatKind(N), L) 9.02/3.16 U94'(tt, L) -> LENGTH(L) 9.02/3.16 9.02/3.16 9.02/3.16 could be oriented strictly and thus removed by the CS-Reduction Pair Processor [LPAR08,DA_EMMES]. 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (46) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1, LENGTH_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U91'_3, U92'_3, U93'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 LENGTH(cons(N, L)) -> U91'(isNatList(L), L, N) 9.02/3.16 U91'(tt, L, N) -> U92'(isNatIListKind(L), L, N) 9.02/3.16 U92'(tt, L, N) -> U93'(isNat(N), L, N) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (47) QCSDependencyGraphProof (EQUIVALENT) 9.02/3.16 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 3 less nodes. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (48) 9.02/3.16 TRUE 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (49) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {U23_1, U46_1, U52_1, U61_1, U71_1, U86_1, s_1, length_1} are replacing on all positions. 9.02/3.16 For all symbols f in {cons_2, U21_2, U22_2, U41_3, U42_3, U43_3, U44_3, U45_2, U51_2, U81_3, U82_3, U83_3, U84_3, U85_2, U91_3, U92_3, U93_3, U94_2, U45'_2, U44'_3, U41'_3, U42'_3, U43'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNatKind_1, isNat_1, isNatIListKind_1, isNatIList_1, isNatList_1, ISNATILIST_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.02/3.16 U45'(tt, V2) -> ISNATILIST(V2) 9.02/3.16 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.02/3.16 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.02/3.16 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.02/3.16 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 U41(tt, V1, V2) -> U42(isNatKind(V1), V1, V2) 9.02/3.16 U42(tt, V1, V2) -> U43(isNatIListKind(V2), V1, V2) 9.02/3.16 U43(tt, V1, V2) -> U44(isNatIListKind(V2), V1, V2) 9.02/3.16 U44(tt, V1, V2) -> U45(isNat(V1), V2) 9.02/3.16 U45(tt, V2) -> U46(isNatIList(V2)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U71(tt) -> tt 9.02/3.16 U81(tt, V1, V2) -> U82(isNatKind(V1), V1, V2) 9.02/3.16 U82(tt, V1, V2) -> U83(isNatIListKind(V2), V1, V2) 9.02/3.16 U83(tt, V1, V2) -> U84(isNatIListKind(V2), V1, V2) 9.02/3.16 U84(tt, V1, V2) -> U85(isNat(V1), V2) 9.02/3.16 U85(tt, V2) -> U86(isNatList(V2)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, L, N) -> U92(isNatIListKind(L), L, N) 9.02/3.16 U92(tt, L, N) -> U93(isNat(N), L, N) 9.02/3.16 U93(tt, L, N) -> U94(isNatKind(N), L) 9.02/3.16 U94(tt, L) -> s(length(L)) 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatIList(cons(V1, V2)) -> U41(isNatKind(V1), V1, V2) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 isNatList(cons(V1, V2)) -> U81(isNatKind(V1), V1, V2) 9.02/3.16 length(cons(N, L)) -> U91(isNatList(L), L, N) 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (50) QCSUsableRulesProof (EQUIVALENT) 9.02/3.16 The following rules are not useable [DA_EMMES] and can be deleted: 9.02/3.16 9.02/3.16 zeros -> cons(0, zeros) 9.02/3.16 U41(tt, x0, x1) -> U42(isNatKind(x0), x0, x1) 9.02/3.16 U42(tt, x0, x1) -> U43(isNatIListKind(x1), x0, x1) 9.02/3.16 U43(tt, x0, x1) -> U44(isNatIListKind(x1), x0, x1) 9.02/3.16 U44(tt, x0, x1) -> U45(isNat(x0), x1) 9.02/3.16 U45(tt, x0) -> U46(isNatIList(x0)) 9.02/3.16 U46(tt) -> tt 9.02/3.16 U81(tt, x0, x1) -> U82(isNatKind(x0), x0, x1) 9.02/3.16 U82(tt, x0, x1) -> U83(isNatIListKind(x1), x0, x1) 9.02/3.16 U83(tt, x0, x1) -> U84(isNatIListKind(x1), x0, x1) 9.02/3.16 U84(tt, x0, x1) -> U85(isNat(x0), x1) 9.02/3.16 U85(tt, x0) -> U86(isNatList(x0)) 9.02/3.16 U86(tt) -> tt 9.02/3.16 U91(tt, x0, x1) -> U92(isNatIListKind(x0), x0, x1) 9.02/3.16 U92(tt, x0, x1) -> U93(isNat(x1), x0, x1) 9.02/3.16 U93(tt, x0, x1) -> U94(isNatKind(x1), x0) 9.02/3.16 U94(tt, x0) -> s(length(x0)) 9.02/3.16 isNatIList(cons(x0, x1)) -> U41(isNatKind(x0), x0, x1) 9.02/3.16 isNatList(cons(x0, x1)) -> U81(isNatKind(x0), x0, x1) 9.02/3.16 length(cons(x0, x1)) -> U91(isNatList(x1), x1, x0) 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (51) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.02/3.16 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U45'_2, U44'_3, U41'_3, U42'_3, U43'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATILIST_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.02/3.16 U45'(tt, V2) -> ISNATILIST(V2) 9.02/3.16 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.02/3.16 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.02/3.16 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.02/3.16 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U71(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (52) QCSDPMuMonotonicPoloProof (EQUIVALENT) 9.02/3.16 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. 9.02/3.16 9.02/3.16 Strictly oriented dependency pairs: 9.02/3.16 9.02/3.16 U45'(tt, V2) -> ISNATILIST(V2) 9.02/3.16 U43'(tt, V1, V2) -> U44'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 9.02/3.16 Used ordering: POLO with Polynomial interpretation [POLO]: 9.02/3.16 9.02/3.16 POL(0) = 0 9.02/3.16 POL(ISNATILIST(x_1)) = 1 + 2*x_1 9.02/3.16 POL(U21(x_1, x_2)) = x_1 9.02/3.16 POL(U22(x_1, x_2)) = x_1 9.02/3.16 POL(U23(x_1)) = x_1 9.02/3.16 POL(U41'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.02/3.16 POL(U42'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.02/3.16 POL(U43'(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_3 9.02/3.16 POL(U44'(x_1, x_2, x_3)) = x_1 + 2*x_3 9.02/3.16 POL(U45'(x_1, x_2)) = x_1 + 2*x_2 9.02/3.16 POL(U51(x_1, x_2)) = x_1 9.02/3.16 POL(U52(x_1)) = x_1 9.02/3.16 POL(U61(x_1)) = x_1 9.02/3.16 POL(U71(x_1)) = x_1 9.02/3.16 POL(cons(x_1, x_2)) = 2 + x_1 + 2*x_2 9.02/3.16 POL(isNat(x_1)) = 2 9.02/3.16 POL(isNatIListKind(x_1)) = 2 9.02/3.16 POL(isNatKind(x_1)) = 2 9.02/3.16 POL(length(x_1)) = 2 + 2*x_1 9.02/3.16 POL(nil) = 2 9.02/3.16 POL(s(x_1)) = x_1 9.02/3.16 POL(tt) = 2 9.02/3.16 POL(zeros) = 2 9.02/3.16 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (53) 9.02/3.16 Obligation: 9.02/3.16 Q-restricted context-sensitive dependency pair problem: 9.02/3.16 The symbols in {s_1, length_1, U61_1, U71_1, U52_1, U23_1} are replacing on all positions. 9.02/3.16 For all symbols f in {U21_2, cons_2, U51_2, U22_2, U45'_2, U44'_3, U41'_3, U42'_3, U43'_3} we have mu(f) = {1}. 9.02/3.16 The symbols in {isNat_1, isNatKind_1, isNatIListKind_1, ISNATILIST_1} are not replacing on any position. 9.02/3.16 9.02/3.16 The TRS P consists of the following rules: 9.02/3.16 9.02/3.16 U44'(tt, V1, V2) -> U45'(isNat(V1), V2) 9.02/3.16 ISNATILIST(cons(V1, V2)) -> U41'(isNatKind(V1), V1, V2) 9.02/3.16 U41'(tt, V1, V2) -> U42'(isNatKind(V1), V1, V2) 9.02/3.16 U42'(tt, V1, V2) -> U43'(isNatIListKind(V2), V1, V2) 9.02/3.16 9.02/3.16 The TRS R consists of the following rules: 9.02/3.16 9.02/3.16 isNat(0) -> tt 9.02/3.16 isNat(s(V1)) -> U21(isNatKind(V1), V1) 9.02/3.16 isNatKind(0) -> tt 9.02/3.16 isNatKind(length(V1)) -> U61(isNatIListKind(V1)) 9.02/3.16 isNatIListKind(nil) -> tt 9.02/3.16 isNatIListKind(zeros) -> tt 9.02/3.16 isNatIListKind(cons(V1, V2)) -> U51(isNatKind(V1), V2) 9.02/3.16 isNatKind(s(V1)) -> U71(isNatKind(V1)) 9.02/3.16 U71(tt) -> tt 9.02/3.16 U51(tt, V2) -> U52(isNatIListKind(V2)) 9.02/3.16 U52(tt) -> tt 9.02/3.16 U61(tt) -> tt 9.02/3.16 U21(tt, V1) -> U22(isNatKind(V1), V1) 9.02/3.16 U22(tt, V1) -> U23(isNat(V1)) 9.02/3.16 U23(tt) -> tt 9.02/3.16 9.02/3.16 Q is empty. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (54) QCSDependencyGraphProof (EQUIVALENT) 9.02/3.16 The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 4 less nodes. 9.02/3.16 9.02/3.16 ---------------------------------------- 9.02/3.16 9.02/3.16 (55) 9.02/3.16 TRUE 9.02/3.18 EOF