/export/starexec/sandbox/solver/bin/starexec_run_standard /export/starexec/sandbox/benchmark/theBenchmark.xml /export/starexec/sandbox/output/output_files -------------------------------------------------------------------------------- YES proof of /export/starexec/sandbox/benchmark/theBenchmark.xml # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty Termination w.r.t. Q of the given QTRS could be proven: (0) QTRS (1) QTRSToCSRProof [EQUIVALENT, 0 ms] (2) CSR (3) CSRRRRProof [EQUIVALENT, 70 ms] (4) CSR (5) CSRRRRProof [EQUIVALENT, 2 ms] (6) CSR (7) CSRRRRProof [EQUIVALENT, 5 ms] (8) CSR (9) CSRRRRProof [EQUIVALENT, 17 ms] (10) CSR (11) CSRRRRProof [EQUIVALENT, 19 ms] (12) CSR (13) CSRRRRProof [EQUIVALENT, 20 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, 148 ms] (22) QDP (23) DependencyGraphProof [EQUIVALENT, 0 ms] (24) AND (25) QDP (26) QDPOrderProof [EQUIVALENT, 28 ms] (27) QDP (28) DependencyGraphProof [EQUIVALENT, 0 ms] (29) TRUE (30) QDP (31) QDPOrderProof [EQUIVALENT, 41 ms] (32) QDP (33) DependencyGraphProof [EQUIVALENT, 0 ms] (34) QDP (35) UsableRulesProof [EQUIVALENT, 0 ms] (36) QDP (37) QDPSizeChangeProof [EQUIVALENT, 0 ms] (38) YES ---------------------------------------- (0) Obligation: Q restricted rewrite system: The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(U11(tt, V1)) -> mark(U12(isNatList(V1))) active(U12(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNat(V1))) active(U22(tt)) -> mark(tt) active(U31(tt, V)) -> mark(U32(isNatList(V))) active(U32(tt)) -> mark(tt) active(U41(tt, V1, V2)) -> mark(U42(isNat(V1), V2)) active(U42(tt, V2)) -> mark(U43(isNatIList(V2))) active(U43(tt)) -> mark(tt) active(U51(tt, V1, V2)) -> mark(U52(isNat(V1), V2)) active(U52(tt, V2)) -> mark(U53(isNatList(V2))) active(U53(tt)) -> mark(tt) active(U61(tt, L)) -> mark(s(length(L))) active(and(tt, X)) -> mark(X) active(isNat(0)) -> mark(tt) active(isNat(length(V1))) -> mark(U11(isNatIListKind(V1), V1)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatIList(V)) -> mark(U31(isNatIListKind(V), V)) active(isNatIList(zeros)) -> mark(tt) active(isNatIList(cons(V1, V2))) -> mark(U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) active(isNatIListKind(nil)) -> mark(tt) active(isNatIListKind(zeros)) -> mark(tt) active(isNatIListKind(cons(V1, V2))) -> mark(and(isNatKind(V1), isNatIListKind(V2))) active(isNatKind(0)) -> mark(tt) active(isNatKind(length(V1))) -> mark(isNatIListKind(V1)) active(isNatKind(s(V1))) -> mark(isNatKind(V1)) active(isNatList(nil)) -> mark(tt) active(isNatList(cons(V1, V2))) -> mark(U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) active(length(nil)) -> mark(0) active(length(cons(N, L))) -> mark(U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L)) active(cons(X1, X2)) -> cons(active(X1), X2) active(U11(X1, X2)) -> U11(active(X1), X2) active(U12(X)) -> U12(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X)) -> U22(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) active(U42(X1, X2)) -> U42(active(X1), X2) active(U43(X)) -> U43(active(X)) active(U51(X1, X2, X3)) -> U51(active(X1), X2, X3) active(U52(X1, X2)) -> U52(active(X1), X2) active(U53(X)) -> U53(active(X)) active(U61(X1, X2)) -> U61(active(X1), X2) active(s(X)) -> s(active(X)) active(length(X)) -> length(active(X)) active(and(X1, X2)) -> and(active(X1), X2) cons(mark(X1), X2) -> mark(cons(X1, X2)) U11(mark(X1), X2) -> mark(U11(X1, X2)) U12(mark(X)) -> mark(U12(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X)) -> mark(U22(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) U42(mark(X1), X2) -> mark(U42(X1, X2)) U43(mark(X)) -> mark(U43(X)) U51(mark(X1), X2, X3) -> mark(U51(X1, X2, X3)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U53(mark(X)) -> mark(U53(X)) U61(mark(X1), X2) -> mark(U61(X1, X2)) s(mark(X)) -> mark(s(X)) length(mark(X)) -> mark(length(X)) and(mark(X1), X2) -> mark(and(X1, X2)) proper(zeros) -> ok(zeros) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(0) -> ok(0) proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) proper(tt) -> ok(tt) proper(U12(X)) -> U12(proper(X)) proper(isNatList(X)) -> isNatList(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X)) -> U22(proper(X)) proper(isNat(X)) -> isNat(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) proper(U42(X1, X2)) -> U42(proper(X1), proper(X2)) proper(U43(X)) -> U43(proper(X)) proper(isNatIList(X)) -> isNatIList(proper(X)) proper(U51(X1, X2, X3)) -> U51(proper(X1), proper(X2), proper(X3)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U53(X)) -> U53(proper(X)) proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) proper(s(X)) -> s(proper(X)) proper(length(X)) -> length(proper(X)) proper(and(X1, X2)) -> and(proper(X1), proper(X2)) proper(isNatIListKind(X)) -> isNatIListKind(proper(X)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(nil) -> ok(nil) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) U12(ok(X)) -> ok(U12(X)) isNatList(ok(X)) -> ok(isNatList(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X)) -> ok(U22(X)) isNat(ok(X)) -> ok(isNat(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) U42(ok(X1), ok(X2)) -> ok(U42(X1, X2)) U43(ok(X)) -> ok(U43(X)) isNatIList(ok(X)) -> ok(isNatIList(X)) U51(ok(X1), ok(X2), ok(X3)) -> ok(U51(X1, X2, X3)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U53(ok(X)) -> ok(U53(X)) U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) s(ok(X)) -> ok(s(X)) length(ok(X)) -> ok(length(X)) and(ok(X1), ok(X2)) -> ok(and(X1, X2)) isNatIListKind(ok(X)) -> ok(isNatIListKind(X)) isNatKind(ok(X)) -> ok(isNatKind(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Q is empty. ---------------------------------------- (1) QTRSToCSRProof (EQUIVALENT) The following Q TRS is given: Q restricted rewrite system: The TRS R consists of the following rules: active(zeros) -> mark(cons(0, zeros)) active(U11(tt, V1)) -> mark(U12(isNatList(V1))) active(U12(tt)) -> mark(tt) active(U21(tt, V1)) -> mark(U22(isNat(V1))) active(U22(tt)) -> mark(tt) active(U31(tt, V)) -> mark(U32(isNatList(V))) active(U32(tt)) -> mark(tt) active(U41(tt, V1, V2)) -> mark(U42(isNat(V1), V2)) active(U42(tt, V2)) -> mark(U43(isNatIList(V2))) active(U43(tt)) -> mark(tt) active(U51(tt, V1, V2)) -> mark(U52(isNat(V1), V2)) active(U52(tt, V2)) -> mark(U53(isNatList(V2))) active(U53(tt)) -> mark(tt) active(U61(tt, L)) -> mark(s(length(L))) active(and(tt, X)) -> mark(X) active(isNat(0)) -> mark(tt) active(isNat(length(V1))) -> mark(U11(isNatIListKind(V1), V1)) active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) active(isNatIList(V)) -> mark(U31(isNatIListKind(V), V)) active(isNatIList(zeros)) -> mark(tt) active(isNatIList(cons(V1, V2))) -> mark(U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) active(isNatIListKind(nil)) -> mark(tt) active(isNatIListKind(zeros)) -> mark(tt) active(isNatIListKind(cons(V1, V2))) -> mark(and(isNatKind(V1), isNatIListKind(V2))) active(isNatKind(0)) -> mark(tt) active(isNatKind(length(V1))) -> mark(isNatIListKind(V1)) active(isNatKind(s(V1))) -> mark(isNatKind(V1)) active(isNatList(nil)) -> mark(tt) active(isNatList(cons(V1, V2))) -> mark(U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) active(length(nil)) -> mark(0) active(length(cons(N, L))) -> mark(U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L)) active(cons(X1, X2)) -> cons(active(X1), X2) active(U11(X1, X2)) -> U11(active(X1), X2) active(U12(X)) -> U12(active(X)) active(U21(X1, X2)) -> U21(active(X1), X2) active(U22(X)) -> U22(active(X)) active(U31(X1, X2)) -> U31(active(X1), X2) active(U32(X)) -> U32(active(X)) active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) active(U42(X1, X2)) -> U42(active(X1), X2) active(U43(X)) -> U43(active(X)) active(U51(X1, X2, X3)) -> U51(active(X1), X2, X3) active(U52(X1, X2)) -> U52(active(X1), X2) active(U53(X)) -> U53(active(X)) active(U61(X1, X2)) -> U61(active(X1), X2) active(s(X)) -> s(active(X)) active(length(X)) -> length(active(X)) active(and(X1, X2)) -> and(active(X1), X2) cons(mark(X1), X2) -> mark(cons(X1, X2)) U11(mark(X1), X2) -> mark(U11(X1, X2)) U12(mark(X)) -> mark(U12(X)) U21(mark(X1), X2) -> mark(U21(X1, X2)) U22(mark(X)) -> mark(U22(X)) U31(mark(X1), X2) -> mark(U31(X1, X2)) U32(mark(X)) -> mark(U32(X)) U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) U42(mark(X1), X2) -> mark(U42(X1, X2)) U43(mark(X)) -> mark(U43(X)) U51(mark(X1), X2, X3) -> mark(U51(X1, X2, X3)) U52(mark(X1), X2) -> mark(U52(X1, X2)) U53(mark(X)) -> mark(U53(X)) U61(mark(X1), X2) -> mark(U61(X1, X2)) s(mark(X)) -> mark(s(X)) length(mark(X)) -> mark(length(X)) and(mark(X1), X2) -> mark(and(X1, X2)) proper(zeros) -> ok(zeros) proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) proper(0) -> ok(0) proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) proper(tt) -> ok(tt) proper(U12(X)) -> U12(proper(X)) proper(isNatList(X)) -> isNatList(proper(X)) proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) proper(U22(X)) -> U22(proper(X)) proper(isNat(X)) -> isNat(proper(X)) proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) proper(U32(X)) -> U32(proper(X)) proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) proper(U42(X1, X2)) -> U42(proper(X1), proper(X2)) proper(U43(X)) -> U43(proper(X)) proper(isNatIList(X)) -> isNatIList(proper(X)) proper(U51(X1, X2, X3)) -> U51(proper(X1), proper(X2), proper(X3)) proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) proper(U53(X)) -> U53(proper(X)) proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) proper(s(X)) -> s(proper(X)) proper(length(X)) -> length(proper(X)) proper(and(X1, X2)) -> and(proper(X1), proper(X2)) proper(isNatIListKind(X)) -> isNatIListKind(proper(X)) proper(isNatKind(X)) -> isNatKind(proper(X)) proper(nil) -> ok(nil) cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) U12(ok(X)) -> ok(U12(X)) isNatList(ok(X)) -> ok(isNatList(X)) U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) U22(ok(X)) -> ok(U22(X)) isNat(ok(X)) -> ok(isNat(X)) U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) U32(ok(X)) -> ok(U32(X)) U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) U42(ok(X1), ok(X2)) -> ok(U42(X1, X2)) U43(ok(X)) -> ok(U43(X)) isNatIList(ok(X)) -> ok(isNatIList(X)) U51(ok(X1), ok(X2), ok(X3)) -> ok(U51(X1, X2, X3)) U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) U53(ok(X)) -> ok(U53(X)) U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) s(ok(X)) -> ok(s(X)) length(ok(X)) -> ok(length(X)) and(ok(X1), ok(X2)) -> ok(and(X1, X2)) isNatIListKind(ok(X)) -> ok(isNatIListKind(X)) isNatKind(ok(X)) -> ok(isNatKind(X)) top(mark(X)) -> top(proper(X)) top(ok(X)) -> top(active(X)) Q is empty. Special symbols used for the transformation (see [GM04]): top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 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 The QTRS contained all rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is complete (and sound). ---------------------------------------- (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(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 ---------------------------------------- (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(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)) = 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) = 0 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: U32(tt) -> tt isNatIList(zeros) -> tt length(nil) -> 0 ---------------------------------------- (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 U31(tt, V) -> U32(isNatList(V)) 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 U31(tt, V) -> U32(isNatList(V)) 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)) = 2*x_1 POL(U32(x_1)) = 2*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)) = x_1 POL(U52(x_1, x_2)) = 2*x_1 POL(U53(x_1)) = x_1 POL(U61(x_1, x_2)) = 2*x_1 + 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)) = 1 POL(isNatIListKind(x_1)) = 0 POL(isNatKind(x_1)) = 0 POL(isNatList(x_1)) = 0 POL(length(x_1)) = 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: isNatIList(V) -> U31(isNatIListKind(V), V) ---------------------------------------- (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 U31(tt, V) -> U32(isNatList(V)) 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 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 ---------------------------------------- (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 U31(tt, V) -> U32(isNatList(V)) 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 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 POL(U32(x_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: U31(tt, V) -> U32(isNatList(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. U61ACTIVE(tt, L) -> MARK(L) MARK(U61(x1, x2)) -> 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) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( ANDACTIVE_2(x_1, x_2) ) = 2x_2 POL( LENGTHACTIVE_1(x_1) ) = x_1 + 2 POL( U21ACTIVE_2(x_1, x_2) ) = max{0, -2} POL( U41ACTIVE_3(x_1, ..., x_3) ) = max{0, -2} POL( U42ACTIVE_2(x_1, x_2) ) = max{0, -2} POL( U51ACTIVE_3(x_1, ..., x_3) ) = max{0, -2} POL( U52ACTIVE_2(x_1, x_2) ) = max{0, -2} POL( U61ACTIVE_2(x_1, x_2) ) = 2x_2 + 2 POL( mark_1(x_1) ) = 2x_1 POL( zeros ) = 0 POL( zerosActive ) = 0 POL( U21_2(x_1, x_2) ) = 2x_1 POL( U21Active_2(x_1, x_2) ) = 2x_1 POL( U22_1(x_1) ) = x_1 POL( U22Active_1(x_1) ) = x_1 POL( U41_3(x_1, ..., x_3) ) = x_1 POL( U41Active_3(x_1, ..., x_3) ) = x_1 POL( U42_2(x_1, x_2) ) = 2x_1 POL( U42Active_2(x_1, x_2) ) = 2x_1 POL( U43_1(x_1) ) = x_1 POL( U43Active_1(x_1) ) = x_1 POL( U51_3(x_1, ..., x_3) ) = x_1 POL( U51Active_3(x_1, ..., x_3) ) = x_1 POL( U52_2(x_1, x_2) ) = 2x_1 POL( U52Active_2(x_1, x_2) ) = 2x_1 POL( U53_1(x_1) ) = 2x_1 POL( U53Active_1(x_1) ) = 2x_1 POL( U61_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 POL( U61Active_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 POL( and_2(x_1, x_2) ) = 2x_1 + 2x_2 POL( andActive_2(x_1, x_2) ) = 2x_1 + 2x_2 POL( tt ) = 0 POL( isNatIListKind_1(x_1) ) = 0 POL( isNatIListKindActive_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 POL( isNatKindActive_1(x_1) ) = 0 POL( isNatKind_1(x_1) ) = 0 POL( length_1(x_1) ) = x_1 + 1 POL( s_1(x_1) ) = x_1 POL( isNat_1(x_1) ) = 0 POL( isNatActive_1(x_1) ) = 0 POL( isNatIList_1(x_1) ) = 0 POL( isNatIListActive_1(x_1) ) = 0 POL( isNatList_1(x_1) ) = 0 POL( isNatListActive_1(x_1) ) = 0 POL( lengthActive_1(x_1) ) = x_1 + 1 POL( 0 ) = 0 POL( nil ) = 0 POL( MARK_1(x_1) ) = 2x_1 POL( ISNATACTIVE_1(x_1) ) = 0 POL( ISNATKINDACTIVE_1(x_1) ) = 0 POL( ISNATILISTKINDACTIVE_1(x_1) ) = 0 POL( ISNATILISTACTIVE_1(x_1) ) = 0 POL( ISNATLISTACTIVE_1(x_1) ) = 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) 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) 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)) 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 2 less nodes. ---------------------------------------- (24) Complex Obligation (AND) ---------------------------------------- (25) Obligation: Q DP problem: The TRS P consists of the following rules: LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(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. ---------------------------------------- (26) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( LENGTHACTIVE_1(x_1) ) = 0 POL( U61ACTIVE_2(x_1, x_2) ) = max{0, 2x_1 - 2} POL( isNatListActive_1(x_1) ) = 0 POL( isNatList_1(x_1) ) = 0 POL( cons_2(x_1, x_2) ) = max{0, x_1 - 2} POL( U51Active_3(x_1, ..., x_3) ) = max{0, -2} POL( andActive_2(x_1, x_2) ) = x_1 POL( isNatKindActive_1(x_1) ) = 2 POL( isNatIListKind_1(x_1) ) = 0 POL( and_2(x_1, x_2) ) = max{0, -2} POL( mark_1(x_1) ) = 2 POL( tt ) = 2 POL( isNatIListKindActive_1(x_1) ) = 2 POL( isNatKind_1(x_1) ) = 0 POL( length_1(x_1) ) = 0 POL( s_1(x_1) ) = max{0, x_1 - 2} POL( zeros ) = 0 POL( zerosActive ) = 0 POL( U21_2(x_1, x_2) ) = 0 POL( U21Active_2(x_1, x_2) ) = 2 POL( U22_1(x_1) ) = 2 POL( U22Active_1(x_1) ) = 2 POL( U41_3(x_1, ..., x_3) ) = 0 POL( U41Active_3(x_1, ..., x_3) ) = max{0, -2} POL( U42_2(x_1, x_2) ) = 0 POL( U42Active_2(x_1, x_2) ) = max{0, -2} POL( U43_1(x_1) ) = 0 POL( U43Active_1(x_1) ) = x_1 POL( U51_3(x_1, ..., x_3) ) = 0 POL( U52_2(x_1, x_2) ) = 0 POL( U52Active_2(x_1, x_2) ) = max{0, -2} POL( U53_1(x_1) ) = 0 POL( U53Active_1(x_1) ) = x_1 POL( U61_2(x_1, x_2) ) = 0 POL( U61Active_2(x_1, x_2) ) = max{0, -2} POL( isNat_1(x_1) ) = 0 POL( isNatActive_1(x_1) ) = 2 POL( isNatIList_1(x_1) ) = 0 POL( isNatIListActive_1(x_1) ) = 0 POL( lengthActive_1(x_1) ) = max{0, -2} POL( 0 ) = 0 POL( nil ) = 0 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: isNatListActive(x1) -> isNatList(x1) isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) andActive(x1, x2) -> and(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(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 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 isNatKindActive(x1) -> isNatKind(x1) isNatKindActive(0) -> tt isNatActive(x1) -> isNat(x1) isNatActive(0) -> tt isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 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: LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), 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. ---------------------------------------- (28) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. ---------------------------------------- (29) TRUE ---------------------------------------- (30) 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(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(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(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. ---------------------------------------- (31) QDPOrderProof (EQUIVALENT) We use the reduction pair processor [LPAR04,JAR06]. The following pairs can be oriented strictly and are deleted. 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(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), 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(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 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(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(cons(x1, x2)) -> MARK(x1) MARK(s(x1)) -> MARK(x1) The remaining pairs can at least be oriented weakly. Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: POL( ANDACTIVE_2(x_1, x_2) ) = 2x_2 + 2 POL( U21ACTIVE_2(x_1, x_2) ) = 2x_2 POL( U41ACTIVE_3(x_1, ..., x_3) ) = 2x_2 + 2x_3 + 2 POL( U42ACTIVE_2(x_1, x_2) ) = 2x_2 + 1 POL( U51ACTIVE_3(x_1, ..., x_3) ) = 2x_2 + x_3 + 2 POL( U52ACTIVE_2(x_1, x_2) ) = x_2 + 2 POL( isNatKindActive_1(x_1) ) = 0 POL( isNatKind_1(x_1) ) = 2x_1 + 1 POL( 0 ) = 0 POL( tt ) = 0 POL( mark_1(x_1) ) = 0 POL( and_2(x_1, x_2) ) = x_1 + x_2 + 1 POL( andActive_2(x_1, x_2) ) = max{0, -2} POL( isNatIListKind_1(x_1) ) = x_1 + 1 POL( isNatIListKindActive_1(x_1) ) = 2 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( length_1(x_1) ) = 2x_1 + 1 POL( s_1(x_1) ) = 2x_1 + 1 POL( zeros ) = 1 POL( zerosActive ) = 0 POL( U21_2(x_1, x_2) ) = x_1 + x_2 POL( U21Active_2(x_1, x_2) ) = max{0, 2x_2 - 2} POL( U22_1(x_1) ) = 2x_1 POL( U22Active_1(x_1) ) = 2 POL( U41_3(x_1, ..., x_3) ) = x_1 + x_2 + x_3 + 2 POL( U41Active_3(x_1, ..., x_3) ) = max{0, 2x_2 + x_3 - 2} POL( U42_2(x_1, x_2) ) = x_1 + 2x_2 + 1 POL( U42Active_2(x_1, x_2) ) = max{0, x_2 - 2} POL( U43_1(x_1) ) = x_1 POL( U43Active_1(x_1) ) = max{0, -2} POL( U51_3(x_1, ..., x_3) ) = x_1 + 2x_2 + x_3 + 2 POL( U51Active_3(x_1, ..., x_3) ) = max{0, 2x_2 - 2} POL( U52_2(x_1, x_2) ) = x_1 + 2x_2 + 2 POL( U52Active_2(x_1, x_2) ) = max{0, x_2 - 2} POL( U53_1(x_1) ) = x_1 + 2 POL( U53Active_1(x_1) ) = max{0, x_1 - 2} POL( U61_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 POL( U61Active_2(x_1, x_2) ) = max{0, x_2 - 2} POL( isNat_1(x_1) ) = 2x_1 POL( isNatActive_1(x_1) ) = 0 POL( isNatIList_1(x_1) ) = x_1 + 1 POL( isNatIListActive_1(x_1) ) = 2x_1 POL( isNatList_1(x_1) ) = x_1 + 2 POL( isNatListActive_1(x_1) ) = x_1 POL( lengthActive_1(x_1) ) = x_1 + 2 POL( nil ) = 0 POL( ISNATACTIVE_1(x_1) ) = 2x_1 POL( ISNATKINDACTIVE_1(x_1) ) = 2x_1 POL( ISNATILISTKINDACTIVE_1(x_1) ) = 2x_1 + 1 POL( MARK_1(x_1) ) = 2x_1 + 1 POL( ISNATILISTACTIVE_1(x_1) ) = 2x_1 + 1 POL( ISNATLISTACTIVE_1(x_1) ) = x_1 + 2 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: none ---------------------------------------- (32) Obligation: Q DP problem: The TRS P consists of the following rules: U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) MARK(U21(x1, x2)) -> MARK(x1) MARK(U22(x1)) -> MARK(x1) U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) MARK(U43(x1)) -> MARK(x1) U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(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. ---------------------------------------- (33) DependencyGraphProof (EQUIVALENT) The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. ---------------------------------------- (34) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U22(x1)) -> MARK(x1) MARK(U21(x1, x2)) -> MARK(x1) MARK(U43(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. ---------------------------------------- (35) 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. ---------------------------------------- (36) Obligation: Q DP problem: The TRS P consists of the following rules: MARK(U22(x1)) -> MARK(x1) MARK(U21(x1, x2)) -> MARK(x1) MARK(U43(x1)) -> MARK(x1) R is empty. Q is empty. We have to consider all minimal (P,Q,R)-chains. ---------------------------------------- (37) 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(U22(x1)) -> MARK(x1) The graph contains the following edges 1 > 1 *MARK(U21(x1, x2)) -> MARK(x1) The graph contains the following edges 1 > 1 *MARK(U43(x1)) -> MARK(x1) The graph contains the following edges 1 > 1 ---------------------------------------- (38) YES