/export/starexec/sandbox2/solver/bin/starexec_run_standard /export/starexec/sandbox2/benchmark/theBenchmark.xml /export/starexec/sandbox2/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml # AProVE Commit ID: c69e44bd14796315568835c1ffa2502984884775 mhark 20210624 unpublished Termination of the given CSR could be proven: (0) CSR (1) CSRRRRProof [EQUIVALENT, 150 ms] (2) CSR (3) CSRRRRProof [EQUIVALENT, 40 ms] (4) CSR (5) CSRRRRProof [EQUIVALENT, 2 ms] (6) CSR (7) CSRRRRProof [EQUIVALENT, 0 ms] (8) CSR (9) CSRRRRProof [EQUIVALENT, 29 ms] (10) CSR (11) CSRRRRProof [EQUIVALENT, 25 ms] (12) CSR (13) CSRRRRProof [EQUIVALENT, 33 ms] (14) CSR (15) Incomplete Giesl Middeldorp-Transformation [SOUND, 0 ms] (16) QTRS (17) DependencyPairsProof [EQUIVALENT, 0 ms] (18) QDP (19) DependencyGraphProof [EQUIVALENT, 0 ms] (20) QDP (21) QDPOrderProof [EQUIVALENT, 166 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) AND (25) QDP (26) QDPOrderProof [EQUIVALENT, 90 ms] (27) QDP (28) QDPOrderProof [EQUIVALENT, 83 ms] (29) QDP (30) QDPOrderProof [EQUIVALENT, 95 ms] (31) QDP (32) QDPOrderProof [EQUIVALENT, 93 ms] (33) QDP (34) QDPOrderProof [EQUIVALENT, 142 ms] (35) QDP (36) QDPOrderProof [EQUIVALENT, 80 ms] (37) QDP (38) DependencyGraphProof [EQUIVALENT, 0 ms] (39) QDP (40) QDPOrderProof [EQUIVALENT, 94 ms] (41) QDP (42) DependencyGraphProof [EQUIVALENT, 0 ms] (43) AND (44) QDP (45) UsableRulesProof [EQUIVALENT, 0 ms] (46) QDP (47) QDPSizeChangeProof [EQUIVALENT, 0 ms] (48) YES (49) QDP (50) QDPSizeChangeProof [EQUIVALENT, 0 ms] (51) YES (52) QDP (53) QDPOrderProof [EQUIVALENT, 110 ms] (54) QDP (55) QDPOrderProof [EQUIVALENT, 86 ms] (56) QDP (57) QDPOrderProof [EQUIVALENT, 59 ms] (58) QDP (59) QDPOrderProof [EQUIVALENT, 46 ms] (60) QDP (61) DependencyGraphProof [EQUIVALENT, 0 ms] (62) AND (63) QDP (64) QDPSizeChangeProof [EQUIVALENT, 0 ms] (65) YES (66) QDP (67) QDPSizeChangeProof [EQUIVALENT, 0 ms] (68) YES (69) QDP (70) QDPSizeChangeProof [EQUIVALENT, 0 ms] (71) YES ---------------------------------------- (0) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt, V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(zeros) -> tt isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(nil) -> 0 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U32: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (1) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt, V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(zeros) -> tt isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(nil) -> 0 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U32: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 POL(U12(x_1)) = 2*x_1 POL(U21(x_1, x_2)) = 2*x_1 POL(U22(x_1)) = x_1 POL(U31(x_1, x_2)) = 2*x_1 POL(U32(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = 2*x_1 POL(U42(x_1, x_2)) = x_1 POL(U43(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = 2*x_1 POL(U52(x_1, x_2)) = x_1 POL(U53(x_1)) = x_1 POL(U61(x_1, x_2)) = 2*x_1 + 2*x_2 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = 0 POL(isNatIList(x_1)) = 0 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = 0 POL(length(x_1)) = x_1 POL(nil) = 2 POL(s(x_1)) = 2*x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: length(nil) -> 0 ---------------------------------------- (2) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt, V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(zeros) -> tt isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U32: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (3) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U31(tt, V) -> U32(isNatList(V)) U32(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(zeros) -> tt isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U32: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 POL(U12(x_1)) = x_1 POL(U21(x_1, x_2)) = 2*x_1 POL(U22(x_1)) = x_1 POL(U31(x_1, x_2)) = 1 + 2*x_1 POL(U32(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = 1 + 2*x_1 POL(U42(x_1, x_2)) = 1 + 2*x_1 POL(U43(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = 2*x_1 POL(U52(x_1, x_2)) = x_1 POL(U53(x_1)) = x_1 POL(U61(x_1, x_2)) = 2*x_1 + 2*x_2 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(isNat(x_1)) = 0 POL(isNatIList(x_1)) = 1 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = 0 POL(length(x_1)) = 2*x_1 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U31(tt, V) -> U32(isNatList(V)) isNatIList(zeros) -> tt ---------------------------------------- (4) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U32(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U32: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (5) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U32(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U32: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 POL(U12(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 POL(U22(x_1)) = x_1 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 POL(U32(x_1)) = 1 + x_1 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U42(x_1, x_2)) = 1 + x_1 + x_2 POL(U43(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = x_1 POL(U52(x_1, x_2)) = x_1 POL(U53(x_1)) = x_1 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 POL(and(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(isNat(x_1)) = 0 POL(isNatIList(x_1)) = 1 + x_1 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = 0 POL(length(x_1)) = 1 + x_1 POL(nil) = 1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U32(tt) -> tt ---------------------------------------- (6) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (7) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(V) -> U31(isNatIListKind(V), V) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U31: {1} U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 POL(U12(x_1)) = x_1 POL(U21(x_1, x_2)) = x_1 POL(U22(x_1)) = x_1 POL(U31(x_1, x_2)) = x_1 + x_2 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 POL(U42(x_1, x_2)) = 1 + x_1 + x_2 POL(U43(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = x_1 POL(U52(x_1, x_2)) = x_1 POL(U53(x_1)) = x_1 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 POL(and(x_1, x_2)) = x_1 + x_2 POL(cons(x_1, x_2)) = x_1 + x_2 POL(isNat(x_1)) = 0 POL(isNatIList(x_1)) = 1 + x_1 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = 0 POL(length(x_1)) = 1 + x_1 POL(nil) = 1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 1 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isNatIList(V) -> U31(isNatIListKind(V), V) ---------------------------------------- (8) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (9) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set U12: {1} isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 POL(U12(x_1)) = 1 + x_1 POL(U21(x_1, x_2)) = 2*x_1 + x_2 POL(U22(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 POL(U42(x_1, x_2)) = x_1 + 2*x_2 POL(U43(x_1)) = x_1 POL(U51(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 POL(U52(x_1, x_2)) = x_1 + 2*x_2 POL(U53(x_1)) = x_1 POL(U61(x_1, x_2)) = 2 + x_1 + 2*x_2 POL(and(x_1, x_2)) = x_1 + 2*x_2 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = 2*x_1 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = 2*x_1 POL(length(x_1)) = 2 + 2*x_1 POL(nil) = 0 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U11(tt, V1) -> U12(isNatList(V1)) U12(tt) -> tt ---------------------------------------- (10) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (11) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(nil) -> tt isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = x_1 POL(U21(x_1, x_2)) = x_1 POL(U22(x_1)) = 2*x_1 POL(U41(x_1, x_2, x_3)) = x_1 POL(U42(x_1, x_2)) = x_1 POL(U43(x_1)) = 2*x_1 POL(U51(x_1, x_2, x_3)) = x_1 + 2*x_3 POL(U52(x_1, x_2)) = x_1 + 2*x_2 POL(U53(x_1)) = 2*x_1 POL(U61(x_1, x_2)) = 2*x_1 + 2*x_2 POL(and(x_1, x_2)) = x_1 + 2*x_2 POL(cons(x_1, x_2)) = x_1 + 2*x_2 POL(isNat(x_1)) = 0 POL(isNatIList(x_1)) = 0 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 2*x_1 POL(nil) = 1 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isNatList(nil) -> tt ---------------------------------------- (12) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (13) CSRRRRProof (EQUIVALENT) The following CSR is given: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(length(V1)) -> U11(isNatIListKind(V1), V1) isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set U11: {1} tt: empty set isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set Used ordering: Polynomial interpretation [POLO]: POL(0) = 0 POL(U11(x_1, x_2)) = 2*x_1 POL(U21(x_1, x_2)) = 2*x_1 + x_2 POL(U22(x_1)) = x_1 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U42(x_1, x_2)) = x_1 + 2*x_2 POL(U43(x_1)) = 2*x_1 POL(U51(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 POL(U52(x_1, x_2)) = x_1 + 2*x_2 POL(U53(x_1)) = 2*x_1 POL(U61(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 POL(and(x_1, x_2)) = x_1 + 2*x_2 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 POL(isNat(x_1)) = x_1 POL(isNatIList(x_1)) = x_1 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = x_1 POL(length(x_1)) = 1 + 2*x_1 POL(nil) = 2 POL(s(x_1)) = x_1 POL(tt) = 0 POL(zeros) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: isNat(length(V1)) -> U11(isNatIListKind(V1), V1) ---------------------------------------- (14) Obligation: Context-sensitive rewrite system: The TRS R consists of the following rules: zeros -> cons(0, zeros) U21(tt, V1) -> U22(isNat(V1)) U22(tt) -> tt U41(tt, V1, V2) -> U42(isNat(V1), V2) U42(tt, V2) -> U43(isNatIList(V2)) U43(tt) -> tt U51(tt, V1, V2) -> U52(isNat(V1), V2) U52(tt, V2) -> U53(isNatList(V2)) U53(tt) -> tt U61(tt, L) -> s(length(L)) and(tt, X) -> X isNat(0) -> tt isNat(s(V1)) -> U21(isNatKind(V1), V1) isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) isNatIListKind(nil) -> tt isNatIListKind(zeros) -> tt isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) isNatKind(0) -> tt isNatKind(length(V1)) -> isNatIListKind(V1) isNatKind(s(V1)) -> isNatKind(V1) isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The replacement map contains the following entries: zeros: empty set cons: {1} 0: empty set tt: empty set isNatList: empty set U21: {1} U22: {1} isNat: empty set U41: {1} U42: {1} U43: {1} isNatIList: empty set U51: {1} U52: {1} U53: {1} U61: {1} s: {1} length: {1} and: {1} isNatIListKind: empty set isNatKind: empty set nil: empty set ---------------------------------------- (15) Incomplete Giesl Middeldorp-Transformation (SOUND) We applied the Incomplete Giesl Middeldorp transformation [CS_Term] to transform the context-sensitive TRS to a usual TRS. ---------------------------------------- (16) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. ---------------------------------------- (17) DependencyPairsProof (EQUIVALENT) Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. ---------------------------------------- (18) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(zeros) -> ZEROSACTIVE MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> U22ACTIVE(mark(x1)) MARK(U22(x1)) -> MARK(x1) MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) MARK(U41(x1, x2, x3)) -> MARK(x1) MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) MARK(U42(x1, x2)) -> MARK(x1) MARK(U43(x1)) -> U43ACTIVE(mark(x1)) MARK(U43(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> U53ACTIVE(mark(x1)) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) MARK(length(x1)) -> MARK(x1) MARK(cons(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) U21ACTIVE(tt, V1) -> U22ACTIVE(isNatActive(V1)) U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) U42ACTIVE(tt, V2) -> U43ACTIVE(isNatIListActive(V2)) U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) U52ACTIVE(tt, V2) -> U53ACTIVE(isNatListActive(V2)) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) ANDACTIVE(tt, X) -> MARK(X) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (19) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. ---------------------------------------- (20) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U41(x1, x2, x3)) -> MARK(x1) MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) MARK(U42(x1, x2)) -> MARK(x1) MARK(U43(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(cons(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (21) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) MARK(U41(x1, x2, x3)) -> MARK(x1) MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) MARK(U42(x1, x2)) -> MARK(x1) MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(MARK(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(mark(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(tt) = [[0], [0]] >>> <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U41ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U42ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATILISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(U42(x_1, x_2)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIList(x_1)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U42Active(x_1, x_2)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: mark(zeros) -> zerosActive mark(U21(x1, x2)) -> U21Active(mark(x1), x2) mark(U22(x1)) -> U22Active(mark(x1)) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) mark(U43(x1)) -> U43Active(mark(x1)) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) mark(U53(x1)) -> U53Active(mark(x1)) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(tt, X) -> mark(X) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) mark(isNat(x1)) -> isNatActive(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) mark(isNatList(x1)) -> isNatListActive(x1) mark(length(x1)) -> lengthActive(mark(x1)) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil isNatKindActive(x1) -> isNatKind(x1) isNatKindActive(0) -> tt isNatActive(x1) -> isNat(x1) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) andActive(x1, x2) -> and(x1, x2) isNatListActive(x1) -> isNatList(x1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U22Active(x1) -> U22(x1) U22Active(tt) -> tt U21Active(x1, x2) -> U21(x1, x2) U41Active(x1, x2, x3) -> U41(x1, x2, x3) U42Active(x1, x2) -> U42(x1, x2) U43Active(x1) -> U43(x1) U43Active(tt) -> tt U51Active(x1, x2, x3) -> U51(x1, x2, x3) U52Active(x1, x2) -> U52(x1, x2) U53Active(x1) -> U53(x1) U53Active(tt) -> tt U61Active(x1, x2) -> U61(x1, x2) isNatIListKindActive(x1) -> isNatIListKind(x1) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt U21Active(tt, V1) -> U22Active(isNatActive(V1)) isNatIListActive(x1) -> isNatIList(x1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) lengthActive(x1) -> length(x1) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) U61Active(tt, L) -> s(lengthActive(mark(L))) zerosActive -> zeros zerosActive -> cons(0, zeros) ---------------------------------------- (22) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U43(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(cons(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (23) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes. ---------------------------------------- (24) Complex Obligation (AND) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U43(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(cons(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (26) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U21ACTIVE(x_1, x_2)) = [[1]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(tt) = [[0], [1]] >>> <<< POL(ISNATACTIVE(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[1]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(MARK(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(mark(x_1)) = [[1], [1]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[1]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[1]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [1]] + [[0, 1], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 1]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[1]] + [[0, 0]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [1]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[1], [1]] + [[0, 1], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[1], [1]] + [[0, 1], [0, 0]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: isNatKindActive(x1) -> isNatKind(x1) isNatKindActive(0) -> tt mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(tt, X) -> mark(X) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) mark(zeros) -> zerosActive mark(U21(x1, x2)) -> U21Active(mark(x1), x2) mark(U22(x1)) -> U22Active(mark(x1)) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) mark(U43(x1)) -> U43Active(mark(x1)) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) mark(U53(x1)) -> U53Active(mark(x1)) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) mark(isNat(x1)) -> isNatActive(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) mark(isNatList(x1)) -> isNatListActive(x1) mark(length(x1)) -> lengthActive(mark(x1)) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil isNatActive(x1) -> isNat(x1) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) andActive(x1, x2) -> and(x1, x2) isNatListActive(x1) -> isNatList(x1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U22Active(x1) -> U22(x1) U22Active(tt) -> tt U21Active(x1, x2) -> U21(x1, x2) U41Active(x1, x2, x3) -> U41(x1, x2, x3) U42Active(x1, x2) -> U42(x1, x2) U43Active(x1) -> U43(x1) U43Active(tt) -> tt U51Active(x1, x2, x3) -> U51(x1, x2, x3) U52Active(x1, x2) -> U52(x1, x2) U53Active(x1) -> U53(x1) U53Active(tt) -> tt U61Active(x1, x2) -> U61(x1, x2) isNatIListKindActive(x1) -> isNatIListKind(x1) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt U21Active(tt, V1) -> U22Active(isNatActive(V1)) isNatIListActive(x1) -> isNatIList(x1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) lengthActive(x1) -> length(x1) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) U61Active(tt, L) -> s(lengthActive(mark(L))) zerosActive -> zeros zerosActive -> cons(0, zeros) ---------------------------------------- (27) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U43(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(cons(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (28) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(cons(x1, x2)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(tt) = [[0], [1]] >>> <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(MARK(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(mark(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[0, 1], [1, 1]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[1], [1]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [1]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 1]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 1]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[0, 1], [0, 1]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[1], [1]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[1], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[1], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[1], [1]] + [[1, 1], [0, 1]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (29) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U43(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (30) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U43(x1)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(tt) = [[0], [1]] >>> <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[1], [1]] + [[1, 1], [1, 1]] * x_1 + [[0, 1], [0, 1]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 >>> <<< POL(MARK(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(mark(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U43(x_1)) = [[1], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [1]] + [[0, 1], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 1]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[1], [0]] + [[1, 0], [1, 1]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (31) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (32) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(tt) = [[0], [1]] >>> <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(MARK(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(mark(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 + [[0, 1], [1, 0]] * x_2 + [[0, 0], [0, 1]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[0, 0], [1, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 0], [0, 1]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[1], [1]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[1], [0]] + [[0, 1], [1, 1]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[1], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 1], [0, 1]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 1], [0, 1]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [1]] + [[0, 1], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 + [[0, 0], [0, 1]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[1], [1]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[1], [1]] + [[1, 1], [0, 1]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [1]] + [[1, 1], [1, 0]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (33) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(length(x1)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (34) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) MARK(length(x1)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(tt) = [[0], [1]] >>> <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(MARK(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(mark(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 0], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 0], [1, 1]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[0, 0], [1, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [1, 1]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[1], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[1], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [1]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [1]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (35) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (36) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) MARK(U61(x1, x2)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(tt) = [[0], [1]] >>> <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(MARK(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(mark(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 1], [0, 1]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[1], [0]] + [[1, 1], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(U61ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(LENGTHACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [1]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[1], [0]] + [[0, 0], [1, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 1], [0, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [1, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 1], [0, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [1, 1]] * x_2 + [[1, 0], [0, 1]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61Active(x_1, x_2)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 + [[0, 1], [0, 0]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [0]] + [[1, 1], [0, 0]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (37) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) U61ACTIVE(tt, L) -> MARK(L) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (38) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. ---------------------------------------- (39) Obligation: Q DP problem: The TRS P consists of the following rules: ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (40) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(ISNATACTIVE(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U21ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(tt) = [[1], [1]] >>> <<< POL(ISNATKINDACTIVE(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(ISNATILISTKINDACTIVE(x_1)) = [[0]] + [[1, 1]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [1]] + [[1, 1], [0, 0]] * x_1 + [[1, 1], [1, 0]] * x_2 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(MARK(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[0, 0], [1, 0]] * x_2 >>> <<< POL(mark(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[0, 0], [1, 0]] * x_2 + [[0, 0], [1, 1]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 + [[1, 0]] * x_3 >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(isNatIListKindActive(x_1)) = [[1], [1]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[1], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 1]] * x_2 + [[0, 0], [1, 1]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [1, 1]] * x_2 + [[0, 0], [1, 1]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIList(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[1], [1]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (41) Obligation: Q DP problem: The TRS P consists of the following rules: ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) ANDACTIVE(tt, X) -> MARK(X) MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(isNat(x1)) -> ISNATACTIVE(x1) MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (42) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 3 SCCs with 8 less nodes. ---------------------------------------- (43) Complex Obligation (AND) ---------------------------------------- (44) Obligation: Q DP problem: The TRS P consists of the following rules: ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (45) UsableRulesProof (EQUIVALENT) We can use the usable rules and reduction pair processor [LPAR04] with the Ce-compatible extension of the polynomial order that maps every function symbol to the sum of its arguments. Then, we can delete all non-usable rules [FROCOS05] from R. ---------------------------------------- (46) Obligation: Q DP problem: The TRS P consists of the following rules: ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (47) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) The graph contains the following edges 1 > 1 ---------------------------------------- (48) YES ---------------------------------------- (49) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (50) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) The graph contains the following edges 1 > 2 *U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) The graph contains the following edges 2 >= 1 ---------------------------------------- (51) YES ---------------------------------------- (52) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (53) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U21(x1, x2)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(MARK(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(U21(x_1, x_2)) = [[0], [1]] + [[0, 1], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(mark(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(tt) = [[0], [0]] >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 1], [0, 1]] * x_2 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(s(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[0, 0], [1, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 + [[0, 0], [1, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [1]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [1, 0]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[1], [0]] + [[0, 0], [1, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIList(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[1], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (54) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U22(x1)) -> MARK(x1) MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (55) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U22(x1)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(MARK(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(U22(x_1)) = [[0], [1]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[1, 0]] * x_3 >>> <<< POL(mark(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(tt) = [[1], [1]] >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(isNatKindActive(x_1)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[0, 1], [1, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(s(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[1, 0], [0, 0]] * x_1 + [[1, 1], [1, 0]] * x_2 + [[1, 0], [0, 0]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [1, 0]] * x_2 + [[0, 0], [0, 0]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 0], [1, 0]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIListKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIList(x_1)) = [[1], [1]] + [[0, 0], [1, 1]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [1]] + [[0, 0], [1, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[1], [1]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (56) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (57) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) MARK(U52(x1, x2)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(MARK(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [0]] + [[1, 1], [0, 1]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[0, 1], [1, 1]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[1, 0]] * x_3 >>> <<< POL(mark(x_1)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(tt) = [[1], [1]] >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[1, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[1, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [1, 0]] * x_2 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(U52(x_1, x_2)) = [[0], [1]] + [[0, 1], [0, 1]] * x_1 + [[1, 1], [1, 0]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(s(x_1)) = [[0], [0]] + [[0, 0], [1, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 1], [0, 1]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 1]] * x_2 + [[0, 1], [0, 1]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[1], [0]] + [[1, 0], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[0, 1], [0, 1]] * x_3 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [1, 0]] * x_2 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 + [[0, 0], [1, 0]] * x_2 >>> <<< POL(isNatIListKindActive(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIList(x_1)) = [[1], [0]] + [[0, 1], [0, 0]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[1], [1]] + [[0, 1], [0, 1]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (58) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U51(x1, x2, x3)) -> MARK(x1) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (59) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) MARK(U51(x1, x2, x3)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Matrix interpretation [MATRO] to (N^2, +, *, >=, >) : <<< POL(MARK(x_1)) = [[0]] + [[0, 1]] * x_1 >>> <<< POL(U51(x_1, x_2, x_3)) = [[0], [1]] + [[1, 1], [0, 1]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [0, 1]] * x_3 >>> <<< POL(U51ACTIVE(x_1, x_2, x_3)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 + [[0, 0]] * x_3 >>> <<< POL(mark(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(tt) = [[0], [0]] >>> <<< POL(U52ACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 0]] * x_2 >>> <<< POL(isNatActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ISNATLISTACTIVE(x_1)) = [[0]] + [[0, 0]] * x_1 >>> <<< POL(cons(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 0], [0, 0]] * x_2 >>> <<< POL(andActive(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatKindActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIListKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(ANDACTIVE(x_1, x_2)) = [[0]] + [[0, 0]] * x_1 + [[0, 1]] * x_2 >>> <<< POL(U53(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(and(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 1]] * x_1 + [[0, 0], [0, 1]] * x_2 >>> <<< POL(s(x_1)) = [[1], [0]] + [[0, 0], [0, 1]] * x_1 >>> <<< POL(zeros) = [[0], [0]] >>> <<< POL(zerosActive) = [[0], [0]] >>> <<< POL(U21(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U21Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U22(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(U22Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U41(x_1, x_2, x_3)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[0, 0], [0, 1]] * x_3 >>> <<< POL(U41Active(x_1, x_2, x_3)) = [[1], [0]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [0, 0]] * x_2 + [[0, 0], [0, 1]] * x_3 >>> <<< POL(U42(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U42Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U43(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U43Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U51Active(x_1, x_2, x_3)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[1, 1], [1, 1]] * x_2 + [[1, 1], [0, 1]] * x_3 >>> <<< POL(U52(x_1, x_2)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U52Active(x_1, x_2)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U53Active(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(U61(x_1, x_2)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(U61Active(x_1, x_2)) = [[0], [1]] + [[0, 0], [0, 0]] * x_1 + [[0, 0], [0, 0]] * x_2 >>> <<< POL(isNatIListKindActive(x_1)) = [[1], [1]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatKind(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(length(x_1)) = [[0], [0]] + [[1, 1], [1, 1]] * x_1 >>> <<< POL(isNat(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(isNatIList(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(isNatIListActive(x_1)) = [[0], [0]] + [[1, 0], [1, 0]] * x_1 >>> <<< POL(isNatList(x_1)) = [[0], [0]] + [[1, 0], [0, 1]] * x_1 >>> <<< POL(isNatListActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(lengthActive(x_1)) = [[0], [0]] + [[0, 0], [0, 0]] * x_1 >>> <<< POL(0) = [[0], [0]] >>> <<< POL(nil) = [[0], [0]] >>> The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (60) Obligation: Q DP problem: The TRS P consists of the following rules: U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) ANDACTIVE(tt, X) -> MARK(X) MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) MARK(and(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (61) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node. ---------------------------------------- (62) Complex Obligation (AND) ---------------------------------------- (63) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U53(x1)) -> MARK(x1) MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) ANDACTIVE(tt, X) -> MARK(X) MARK(and(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (64) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) The graph contains the following edges 1 > 2 *ANDACTIVE(tt, X) -> MARK(X) The graph contains the following edges 2 >= 1 *MARK(U53(x1)) -> MARK(x1) The graph contains the following edges 1 > 1 *MARK(and(x1, x2)) -> MARK(x1) The graph contains the following edges 1 > 1 *MARK(s(x1)) -> MARK(x1) The graph contains the following edges 1 > 1 ---------------------------------------- (65) YES ---------------------------------------- (66) Obligation: Q DP problem: The TRS P consists of the following rules: U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (67) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) The graph contains the following edges 1 > 2, 1 > 3 *U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) The graph contains the following edges 3 >= 2 *U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) The graph contains the following edges 2 >= 1 ---------------------------------------- (68) YES ---------------------------------------- (69) Obligation: Q DP problem: The TRS P consists of the following rules: U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) The TRS R consists of the following rules: mark(zeros) -> zerosActive zerosActive -> zeros mark(U21(x1, x2)) -> U21Active(mark(x1), x2) U21Active(x1, x2) -> U21(x1, x2) mark(U22(x1)) -> U22Active(mark(x1)) U22Active(x1) -> U22(x1) mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) U41Active(x1, x2, x3) -> U41(x1, x2, x3) mark(U42(x1, x2)) -> U42Active(mark(x1), x2) U42Active(x1, x2) -> U42(x1, x2) mark(U43(x1)) -> U43Active(mark(x1)) U43Active(x1) -> U43(x1) mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) U51Active(x1, x2, x3) -> U51(x1, x2, x3) mark(U52(x1, x2)) -> U52Active(mark(x1), x2) U52Active(x1, x2) -> U52(x1, x2) mark(U53(x1)) -> U53Active(mark(x1)) U53Active(x1) -> U53(x1) mark(U61(x1, x2)) -> U61Active(mark(x1), x2) U61Active(x1, x2) -> U61(x1, x2) mark(and(x1, x2)) -> andActive(mark(x1), x2) andActive(x1, x2) -> and(x1, x2) mark(isNat(x1)) -> isNatActive(x1) isNatActive(x1) -> isNat(x1) mark(isNatIList(x1)) -> isNatIListActive(x1) isNatIListActive(x1) -> isNatIList(x1) mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) isNatIListKindActive(x1) -> isNatIListKind(x1) mark(isNatKind(x1)) -> isNatKindActive(x1) isNatKindActive(x1) -> isNatKind(x1) mark(isNatList(x1)) -> isNatListActive(x1) isNatListActive(x1) -> isNatList(x1) mark(length(x1)) -> lengthActive(mark(x1)) lengthActive(x1) -> length(x1) mark(cons(x1, x2)) -> cons(mark(x1), x2) mark(0) -> 0 mark(tt) -> tt mark(s(x1)) -> s(mark(x1)) mark(nil) -> nil zerosActive -> cons(0, zeros) U21Active(tt, V1) -> U22Active(isNatActive(V1)) U22Active(tt) -> tt U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) U43Active(tt) -> tt U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) U52Active(tt, V2) -> U53Active(isNatListActive(V2)) U53Active(tt) -> tt U61Active(tt, L) -> s(lengthActive(mark(L))) andActive(tt, X) -> mark(X) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) isNatIListKindActive(nil) -> tt isNatIListKindActive(zeros) -> tt isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) isNatKindActive(0) -> tt isNatKindActive(length(V1)) -> isNatIListKindActive(V1) isNatKindActive(s(V1)) -> isNatKindActive(V1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (70) QDPSizeChangeProof (EQUIVALENT) By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. From the DPs we obtained the following set of size-change graphs: *U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) The graph contains the following edges 2 >= 1 *ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) The graph contains the following edges 1 > 2, 1 > 3 *U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) The graph contains the following edges 3 >= 2 ---------------------------------------- (71) YES