181.03/50.00 YES 201.04/55.05 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 201.04/55.05 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 201.04/55.05 201.04/55.05 201.04/55.05 Termination w.r.t. Q of the given QTRS could be proven: 201.04/55.05 201.04/55.05 (0) QTRS 201.04/55.05 (1) QTRSToCSRProof [SOUND, 0 ms] 201.04/55.05 (2) CSR 201.04/55.05 (3) CSRRRRProof [EQUIVALENT, 110 ms] 201.04/55.05 (4) CSR 201.04/55.05 (5) CSRRRRProof [EQUIVALENT, 21 ms] 201.04/55.05 (6) CSR 201.04/55.05 (7) CSRRRRProof [EQUIVALENT, 6 ms] 201.04/55.05 (8) CSR 201.04/55.05 (9) CSRRRRProof [EQUIVALENT, 9 ms] 201.04/55.05 (10) CSR 201.04/55.05 (11) CSRRRRProof [EQUIVALENT, 9 ms] 201.04/55.05 (12) CSR 201.04/55.05 (13) CSRRRRProof [EQUIVALENT, 21 ms] 201.04/55.05 (14) CSR 201.04/55.05 (15) CSRRRRProof [EQUIVALENT, 40 ms] 201.04/55.05 (16) CSR 201.04/55.05 (17) Incomplete Giesl Middeldorp-Transformation [SOUND, 0 ms] 201.04/55.05 (18) QTRS 201.04/55.05 (19) DependencyPairsProof [EQUIVALENT, 0 ms] 201.04/55.05 (20) QDP 201.04/55.05 (21) DependencyGraphProof [EQUIVALENT, 0 ms] 201.04/55.05 (22) QDP 201.04/55.05 (23) QDPOrderProof [EQUIVALENT, 161 ms] 201.04/55.05 (24) QDP 201.04/55.05 (25) DependencyGraphProof [EQUIVALENT, 0 ms] 201.04/55.05 (26) AND 201.04/55.05 (27) QDP 201.04/55.05 (28) QDPOrderProof [EQUIVALENT, 25 ms] 201.04/55.05 (29) QDP 201.04/55.05 (30) DependencyGraphProof [EQUIVALENT, 0 ms] 201.04/55.05 (31) TRUE 201.04/55.05 (32) QDP 201.04/55.05 (33) QDPOrderProof [EQUIVALENT, 106 ms] 201.04/55.05 (34) QDP 201.04/55.05 (35) DependencyGraphProof [EQUIVALENT, 0 ms] 201.04/55.05 (36) QDP 201.04/55.05 (37) UsableRulesProof [EQUIVALENT, 0 ms] 201.04/55.05 (38) QDP 201.04/55.05 (39) QDPSizeChangeProof [EQUIVALENT, 0 ms] 201.04/55.05 (40) YES 201.04/55.05 201.04/55.05 201.04/55.05 ---------------------------------------- 201.04/55.05 201.04/55.05 (0) 201.04/55.05 Obligation: 201.04/55.05 Q restricted rewrite system: 201.04/55.05 The TRS R consists of the following rules: 201.04/55.05 201.04/55.05 active(zeros) -> mark(cons(0, zeros)) 201.04/55.05 active(U11(tt, V1)) -> mark(U12(isNatList(V1))) 201.04/55.05 active(U12(tt)) -> mark(tt) 201.04/55.05 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 201.04/55.05 active(U22(tt)) -> mark(tt) 201.04/55.05 active(U31(tt, V)) -> mark(U32(isNatList(V))) 201.04/55.05 active(U32(tt)) -> mark(tt) 201.04/55.05 active(U41(tt, V1, V2)) -> mark(U42(isNat(V1), V2)) 201.04/55.05 active(U42(tt, V2)) -> mark(U43(isNatIList(V2))) 201.04/55.05 active(U43(tt)) -> mark(tt) 201.04/55.05 active(U51(tt, V1, V2)) -> mark(U52(isNat(V1), V2)) 201.04/55.05 active(U52(tt, V2)) -> mark(U53(isNatList(V2))) 201.04/55.05 active(U53(tt)) -> mark(tt) 201.04/55.05 active(U61(tt, L)) -> mark(s(length(L))) 201.04/55.05 active(and(tt, X)) -> mark(X) 201.04/55.05 active(isNat(0)) -> mark(tt) 201.04/55.05 active(isNat(length(V1))) -> mark(U11(isNatIListKind(V1), V1)) 201.04/55.05 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 201.04/55.05 active(isNatIList(V)) -> mark(U31(isNatIListKind(V), V)) 201.04/55.05 active(isNatIList(zeros)) -> mark(tt) 201.04/55.05 active(isNatIList(cons(V1, V2))) -> mark(U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) 201.04/55.05 active(isNatIListKind(nil)) -> mark(tt) 201.04/55.05 active(isNatIListKind(zeros)) -> mark(tt) 201.04/55.05 active(isNatIListKind(cons(V1, V2))) -> mark(and(isNatKind(V1), isNatIListKind(V2))) 201.04/55.05 active(isNatKind(0)) -> mark(tt) 201.04/55.05 active(isNatKind(length(V1))) -> mark(isNatIListKind(V1)) 201.04/55.05 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 201.04/55.05 active(isNatList(nil)) -> mark(tt) 201.04/55.05 active(isNatList(cons(V1, V2))) -> mark(U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) 201.04/55.05 active(length(nil)) -> mark(0) 201.04/55.05 active(length(cons(N, L))) -> mark(U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L)) 201.04/55.05 active(cons(X1, X2)) -> cons(active(X1), X2) 201.04/55.05 active(U11(X1, X2)) -> U11(active(X1), X2) 201.04/55.05 active(U12(X)) -> U12(active(X)) 201.04/55.05 active(U21(X1, X2)) -> U21(active(X1), X2) 201.04/55.05 active(U22(X)) -> U22(active(X)) 201.04/55.05 active(U31(X1, X2)) -> U31(active(X1), X2) 201.04/55.05 active(U32(X)) -> U32(active(X)) 201.04/55.05 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 201.04/55.05 active(U42(X1, X2)) -> U42(active(X1), X2) 201.04/55.05 active(U43(X)) -> U43(active(X)) 201.04/55.05 active(U51(X1, X2, X3)) -> U51(active(X1), X2, X3) 201.04/55.05 active(U52(X1, X2)) -> U52(active(X1), X2) 201.04/55.05 active(U53(X)) -> U53(active(X)) 201.04/55.05 active(U61(X1, X2)) -> U61(active(X1), X2) 201.04/55.05 active(s(X)) -> s(active(X)) 201.04/55.05 active(length(X)) -> length(active(X)) 201.04/55.05 active(and(X1, X2)) -> and(active(X1), X2) 201.04/55.05 cons(mark(X1), X2) -> mark(cons(X1, X2)) 201.04/55.05 U11(mark(X1), X2) -> mark(U11(X1, X2)) 201.04/55.05 U12(mark(X)) -> mark(U12(X)) 201.04/55.05 U21(mark(X1), X2) -> mark(U21(X1, X2)) 201.04/55.05 U22(mark(X)) -> mark(U22(X)) 201.04/55.05 U31(mark(X1), X2) -> mark(U31(X1, X2)) 201.04/55.05 U32(mark(X)) -> mark(U32(X)) 201.04/55.05 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 201.04/55.05 U42(mark(X1), X2) -> mark(U42(X1, X2)) 201.04/55.05 U43(mark(X)) -> mark(U43(X)) 201.04/55.05 U51(mark(X1), X2, X3) -> mark(U51(X1, X2, X3)) 201.04/55.05 U52(mark(X1), X2) -> mark(U52(X1, X2)) 201.04/55.05 U53(mark(X)) -> mark(U53(X)) 201.04/55.05 U61(mark(X1), X2) -> mark(U61(X1, X2)) 201.04/55.05 s(mark(X)) -> mark(s(X)) 201.04/55.05 length(mark(X)) -> mark(length(X)) 201.04/55.05 and(mark(X1), X2) -> mark(and(X1, X2)) 201.04/55.05 proper(zeros) -> ok(zeros) 201.04/55.05 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 201.04/55.05 proper(0) -> ok(0) 201.04/55.05 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 201.04/55.05 proper(tt) -> ok(tt) 201.04/55.05 proper(U12(X)) -> U12(proper(X)) 201.04/55.05 proper(isNatList(X)) -> isNatList(proper(X)) 201.04/55.05 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 201.04/55.05 proper(U22(X)) -> U22(proper(X)) 201.04/55.05 proper(isNat(X)) -> isNat(proper(X)) 201.04/55.05 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 201.04/55.05 proper(U32(X)) -> U32(proper(X)) 201.04/55.05 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 201.04/55.05 proper(U42(X1, X2)) -> U42(proper(X1), proper(X2)) 201.04/55.05 proper(U43(X)) -> U43(proper(X)) 201.04/55.05 proper(isNatIList(X)) -> isNatIList(proper(X)) 201.04/55.05 proper(U51(X1, X2, X3)) -> U51(proper(X1), proper(X2), proper(X3)) 201.04/55.05 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 201.04/55.05 proper(U53(X)) -> U53(proper(X)) 201.04/55.05 proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) 201.04/55.05 proper(s(X)) -> s(proper(X)) 201.04/55.05 proper(length(X)) -> length(proper(X)) 201.04/55.05 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 201.04/55.05 proper(isNatIListKind(X)) -> isNatIListKind(proper(X)) 201.04/55.05 proper(isNatKind(X)) -> isNatKind(proper(X)) 201.04/55.05 proper(nil) -> ok(nil) 201.04/55.05 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 201.04/55.05 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 201.04/55.05 U12(ok(X)) -> ok(U12(X)) 201.04/55.05 isNatList(ok(X)) -> ok(isNatList(X)) 201.04/55.05 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 201.04/55.05 U22(ok(X)) -> ok(U22(X)) 201.04/55.05 isNat(ok(X)) -> ok(isNat(X)) 201.04/55.05 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 201.04/55.05 U32(ok(X)) -> ok(U32(X)) 201.04/55.05 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 201.04/55.05 U42(ok(X1), ok(X2)) -> ok(U42(X1, X2)) 201.04/55.05 U43(ok(X)) -> ok(U43(X)) 201.04/55.05 isNatIList(ok(X)) -> ok(isNatIList(X)) 201.04/55.05 U51(ok(X1), ok(X2), ok(X3)) -> ok(U51(X1, X2, X3)) 201.04/55.05 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 201.04/55.05 U53(ok(X)) -> ok(U53(X)) 201.04/55.05 U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) 201.04/55.05 s(ok(X)) -> ok(s(X)) 201.04/55.05 length(ok(X)) -> ok(length(X)) 201.04/55.05 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 201.04/55.05 isNatIListKind(ok(X)) -> ok(isNatIListKind(X)) 201.04/55.05 isNatKind(ok(X)) -> ok(isNatKind(X)) 201.04/55.05 top(mark(X)) -> top(proper(X)) 201.04/55.05 top(ok(X)) -> top(active(X)) 201.04/55.05 201.04/55.05 The set Q consists of the following terms: 201.04/55.05 201.04/55.05 active(zeros) 201.04/55.05 active(isNat(0)) 201.04/55.05 active(isNat(length(x0))) 201.04/55.05 active(isNat(s(x0))) 201.04/55.05 active(isNatIList(x0)) 201.04/55.05 active(isNatIListKind(nil)) 201.04/55.05 active(isNatIListKind(zeros)) 201.04/55.05 active(isNatIListKind(cons(x0, x1))) 201.04/55.05 active(isNatKind(0)) 201.04/55.05 active(isNatKind(length(x0))) 201.04/55.05 active(isNatKind(s(x0))) 201.04/55.05 active(isNatList(nil)) 201.04/55.05 active(isNatList(cons(x0, x1))) 201.04/55.05 active(cons(x0, x1)) 201.04/55.05 active(U11(x0, x1)) 201.04/55.05 active(U12(x0)) 201.04/55.05 active(U21(x0, x1)) 201.04/55.05 active(U22(x0)) 201.04/55.05 active(U31(x0, x1)) 201.04/55.05 active(U32(x0)) 201.04/55.05 active(U41(x0, x1, x2)) 201.04/55.05 active(U42(x0, x1)) 201.04/55.05 active(U43(x0)) 201.04/55.05 active(U51(x0, x1, x2)) 201.04/55.05 active(U52(x0, x1)) 201.04/55.05 active(U53(x0)) 201.04/55.05 active(U61(x0, x1)) 201.04/55.05 active(s(x0)) 201.04/55.05 active(length(x0)) 201.04/55.05 active(and(x0, x1)) 201.04/55.05 cons(mark(x0), x1) 201.04/55.05 U11(mark(x0), x1) 201.04/55.05 U12(mark(x0)) 201.04/55.05 U21(mark(x0), x1) 201.04/55.05 U22(mark(x0)) 201.04/55.05 U31(mark(x0), x1) 201.04/55.05 U32(mark(x0)) 201.04/55.05 U41(mark(x0), x1, x2) 201.04/55.05 U42(mark(x0), x1) 201.04/55.05 U43(mark(x0)) 201.04/55.05 U51(mark(x0), x1, x2) 201.04/55.05 U52(mark(x0), x1) 201.04/55.05 U53(mark(x0)) 201.04/55.05 U61(mark(x0), x1) 201.04/55.05 s(mark(x0)) 201.04/55.05 length(mark(x0)) 201.04/55.05 and(mark(x0), x1) 201.04/55.05 proper(zeros) 201.04/55.05 proper(cons(x0, x1)) 201.04/55.05 proper(0) 201.04/55.05 proper(U11(x0, x1)) 201.04/55.05 proper(tt) 201.04/55.05 proper(U12(x0)) 201.04/55.05 proper(isNatList(x0)) 201.04/55.05 proper(U21(x0, x1)) 201.04/55.05 proper(U22(x0)) 201.04/55.05 proper(isNat(x0)) 201.04/55.05 proper(U31(x0, x1)) 201.04/55.05 proper(U32(x0)) 201.04/55.05 proper(U41(x0, x1, x2)) 201.04/55.05 proper(U42(x0, x1)) 201.04/55.05 proper(U43(x0)) 201.04/55.05 proper(isNatIList(x0)) 201.04/55.05 proper(U51(x0, x1, x2)) 201.04/55.05 proper(U52(x0, x1)) 201.04/55.05 proper(U53(x0)) 201.04/55.05 proper(U61(x0, x1)) 201.04/55.05 proper(s(x0)) 201.04/55.05 proper(length(x0)) 201.04/55.05 proper(and(x0, x1)) 201.04/55.05 proper(isNatIListKind(x0)) 201.04/55.05 proper(isNatKind(x0)) 201.04/55.05 proper(nil) 201.04/55.05 cons(ok(x0), ok(x1)) 201.04/55.05 U11(ok(x0), ok(x1)) 201.04/55.05 U12(ok(x0)) 201.04/55.05 isNatList(ok(x0)) 201.04/55.05 U21(ok(x0), ok(x1)) 201.04/55.05 U22(ok(x0)) 201.04/55.05 isNat(ok(x0)) 201.04/55.05 U31(ok(x0), ok(x1)) 201.04/55.05 U32(ok(x0)) 201.04/55.05 U41(ok(x0), ok(x1), ok(x2)) 201.04/55.05 U42(ok(x0), ok(x1)) 201.04/55.05 U43(ok(x0)) 201.04/55.05 isNatIList(ok(x0)) 201.04/55.05 U51(ok(x0), ok(x1), ok(x2)) 201.04/55.05 U52(ok(x0), ok(x1)) 201.04/55.05 U53(ok(x0)) 201.04/55.05 U61(ok(x0), ok(x1)) 201.04/55.05 s(ok(x0)) 201.04/55.05 length(ok(x0)) 201.04/55.05 and(ok(x0), ok(x1)) 201.04/55.05 isNatIListKind(ok(x0)) 201.04/55.05 isNatKind(ok(x0)) 201.04/55.05 top(mark(x0)) 201.04/55.05 top(ok(x0)) 201.04/55.05 201.04/55.05 201.04/55.05 ---------------------------------------- 201.04/55.05 201.04/55.05 (1) QTRSToCSRProof (SOUND) 201.04/55.05 The following Q TRS is given: Q restricted rewrite system: 201.04/55.05 The TRS R consists of the following rules: 201.04/55.05 201.04/55.05 active(zeros) -> mark(cons(0, zeros)) 201.04/55.05 active(U11(tt, V1)) -> mark(U12(isNatList(V1))) 201.04/55.05 active(U12(tt)) -> mark(tt) 201.04/55.05 active(U21(tt, V1)) -> mark(U22(isNat(V1))) 201.04/55.05 active(U22(tt)) -> mark(tt) 201.04/55.05 active(U31(tt, V)) -> mark(U32(isNatList(V))) 201.04/55.05 active(U32(tt)) -> mark(tt) 201.04/55.05 active(U41(tt, V1, V2)) -> mark(U42(isNat(V1), V2)) 201.04/55.05 active(U42(tt, V2)) -> mark(U43(isNatIList(V2))) 201.04/55.05 active(U43(tt)) -> mark(tt) 201.04/55.05 active(U51(tt, V1, V2)) -> mark(U52(isNat(V1), V2)) 201.04/55.05 active(U52(tt, V2)) -> mark(U53(isNatList(V2))) 201.04/55.05 active(U53(tt)) -> mark(tt) 201.04/55.05 active(U61(tt, L)) -> mark(s(length(L))) 201.04/55.05 active(and(tt, X)) -> mark(X) 201.04/55.05 active(isNat(0)) -> mark(tt) 201.04/55.05 active(isNat(length(V1))) -> mark(U11(isNatIListKind(V1), V1)) 201.04/55.05 active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1)) 201.04/55.05 active(isNatIList(V)) -> mark(U31(isNatIListKind(V), V)) 201.04/55.05 active(isNatIList(zeros)) -> mark(tt) 201.04/55.05 active(isNatIList(cons(V1, V2))) -> mark(U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) 201.04/55.05 active(isNatIListKind(nil)) -> mark(tt) 201.04/55.05 active(isNatIListKind(zeros)) -> mark(tt) 201.04/55.05 active(isNatIListKind(cons(V1, V2))) -> mark(and(isNatKind(V1), isNatIListKind(V2))) 201.04/55.05 active(isNatKind(0)) -> mark(tt) 201.04/55.05 active(isNatKind(length(V1))) -> mark(isNatIListKind(V1)) 201.04/55.05 active(isNatKind(s(V1))) -> mark(isNatKind(V1)) 201.04/55.05 active(isNatList(nil)) -> mark(tt) 201.04/55.05 active(isNatList(cons(V1, V2))) -> mark(U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2)) 201.04/55.05 active(length(nil)) -> mark(0) 201.04/55.05 active(length(cons(N, L))) -> mark(U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L)) 201.04/55.05 active(cons(X1, X2)) -> cons(active(X1), X2) 201.04/55.05 active(U11(X1, X2)) -> U11(active(X1), X2) 201.04/55.05 active(U12(X)) -> U12(active(X)) 201.04/55.05 active(U21(X1, X2)) -> U21(active(X1), X2) 201.04/55.05 active(U22(X)) -> U22(active(X)) 201.04/55.05 active(U31(X1, X2)) -> U31(active(X1), X2) 201.04/55.05 active(U32(X)) -> U32(active(X)) 201.04/55.05 active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3) 201.04/55.05 active(U42(X1, X2)) -> U42(active(X1), X2) 201.04/55.05 active(U43(X)) -> U43(active(X)) 201.04/55.05 active(U51(X1, X2, X3)) -> U51(active(X1), X2, X3) 201.04/55.05 active(U52(X1, X2)) -> U52(active(X1), X2) 201.04/55.05 active(U53(X)) -> U53(active(X)) 201.04/55.05 active(U61(X1, X2)) -> U61(active(X1), X2) 201.04/55.05 active(s(X)) -> s(active(X)) 201.04/55.05 active(length(X)) -> length(active(X)) 201.04/55.05 active(and(X1, X2)) -> and(active(X1), X2) 201.04/55.05 cons(mark(X1), X2) -> mark(cons(X1, X2)) 201.04/55.05 U11(mark(X1), X2) -> mark(U11(X1, X2)) 201.04/55.05 U12(mark(X)) -> mark(U12(X)) 201.04/55.05 U21(mark(X1), X2) -> mark(U21(X1, X2)) 201.04/55.05 U22(mark(X)) -> mark(U22(X)) 201.04/55.05 U31(mark(X1), X2) -> mark(U31(X1, X2)) 201.04/55.05 U32(mark(X)) -> mark(U32(X)) 201.04/55.05 U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3)) 201.04/55.05 U42(mark(X1), X2) -> mark(U42(X1, X2)) 201.04/55.05 U43(mark(X)) -> mark(U43(X)) 201.04/55.05 U51(mark(X1), X2, X3) -> mark(U51(X1, X2, X3)) 201.04/55.05 U52(mark(X1), X2) -> mark(U52(X1, X2)) 201.04/55.05 U53(mark(X)) -> mark(U53(X)) 201.04/55.05 U61(mark(X1), X2) -> mark(U61(X1, X2)) 201.04/55.05 s(mark(X)) -> mark(s(X)) 201.04/55.05 length(mark(X)) -> mark(length(X)) 201.04/55.05 and(mark(X1), X2) -> mark(and(X1, X2)) 201.04/55.05 proper(zeros) -> ok(zeros) 201.04/55.05 proper(cons(X1, X2)) -> cons(proper(X1), proper(X2)) 201.04/55.05 proper(0) -> ok(0) 201.04/55.05 proper(U11(X1, X2)) -> U11(proper(X1), proper(X2)) 201.04/55.05 proper(tt) -> ok(tt) 201.04/55.05 proper(U12(X)) -> U12(proper(X)) 201.04/55.05 proper(isNatList(X)) -> isNatList(proper(X)) 201.04/55.05 proper(U21(X1, X2)) -> U21(proper(X1), proper(X2)) 201.04/55.05 proper(U22(X)) -> U22(proper(X)) 201.04/55.05 proper(isNat(X)) -> isNat(proper(X)) 201.04/55.05 proper(U31(X1, X2)) -> U31(proper(X1), proper(X2)) 201.04/55.05 proper(U32(X)) -> U32(proper(X)) 201.04/55.05 proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3)) 201.04/55.05 proper(U42(X1, X2)) -> U42(proper(X1), proper(X2)) 201.04/55.05 proper(U43(X)) -> U43(proper(X)) 201.04/55.05 proper(isNatIList(X)) -> isNatIList(proper(X)) 201.04/55.05 proper(U51(X1, X2, X3)) -> U51(proper(X1), proper(X2), proper(X3)) 201.04/55.05 proper(U52(X1, X2)) -> U52(proper(X1), proper(X2)) 201.04/55.05 proper(U53(X)) -> U53(proper(X)) 201.04/55.05 proper(U61(X1, X2)) -> U61(proper(X1), proper(X2)) 201.04/55.05 proper(s(X)) -> s(proper(X)) 201.04/55.05 proper(length(X)) -> length(proper(X)) 201.04/55.05 proper(and(X1, X2)) -> and(proper(X1), proper(X2)) 201.04/55.05 proper(isNatIListKind(X)) -> isNatIListKind(proper(X)) 201.04/55.05 proper(isNatKind(X)) -> isNatKind(proper(X)) 201.04/55.05 proper(nil) -> ok(nil) 201.04/55.05 cons(ok(X1), ok(X2)) -> ok(cons(X1, X2)) 201.04/55.05 U11(ok(X1), ok(X2)) -> ok(U11(X1, X2)) 201.04/55.05 U12(ok(X)) -> ok(U12(X)) 201.04/55.05 isNatList(ok(X)) -> ok(isNatList(X)) 201.04/55.05 U21(ok(X1), ok(X2)) -> ok(U21(X1, X2)) 201.04/55.05 U22(ok(X)) -> ok(U22(X)) 201.04/55.05 isNat(ok(X)) -> ok(isNat(X)) 201.04/55.05 U31(ok(X1), ok(X2)) -> ok(U31(X1, X2)) 201.04/55.05 U32(ok(X)) -> ok(U32(X)) 201.04/55.05 U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3)) 201.04/55.05 U42(ok(X1), ok(X2)) -> ok(U42(X1, X2)) 201.04/55.05 U43(ok(X)) -> ok(U43(X)) 201.04/55.05 isNatIList(ok(X)) -> ok(isNatIList(X)) 201.04/55.05 U51(ok(X1), ok(X2), ok(X3)) -> ok(U51(X1, X2, X3)) 201.04/55.05 U52(ok(X1), ok(X2)) -> ok(U52(X1, X2)) 201.04/55.05 U53(ok(X)) -> ok(U53(X)) 201.04/55.05 U61(ok(X1), ok(X2)) -> ok(U61(X1, X2)) 201.04/55.05 s(ok(X)) -> ok(s(X)) 201.04/55.05 length(ok(X)) -> ok(length(X)) 201.04/55.05 and(ok(X1), ok(X2)) -> ok(and(X1, X2)) 201.04/55.05 isNatIListKind(ok(X)) -> ok(isNatIListKind(X)) 201.04/55.05 isNatKind(ok(X)) -> ok(isNatKind(X)) 201.04/55.05 top(mark(X)) -> top(proper(X)) 201.04/55.05 top(ok(X)) -> top(active(X)) 201.04/55.05 201.04/55.05 The set Q consists of the following terms: 201.04/55.05 201.04/55.05 active(zeros) 201.04/55.05 active(isNat(0)) 201.04/55.05 active(isNat(length(x0))) 201.04/55.05 active(isNat(s(x0))) 201.04/55.05 active(isNatIList(x0)) 201.04/55.05 active(isNatIListKind(nil)) 201.04/55.05 active(isNatIListKind(zeros)) 201.04/55.05 active(isNatIListKind(cons(x0, x1))) 201.04/55.05 active(isNatKind(0)) 201.04/55.05 active(isNatKind(length(x0))) 201.04/55.05 active(isNatKind(s(x0))) 201.04/55.05 active(isNatList(nil)) 201.04/55.05 active(isNatList(cons(x0, x1))) 201.04/55.05 active(cons(x0, x1)) 201.04/55.05 active(U11(x0, x1)) 201.04/55.05 active(U12(x0)) 201.04/55.05 active(U21(x0, x1)) 201.04/55.05 active(U22(x0)) 201.04/55.05 active(U31(x0, x1)) 201.04/55.05 active(U32(x0)) 201.04/55.05 active(U41(x0, x1, x2)) 201.04/55.05 active(U42(x0, x1)) 201.04/55.05 active(U43(x0)) 201.04/55.05 active(U51(x0, x1, x2)) 201.04/55.05 active(U52(x0, x1)) 201.04/55.05 active(U53(x0)) 201.04/55.05 active(U61(x0, x1)) 201.04/55.05 active(s(x0)) 201.04/55.05 active(length(x0)) 201.04/55.05 active(and(x0, x1)) 201.04/55.05 cons(mark(x0), x1) 201.04/55.05 U11(mark(x0), x1) 201.04/55.05 U12(mark(x0)) 201.04/55.05 U21(mark(x0), x1) 201.04/55.05 U22(mark(x0)) 201.04/55.05 U31(mark(x0), x1) 201.04/55.05 U32(mark(x0)) 201.04/55.05 U41(mark(x0), x1, x2) 201.04/55.05 U42(mark(x0), x1) 201.04/55.05 U43(mark(x0)) 201.04/55.05 U51(mark(x0), x1, x2) 201.04/55.05 U52(mark(x0), x1) 201.04/55.05 U53(mark(x0)) 201.04/55.05 U61(mark(x0), x1) 201.04/55.05 s(mark(x0)) 201.04/55.05 length(mark(x0)) 201.04/55.05 and(mark(x0), x1) 201.04/55.05 proper(zeros) 201.04/55.05 proper(cons(x0, x1)) 201.04/55.05 proper(0) 201.04/55.05 proper(U11(x0, x1)) 201.04/55.05 proper(tt) 201.04/55.05 proper(U12(x0)) 201.04/55.05 proper(isNatList(x0)) 201.04/55.05 proper(U21(x0, x1)) 201.04/55.05 proper(U22(x0)) 201.04/55.05 proper(isNat(x0)) 201.04/55.05 proper(U31(x0, x1)) 201.04/55.05 proper(U32(x0)) 201.04/55.05 proper(U41(x0, x1, x2)) 201.04/55.05 proper(U42(x0, x1)) 201.04/55.05 proper(U43(x0)) 201.04/55.06 proper(isNatIList(x0)) 201.04/55.06 proper(U51(x0, x1, x2)) 201.04/55.06 proper(U52(x0, x1)) 201.04/55.06 proper(U53(x0)) 201.04/55.06 proper(U61(x0, x1)) 201.04/55.06 proper(s(x0)) 201.04/55.06 proper(length(x0)) 201.04/55.06 proper(and(x0, x1)) 201.04/55.06 proper(isNatIListKind(x0)) 201.04/55.06 proper(isNatKind(x0)) 201.04/55.06 proper(nil) 201.04/55.06 cons(ok(x0), ok(x1)) 201.04/55.06 U11(ok(x0), ok(x1)) 201.04/55.06 U12(ok(x0)) 201.04/55.06 isNatList(ok(x0)) 201.04/55.06 U21(ok(x0), ok(x1)) 201.04/55.06 U22(ok(x0)) 201.04/55.06 isNat(ok(x0)) 201.04/55.06 U31(ok(x0), ok(x1)) 201.04/55.06 U32(ok(x0)) 201.04/55.06 U41(ok(x0), ok(x1), ok(x2)) 201.04/55.06 U42(ok(x0), ok(x1)) 201.04/55.06 U43(ok(x0)) 201.04/55.06 isNatIList(ok(x0)) 201.04/55.06 U51(ok(x0), ok(x1), ok(x2)) 201.04/55.06 U52(ok(x0), ok(x1)) 201.04/55.06 U53(ok(x0)) 201.04/55.06 U61(ok(x0), ok(x1)) 201.04/55.06 s(ok(x0)) 201.04/55.06 length(ok(x0)) 201.04/55.06 and(ok(x0), ok(x1)) 201.04/55.06 isNatIListKind(ok(x0)) 201.04/55.06 isNatKind(ok(x0)) 201.04/55.06 top(mark(x0)) 201.04/55.06 top(ok(x0)) 201.04/55.06 201.04/55.06 Special symbols used for the transformation (see [GM04]): 201.04/55.06 top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete. 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (2) 201.04/55.06 Obligation: 201.04/55.06 Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U31(tt, V) -> U32(isNatList(V)) 201.04/55.06 U32(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(zeros) -> tt 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(nil) -> 0 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (3) CSRRRRProof (EQUIVALENT) 201.04/55.06 The following CSR is given: Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U31(tt, V) -> U32(isNatList(V)) 201.04/55.06 U32(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(zeros) -> tt 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(nil) -> 0 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 Used ordering: 201.04/55.06 Polynomial interpretation [POLO]: 201.04/55.06 201.04/55.06 POL(0) = 0 201.04/55.06 POL(U11(x_1, x_2)) = 2*x_1 201.04/55.06 POL(U12(x_1)) = 2*x_1 201.04/55.06 POL(U21(x_1, x_2)) = 2*x_1 201.04/55.06 POL(U22(x_1)) = x_1 201.04/55.06 POL(U31(x_1, x_2)) = 2*x_1 201.04/55.06 POL(U32(x_1)) = x_1 201.04/55.06 POL(U41(x_1, x_2, x_3)) = 2*x_1 201.04/55.06 POL(U42(x_1, x_2)) = x_1 201.04/55.06 POL(U43(x_1)) = x_1 201.04/55.06 POL(U51(x_1, x_2, x_3)) = 2*x_1 201.04/55.06 POL(U52(x_1, x_2)) = x_1 201.04/55.06 POL(U53(x_1)) = x_1 201.04/55.06 POL(U61(x_1, x_2)) = 2*x_1 + 2*x_2 201.04/55.06 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 201.04/55.06 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 201.04/55.06 POL(isNat(x_1)) = 0 201.04/55.06 POL(isNatIList(x_1)) = 0 201.04/55.06 POL(isNatIListKind(x_1)) = 0 201.04/55.06 POL(isNatKind(x_1)) = 0 201.04/55.06 POL(isNatList(x_1)) = 0 201.04/55.06 POL(length(x_1)) = x_1 201.04/55.06 POL(nil) = 2 201.04/55.06 POL(s(x_1)) = 2*x_1 201.04/55.06 POL(tt) = 0 201.04/55.06 POL(zeros) = 0 201.04/55.06 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.04/55.06 201.04/55.06 length(nil) -> 0 201.04/55.06 201.04/55.06 201.04/55.06 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (4) 201.04/55.06 Obligation: 201.04/55.06 Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U31(tt, V) -> U32(isNatList(V)) 201.04/55.06 U32(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(zeros) -> tt 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (5) CSRRRRProof (EQUIVALENT) 201.04/55.06 The following CSR is given: Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U31(tt, V) -> U32(isNatList(V)) 201.04/55.06 U32(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(zeros) -> tt 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 Used ordering: 201.04/55.06 Polynomial interpretation [POLO]: 201.04/55.06 201.04/55.06 POL(0) = 0 201.04/55.06 POL(U11(x_1, x_2)) = 2*x_1 201.04/55.06 POL(U12(x_1)) = x_1 201.04/55.06 POL(U21(x_1, x_2)) = 2*x_1 201.04/55.06 POL(U22(x_1)) = x_1 201.04/55.06 POL(U31(x_1, x_2)) = 1 + 2*x_1 201.04/55.06 POL(U32(x_1)) = x_1 201.04/55.06 POL(U41(x_1, x_2, x_3)) = 1 + 2*x_1 201.04/55.06 POL(U42(x_1, x_2)) = 1 + 2*x_1 201.04/55.06 POL(U43(x_1)) = x_1 201.04/55.06 POL(U51(x_1, x_2, x_3)) = 2*x_1 201.04/55.06 POL(U52(x_1, x_2)) = x_1 201.04/55.06 POL(U53(x_1)) = x_1 201.04/55.06 POL(U61(x_1, x_2)) = 2*x_1 + 2*x_2 201.04/55.06 POL(and(x_1, x_2)) = 2*x_1 + 2*x_2 201.04/55.06 POL(cons(x_1, x_2)) = x_1 + 2*x_2 201.04/55.06 POL(isNat(x_1)) = 0 201.04/55.06 POL(isNatIList(x_1)) = 1 201.04/55.06 POL(isNatIListKind(x_1)) = 0 201.04/55.06 POL(isNatKind(x_1)) = 0 201.04/55.06 POL(isNatList(x_1)) = 0 201.04/55.06 POL(length(x_1)) = 2*x_1 201.04/55.06 POL(nil) = 0 201.04/55.06 POL(s(x_1)) = x_1 201.04/55.06 POL(tt) = 0 201.04/55.06 POL(zeros) = 0 201.04/55.06 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.04/55.06 201.04/55.06 U31(tt, V) -> U32(isNatList(V)) 201.04/55.06 isNatIList(zeros) -> tt 201.04/55.06 201.04/55.06 201.04/55.06 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (6) 201.04/55.06 Obligation: 201.04/55.06 Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U32(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (7) CSRRRRProof (EQUIVALENT) 201.04/55.06 The following CSR is given: Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U32(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U32: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 Used ordering: 201.04/55.06 Polynomial interpretation [POLO]: 201.04/55.06 201.04/55.06 POL(0) = 0 201.04/55.06 POL(U11(x_1, x_2)) = x_1 201.04/55.06 POL(U12(x_1)) = x_1 201.04/55.06 POL(U21(x_1, x_2)) = x_1 201.04/55.06 POL(U22(x_1)) = x_1 201.04/55.06 POL(U31(x_1, x_2)) = 1 + x_1 + x_2 201.04/55.06 POL(U32(x_1)) = 1 + x_1 201.04/55.06 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 201.04/55.06 POL(U42(x_1, x_2)) = 1 + x_1 + x_2 201.04/55.06 POL(U43(x_1)) = x_1 201.04/55.06 POL(U51(x_1, x_2, x_3)) = x_1 201.04/55.06 POL(U52(x_1, x_2)) = x_1 201.04/55.06 POL(U53(x_1)) = x_1 201.04/55.06 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 201.04/55.06 POL(and(x_1, x_2)) = x_1 + x_2 201.04/55.06 POL(cons(x_1, x_2)) = x_1 + x_2 201.04/55.06 POL(isNat(x_1)) = 0 201.04/55.06 POL(isNatIList(x_1)) = 1 + x_1 201.04/55.06 POL(isNatIListKind(x_1)) = 0 201.04/55.06 POL(isNatKind(x_1)) = 0 201.04/55.06 POL(isNatList(x_1)) = 0 201.04/55.06 POL(length(x_1)) = 1 + x_1 201.04/55.06 POL(nil) = 1 201.04/55.06 POL(s(x_1)) = x_1 201.04/55.06 POL(tt) = 0 201.04/55.06 POL(zeros) = 1 201.04/55.06 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.04/55.06 201.04/55.06 U32(tt) -> tt 201.04/55.06 201.04/55.06 201.04/55.06 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (8) 201.04/55.06 Obligation: 201.04/55.06 Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 201.04/55.06 ---------------------------------------- 201.04/55.06 201.04/55.06 (9) CSRRRRProof (EQUIVALENT) 201.04/55.06 The following CSR is given: Context-sensitive rewrite system: 201.04/55.06 The TRS R consists of the following rules: 201.04/55.06 201.04/55.06 zeros -> cons(0, zeros) 201.04/55.06 U11(tt, V1) -> U12(isNatList(V1)) 201.04/55.06 U12(tt) -> tt 201.04/55.06 U21(tt, V1) -> U22(isNat(V1)) 201.04/55.06 U22(tt) -> tt 201.04/55.06 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.04/55.06 U42(tt, V2) -> U43(isNatIList(V2)) 201.04/55.06 U43(tt) -> tt 201.04/55.06 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.04/55.06 U52(tt, V2) -> U53(isNatList(V2)) 201.04/55.06 U53(tt) -> tt 201.04/55.06 U61(tt, L) -> s(length(L)) 201.04/55.06 and(tt, X) -> X 201.04/55.06 isNat(0) -> tt 201.04/55.06 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.04/55.06 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.04/55.06 isNatIList(V) -> U31(isNatIListKind(V), V) 201.04/55.06 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 isNatIListKind(nil) -> tt 201.04/55.06 isNatIListKind(zeros) -> tt 201.04/55.06 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.04/55.06 isNatKind(0) -> tt 201.04/55.06 isNatKind(length(V1)) -> isNatIListKind(V1) 201.04/55.06 isNatKind(s(V1)) -> isNatKind(V1) 201.04/55.06 isNatList(nil) -> tt 201.04/55.06 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.04/55.06 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.04/55.06 201.04/55.06 The replacement map contains the following entries: 201.04/55.06 201.04/55.06 zeros: empty set 201.04/55.06 cons: {1} 201.04/55.06 0: empty set 201.04/55.06 U11: {1} 201.04/55.06 tt: empty set 201.04/55.06 U12: {1} 201.04/55.06 isNatList: empty set 201.04/55.06 U21: {1} 201.04/55.06 U22: {1} 201.04/55.06 isNat: empty set 201.04/55.06 U31: {1} 201.04/55.06 U41: {1} 201.04/55.06 U42: {1} 201.04/55.06 U43: {1} 201.04/55.06 isNatIList: empty set 201.04/55.06 U51: {1} 201.04/55.06 U52: {1} 201.04/55.06 U53: {1} 201.04/55.06 U61: {1} 201.04/55.06 s: {1} 201.04/55.06 length: {1} 201.04/55.06 and: {1} 201.04/55.06 isNatIListKind: empty set 201.04/55.06 isNatKind: empty set 201.04/55.06 nil: empty set 201.04/55.06 Used ordering: 201.04/55.06 Polynomial interpretation [POLO]: 201.04/55.06 201.04/55.06 POL(0) = 0 201.04/55.06 POL(U11(x_1, x_2)) = x_1 201.18/55.08 POL(U12(x_1)) = x_1 201.18/55.08 POL(U21(x_1, x_2)) = x_1 201.18/55.08 POL(U22(x_1)) = x_1 201.18/55.08 POL(U31(x_1, x_2)) = x_1 + x_2 201.18/55.08 POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3 201.18/55.08 POL(U42(x_1, x_2)) = 1 + x_1 + x_2 201.18/55.08 POL(U43(x_1)) = x_1 201.18/55.08 POL(U51(x_1, x_2, x_3)) = x_1 201.18/55.08 POL(U52(x_1, x_2)) = x_1 201.18/55.08 POL(U53(x_1)) = x_1 201.18/55.08 POL(U61(x_1, x_2)) = 1 + x_1 + x_2 201.18/55.08 POL(and(x_1, x_2)) = x_1 + x_2 201.18/55.08 POL(cons(x_1, x_2)) = x_1 + x_2 201.18/55.08 POL(isNat(x_1)) = 0 201.18/55.08 POL(isNatIList(x_1)) = 1 + x_1 201.18/55.08 POL(isNatIListKind(x_1)) = 0 201.18/55.08 POL(isNatKind(x_1)) = 0 201.18/55.08 POL(isNatList(x_1)) = 0 201.18/55.08 POL(length(x_1)) = 1 + x_1 201.18/55.08 POL(nil) = 1 201.18/55.08 POL(s(x_1)) = x_1 201.18/55.08 POL(tt) = 0 201.18/55.08 POL(zeros) = 1 201.18/55.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.18/55.08 201.18/55.08 isNatIList(V) -> U31(isNatIListKind(V), V) 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (10) 201.18/55.08 Obligation: 201.18/55.08 Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U11(tt, V1) -> U12(isNatList(V1)) 201.18/55.08 U12(tt) -> tt 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(nil) -> tt 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 U11: {1} 201.18/55.08 tt: empty set 201.18/55.08 U12: {1} 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (11) CSRRRRProof (EQUIVALENT) 201.18/55.08 The following CSR is given: Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U11(tt, V1) -> U12(isNatList(V1)) 201.18/55.08 U12(tt) -> tt 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(nil) -> tt 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 U11: {1} 201.18/55.08 tt: empty set 201.18/55.08 U12: {1} 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 Used ordering: 201.18/55.08 Polynomial interpretation [POLO]: 201.18/55.08 201.18/55.08 POL(0) = 0 201.18/55.08 POL(U11(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 201.18/55.08 POL(U12(x_1)) = 1 + x_1 201.18/55.08 POL(U21(x_1, x_2)) = 2*x_1 + x_2 201.18/55.08 POL(U22(x_1)) = x_1 201.18/55.08 POL(U41(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 201.18/55.08 POL(U42(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(U43(x_1)) = x_1 201.18/55.08 POL(U51(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3 201.18/55.08 POL(U52(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(U53(x_1)) = x_1 201.18/55.08 POL(U61(x_1, x_2)) = 2 + x_1 + 2*x_2 201.18/55.08 POL(and(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 201.18/55.08 POL(isNat(x_1)) = x_1 201.18/55.08 POL(isNatIList(x_1)) = 2*x_1 201.18/55.08 POL(isNatIListKind(x_1)) = 0 201.18/55.08 POL(isNatKind(x_1)) = 0 201.18/55.08 POL(isNatList(x_1)) = 2*x_1 201.18/55.08 POL(length(x_1)) = 2 + 2*x_1 201.18/55.08 POL(nil) = 0 201.18/55.08 POL(s(x_1)) = x_1 201.18/55.08 POL(tt) = 0 201.18/55.08 POL(zeros) = 0 201.18/55.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.18/55.08 201.18/55.08 U11(tt, V1) -> U12(isNatList(V1)) 201.18/55.08 U12(tt) -> tt 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (12) 201.18/55.08 Obligation: 201.18/55.08 Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(nil) -> tt 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 U11: {1} 201.18/55.08 tt: empty set 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (13) CSRRRRProof (EQUIVALENT) 201.18/55.08 The following CSR is given: Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(nil) -> tt 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 U11: {1} 201.18/55.08 tt: empty set 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 Used ordering: 201.18/55.08 Polynomial interpretation [POLO]: 201.18/55.08 201.18/55.08 POL(0) = 0 201.18/55.08 POL(U11(x_1, x_2)) = x_1 201.18/55.08 POL(U21(x_1, x_2)) = x_1 201.18/55.08 POL(U22(x_1)) = 2*x_1 201.18/55.08 POL(U41(x_1, x_2, x_3)) = x_1 201.18/55.08 POL(U42(x_1, x_2)) = x_1 201.18/55.08 POL(U43(x_1)) = 2*x_1 201.18/55.08 POL(U51(x_1, x_2, x_3)) = x_1 + 2*x_3 201.18/55.08 POL(U52(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(U53(x_1)) = 2*x_1 201.18/55.08 POL(U61(x_1, x_2)) = 2*x_1 + 2*x_2 201.18/55.08 POL(and(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(cons(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(isNat(x_1)) = 0 201.18/55.08 POL(isNatIList(x_1)) = 0 201.18/55.08 POL(isNatIListKind(x_1)) = 0 201.18/55.08 POL(isNatKind(x_1)) = 0 201.18/55.08 POL(isNatList(x_1)) = x_1 201.18/55.08 POL(length(x_1)) = 2*x_1 201.18/55.08 POL(nil) = 1 201.18/55.08 POL(s(x_1)) = x_1 201.18/55.08 POL(tt) = 0 201.18/55.08 POL(zeros) = 0 201.18/55.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.18/55.08 201.18/55.08 isNatList(nil) -> tt 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (14) 201.18/55.08 Obligation: 201.18/55.08 Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 U11: {1} 201.18/55.08 tt: empty set 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (15) CSRRRRProof (EQUIVALENT) 201.18/55.08 The following CSR is given: Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 U11: {1} 201.18/55.08 tt: empty set 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 Used ordering: 201.18/55.08 Polynomial interpretation [POLO]: 201.18/55.08 201.18/55.08 POL(0) = 0 201.18/55.08 POL(U11(x_1, x_2)) = 2*x_1 201.18/55.08 POL(U21(x_1, x_2)) = 2*x_1 + x_2 201.18/55.08 POL(U22(x_1)) = x_1 201.18/55.08 POL(U41(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 201.18/55.08 POL(U42(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(U43(x_1)) = 2*x_1 201.18/55.08 POL(U51(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3 201.18/55.08 POL(U52(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(U53(x_1)) = 2*x_1 201.18/55.08 POL(U61(x_1, x_2)) = 1 + 2*x_1 + 2*x_2 201.18/55.08 POL(and(x_1, x_2)) = x_1 + 2*x_2 201.18/55.08 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 201.18/55.08 POL(isNat(x_1)) = x_1 201.18/55.08 POL(isNatIList(x_1)) = x_1 201.18/55.08 POL(isNatIListKind(x_1)) = 0 201.18/55.08 POL(isNatKind(x_1)) = 0 201.18/55.08 POL(isNatList(x_1)) = x_1 201.18/55.08 POL(length(x_1)) = 1 + 2*x_1 201.18/55.08 POL(nil) = 2 201.18/55.08 POL(s(x_1)) = x_1 201.18/55.08 POL(tt) = 0 201.18/55.08 POL(zeros) = 0 201.18/55.08 With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly: 201.18/55.08 201.18/55.08 isNat(length(V1)) -> U11(isNatIListKind(V1), V1) 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (16) 201.18/55.08 Obligation: 201.18/55.08 Context-sensitive rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 zeros -> cons(0, zeros) 201.18/55.08 U21(tt, V1) -> U22(isNat(V1)) 201.18/55.08 U22(tt) -> tt 201.18/55.08 U41(tt, V1, V2) -> U42(isNat(V1), V2) 201.18/55.08 U42(tt, V2) -> U43(isNatIList(V2)) 201.18/55.08 U43(tt) -> tt 201.18/55.08 U51(tt, V1, V2) -> U52(isNat(V1), V2) 201.18/55.08 U52(tt, V2) -> U53(isNatList(V2)) 201.18/55.08 U53(tt) -> tt 201.18/55.08 U61(tt, L) -> s(length(L)) 201.18/55.08 and(tt, X) -> X 201.18/55.08 isNat(0) -> tt 201.18/55.08 isNat(s(V1)) -> U21(isNatKind(V1), V1) 201.18/55.08 isNatIList(cons(V1, V2)) -> U41(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKind(nil) -> tt 201.18/55.08 isNatIListKind(zeros) -> tt 201.18/55.08 isNatIListKind(cons(V1, V2)) -> and(isNatKind(V1), isNatIListKind(V2)) 201.18/55.08 isNatKind(0) -> tt 201.18/55.08 isNatKind(length(V1)) -> isNatIListKind(V1) 201.18/55.08 isNatKind(s(V1)) -> isNatKind(V1) 201.18/55.08 isNatList(cons(V1, V2)) -> U51(and(isNatKind(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 length(cons(N, L)) -> U61(and(and(isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 The replacement map contains the following entries: 201.18/55.08 201.18/55.08 zeros: empty set 201.18/55.08 cons: {1} 201.18/55.08 0: empty set 201.18/55.08 tt: empty set 201.18/55.08 isNatList: empty set 201.18/55.08 U21: {1} 201.18/55.08 U22: {1} 201.18/55.08 isNat: empty set 201.18/55.08 U41: {1} 201.18/55.08 U42: {1} 201.18/55.08 U43: {1} 201.18/55.08 isNatIList: empty set 201.18/55.08 U51: {1} 201.18/55.08 U52: {1} 201.18/55.08 U53: {1} 201.18/55.08 U61: {1} 201.18/55.08 s: {1} 201.18/55.08 length: {1} 201.18/55.08 and: {1} 201.18/55.08 isNatIListKind: empty set 201.18/55.08 isNatKind: empty set 201.18/55.08 nil: empty set 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (17) Incomplete Giesl Middeldorp-Transformation (SOUND) 201.18/55.08 We applied the Incomplete Giesl Middeldorp transformation [CS_Term] to transform the context-sensitive TRS to a usual TRS. 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (18) 201.18/55.08 Obligation: 201.18/55.08 Q restricted rewrite system: 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 mark(zeros) -> zerosActive 201.18/55.08 zerosActive -> zeros 201.18/55.08 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.08 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.08 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.08 U22Active(x1) -> U22(x1) 201.18/55.08 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.08 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.08 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.08 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.08 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.08 U43Active(x1) -> U43(x1) 201.18/55.08 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.08 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.08 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.08 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.08 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.08 U53Active(x1) -> U53(x1) 201.18/55.08 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.08 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.08 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.08 andActive(x1, x2) -> and(x1, x2) 201.18/55.08 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.08 isNatActive(x1) -> isNat(x1) 201.18/55.08 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.08 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.08 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.08 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.08 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.08 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.08 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.08 isNatListActive(x1) -> isNatList(x1) 201.18/55.08 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.08 lengthActive(x1) -> length(x1) 201.18/55.08 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.08 mark(0) -> 0 201.18/55.08 mark(tt) -> tt 201.18/55.08 mark(s(x1)) -> s(mark(x1)) 201.18/55.08 mark(nil) -> nil 201.18/55.08 zerosActive -> cons(0, zeros) 201.18/55.08 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.08 U22Active(tt) -> tt 201.18/55.08 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.08 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.08 U43Active(tt) -> tt 201.18/55.08 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.08 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.08 U53Active(tt) -> tt 201.18/55.08 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.08 andActive(tt, X) -> mark(X) 201.18/55.08 isNatActive(0) -> tt 201.18/55.08 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.08 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 isNatIListKindActive(nil) -> tt 201.18/55.08 isNatIListKindActive(zeros) -> tt 201.18/55.08 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.08 isNatKindActive(0) -> tt 201.18/55.08 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.08 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.08 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 201.18/55.08 Q is empty. 201.18/55.08 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (19) DependencyPairsProof (EQUIVALENT) 201.18/55.08 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 201.18/55.08 ---------------------------------------- 201.18/55.08 201.18/55.08 (20) 201.18/55.08 Obligation: 201.18/55.08 Q DP problem: 201.18/55.08 The TRS P consists of the following rules: 201.18/55.08 201.18/55.08 MARK(zeros) -> ZEROSACTIVE 201.18/55.08 MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) 201.18/55.08 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.08 MARK(U22(x1)) -> U22ACTIVE(mark(x1)) 201.18/55.08 MARK(U22(x1)) -> MARK(x1) 201.18/55.08 MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) 201.18/55.08 MARK(U41(x1, x2, x3)) -> MARK(x1) 201.18/55.08 MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) 201.18/55.08 MARK(U42(x1, x2)) -> MARK(x1) 201.18/55.08 MARK(U43(x1)) -> U43ACTIVE(mark(x1)) 201.18/55.08 MARK(U43(x1)) -> MARK(x1) 201.18/55.08 MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) 201.18/55.08 MARK(U51(x1, x2, x3)) -> MARK(x1) 201.18/55.08 MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) 201.18/55.08 MARK(U52(x1, x2)) -> MARK(x1) 201.18/55.08 MARK(U53(x1)) -> U53ACTIVE(mark(x1)) 201.18/55.08 MARK(U53(x1)) -> MARK(x1) 201.18/55.08 MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) 201.18/55.08 MARK(U61(x1, x2)) -> MARK(x1) 201.18/55.08 MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) 201.18/55.08 MARK(and(x1, x2)) -> MARK(x1) 201.18/55.08 MARK(isNat(x1)) -> ISNATACTIVE(x1) 201.18/55.08 MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) 201.18/55.08 MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) 201.18/55.08 MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) 201.18/55.08 MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) 201.18/55.08 MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) 201.18/55.08 MARK(length(x1)) -> MARK(x1) 201.18/55.08 MARK(cons(x1, x2)) -> MARK(x1) 201.18/55.08 MARK(s(x1)) -> MARK(x1) 201.18/55.08 U21ACTIVE(tt, V1) -> U22ACTIVE(isNatActive(V1)) 201.18/55.08 U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) 201.18/55.08 U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) 201.18/55.08 U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.08 U42ACTIVE(tt, V2) -> U43ACTIVE(isNatIListActive(V2)) 201.18/55.08 U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) 201.18/55.08 U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) 201.18/55.08 U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.08 U52ACTIVE(tt, V2) -> U53ACTIVE(isNatListActive(V2)) 201.18/55.08 U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) 201.18/55.08 U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) 201.18/55.08 U61ACTIVE(tt, L) -> MARK(L) 201.18/55.08 ANDACTIVE(tt, X) -> MARK(X) 201.18/55.08 ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) 201.18/55.08 ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.08 ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.08 ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.08 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.08 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.08 ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) 201.18/55.08 ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.08 ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.08 ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.08 ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.08 LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.08 LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) 201.18/55.08 LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) 201.18/55.08 LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) 201.18/55.08 201.18/55.08 The TRS R consists of the following rules: 201.18/55.08 201.18/55.08 mark(zeros) -> zerosActive 201.18/55.08 zerosActive -> zeros 201.18/55.08 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.08 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.08 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.08 U22Active(x1) -> U22(x1) 201.18/55.08 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.08 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.08 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.08 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.08 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.08 U43Active(x1) -> U43(x1) 201.18/55.08 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.08 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.08 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.08 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.08 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.08 U53Active(x1) -> U53(x1) 201.18/55.08 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.08 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.08 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.08 andActive(x1, x2) -> and(x1, x2) 201.18/55.08 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.08 isNatActive(x1) -> isNat(x1) 201.18/55.08 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.08 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.08 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.08 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.08 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.08 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (21) DependencyGraphProof (EQUIVALENT) 201.18/55.09 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 7 less nodes. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (22) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) 201.18/55.09 U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ANDACTIVE(tt, X) -> MARK(X) 201.18/55.09 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U22(x1)) -> MARK(x1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) 201.18/55.09 U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U42(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U43(x1)) -> MARK(x1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) 201.18/55.09 U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U52(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U53(x1)) -> MARK(x1) 201.18/55.09 MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) 201.18/55.09 U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 U61ACTIVE(tt, L) -> MARK(L) 201.18/55.09 MARK(U61(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) 201.18/55.09 MARK(and(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(isNat(x1)) -> ISNATACTIVE(x1) 201.18/55.09 MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) 201.18/55.09 MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) 201.18/55.09 MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) 201.18/55.09 MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) 201.18/55.09 MARK(length(x1)) -> MARK(x1) 201.18/55.09 MARK(cons(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(s(x1)) -> MARK(x1) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (23) QDPOrderProof (EQUIVALENT) 201.18/55.09 We use the reduction pair processor [LPAR04,JAR06]. 201.18/55.09 201.18/55.09 201.18/55.09 The following pairs can be oriented strictly and are deleted. 201.18/55.09 201.18/55.09 U61ACTIVE(tt, L) -> MARK(L) 201.18/55.09 MARK(U61(x1, x2)) -> MARK(x1) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> ANDACTIVE(isNatListActive(L), isNatIListKind(L)) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> ISNATLISTACTIVE(L) 201.18/55.09 MARK(length(x1)) -> MARK(x1) 201.18/55.09 The remaining pairs can at least be oriented weakly. 201.18/55.09 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 201.18/55.09 201.18/55.09 POL( ANDACTIVE_2(x_1, x_2) ) = 2x_2 201.18/55.09 POL( LENGTHACTIVE_1(x_1) ) = x_1 + 2 201.18/55.09 POL( U21ACTIVE_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( U41ACTIVE_3(x_1, ..., x_3) ) = max{0, -2} 201.18/55.09 POL( U42ACTIVE_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( U51ACTIVE_3(x_1, ..., x_3) ) = max{0, -2} 201.18/55.09 POL( U52ACTIVE_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( U61ACTIVE_2(x_1, x_2) ) = 2x_2 + 2 201.18/55.09 POL( mark_1(x_1) ) = 2x_1 201.18/55.09 POL( zeros ) = 0 201.18/55.09 POL( zerosActive ) = 0 201.18/55.09 POL( U21_2(x_1, x_2) ) = 2x_1 201.18/55.09 POL( U21Active_2(x_1, x_2) ) = 2x_1 201.18/55.09 POL( U22_1(x_1) ) = x_1 201.18/55.09 POL( U22Active_1(x_1) ) = x_1 201.18/55.09 POL( U41_3(x_1, ..., x_3) ) = x_1 201.18/55.09 POL( U41Active_3(x_1, ..., x_3) ) = x_1 201.18/55.09 POL( U42_2(x_1, x_2) ) = 2x_1 201.18/55.09 POL( U42Active_2(x_1, x_2) ) = 2x_1 201.18/55.09 POL( U43_1(x_1) ) = x_1 201.18/55.09 POL( U43Active_1(x_1) ) = x_1 201.18/55.09 POL( U51_3(x_1, ..., x_3) ) = x_1 201.18/55.09 POL( U51Active_3(x_1, ..., x_3) ) = x_1 201.18/55.09 POL( U52_2(x_1, x_2) ) = 2x_1 201.18/55.09 POL( U52Active_2(x_1, x_2) ) = 2x_1 201.18/55.09 POL( U53_1(x_1) ) = 2x_1 201.18/55.09 POL( U53Active_1(x_1) ) = 2x_1 201.18/55.09 POL( U61_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 201.18/55.09 POL( U61Active_2(x_1, x_2) ) = 2x_1 + 2x_2 + 1 201.18/55.09 POL( and_2(x_1, x_2) ) = 2x_1 + 2x_2 201.18/55.09 POL( andActive_2(x_1, x_2) ) = 2x_1 + 2x_2 201.18/55.09 POL( tt ) = 0 201.18/55.09 POL( isNatIListKind_1(x_1) ) = 0 201.18/55.09 POL( isNatIListKindActive_1(x_1) ) = 0 201.18/55.09 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 201.18/55.09 POL( isNatKindActive_1(x_1) ) = 0 201.18/55.09 POL( isNatKind_1(x_1) ) = 0 201.18/55.09 POL( length_1(x_1) ) = x_1 + 1 201.18/55.09 POL( s_1(x_1) ) = x_1 201.18/55.09 POL( isNat_1(x_1) ) = 0 201.18/55.09 POL( isNatActive_1(x_1) ) = 0 201.18/55.09 POL( isNatIList_1(x_1) ) = 0 201.18/55.09 POL( isNatIListActive_1(x_1) ) = 0 201.18/55.09 POL( isNatList_1(x_1) ) = 0 201.18/55.09 POL( isNatListActive_1(x_1) ) = 0 201.18/55.09 POL( lengthActive_1(x_1) ) = x_1 + 1 201.18/55.09 POL( 0 ) = 0 201.18/55.09 POL( nil ) = 0 201.18/55.09 POL( MARK_1(x_1) ) = 2x_1 201.18/55.09 POL( ISNATACTIVE_1(x_1) ) = 0 201.18/55.09 POL( ISNATKINDACTIVE_1(x_1) ) = 0 201.18/55.09 POL( ISNATILISTKINDACTIVE_1(x_1) ) = 0 201.18/55.09 POL( ISNATILISTACTIVE_1(x_1) ) = 0 201.18/55.09 POL( ISNATLISTACTIVE_1(x_1) ) = 0 201.18/55.09 201.18/55.09 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 zerosActive -> zeros 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 201.18/55.09 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (24) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) 201.18/55.09 U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ANDACTIVE(tt, X) -> MARK(X) 201.18/55.09 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U22(x1)) -> MARK(x1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) 201.18/55.09 U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U42(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U43(x1)) -> MARK(x1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) 201.18/55.09 U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U52(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U53(x1)) -> MARK(x1) 201.18/55.09 MARK(U61(x1, x2)) -> U61ACTIVE(mark(x1), x2) 201.18/55.09 U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) 201.18/55.09 MARK(and(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(isNat(x1)) -> ISNATACTIVE(x1) 201.18/55.09 MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) 201.18/55.09 MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) 201.18/55.09 MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) 201.18/55.09 MARK(length(x1)) -> LENGTHACTIVE(mark(x1)) 201.18/55.09 MARK(cons(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(s(x1)) -> MARK(x1) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (25) DependencyGraphProof (EQUIVALENT) 201.18/55.09 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (26) 201.18/55.09 Complex Obligation (AND) 201.18/55.09 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (27) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (28) QDPOrderProof (EQUIVALENT) 201.18/55.09 We use the reduction pair processor [LPAR04,JAR06]. 201.18/55.09 201.18/55.09 201.18/55.09 The following pairs can be oriented strictly and are deleted. 201.18/55.09 201.18/55.09 U61ACTIVE(tt, L) -> LENGTHACTIVE(mark(L)) 201.18/55.09 The remaining pairs can at least be oriented weakly. 201.18/55.09 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 201.18/55.09 201.18/55.09 POL( LENGTHACTIVE_1(x_1) ) = 0 201.18/55.09 POL( U61ACTIVE_2(x_1, x_2) ) = max{0, 2x_1 - 2} 201.18/55.09 POL( isNatListActive_1(x_1) ) = 0 201.18/55.09 POL( isNatList_1(x_1) ) = 0 201.18/55.09 POL( cons_2(x_1, x_2) ) = max{0, x_1 - 2} 201.18/55.09 POL( U51Active_3(x_1, ..., x_3) ) = max{0, -2} 201.18/55.09 POL( andActive_2(x_1, x_2) ) = x_1 201.18/55.09 POL( isNatKindActive_1(x_1) ) = 2 201.18/55.09 POL( isNatIListKind_1(x_1) ) = 0 201.18/55.09 POL( and_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( mark_1(x_1) ) = 2 201.18/55.09 POL( tt ) = 2 201.18/55.09 POL( isNatIListKindActive_1(x_1) ) = 2 201.18/55.09 POL( isNatKind_1(x_1) ) = 0 201.18/55.09 POL( length_1(x_1) ) = 0 201.18/55.09 POL( s_1(x_1) ) = max{0, x_1 - 2} 201.18/55.09 POL( zeros ) = 0 201.18/55.09 POL( zerosActive ) = 0 201.18/55.09 POL( U21_2(x_1, x_2) ) = 0 201.18/55.09 POL( U21Active_2(x_1, x_2) ) = 2 201.18/55.09 POL( U22_1(x_1) ) = 2 201.18/55.09 POL( U22Active_1(x_1) ) = 2 201.18/55.09 POL( U41_3(x_1, ..., x_3) ) = 0 201.18/55.09 POL( U41Active_3(x_1, ..., x_3) ) = max{0, -2} 201.18/55.09 POL( U42_2(x_1, x_2) ) = 0 201.18/55.09 POL( U42Active_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( U43_1(x_1) ) = 0 201.18/55.09 POL( U43Active_1(x_1) ) = x_1 201.18/55.09 POL( U51_3(x_1, ..., x_3) ) = 0 201.18/55.09 POL( U52_2(x_1, x_2) ) = 0 201.18/55.09 POL( U52Active_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( U53_1(x_1) ) = 0 201.18/55.09 POL( U53Active_1(x_1) ) = x_1 201.18/55.09 POL( U61_2(x_1, x_2) ) = 0 201.18/55.09 POL( U61Active_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( isNat_1(x_1) ) = 0 201.18/55.09 POL( isNatActive_1(x_1) ) = 2 201.18/55.09 POL( isNatIList_1(x_1) ) = 0 201.18/55.09 POL( isNatIListActive_1(x_1) ) = 0 201.18/55.09 POL( lengthActive_1(x_1) ) = max{0, -2} 201.18/55.09 POL( 0 ) = 0 201.18/55.09 POL( nil ) = 0 201.18/55.09 201.18/55.09 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 201.18/55.09 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 zerosActive -> zeros 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 201.18/55.09 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (29) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 LENGTHACTIVE(cons(N, L)) -> U61ACTIVE(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (30) DependencyGraphProof (EQUIVALENT) 201.18/55.09 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (31) 201.18/55.09 TRUE 201.18/55.09 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (32) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ANDACTIVE(tt, X) -> MARK(X) 201.18/55.09 MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U22(x1)) -> MARK(x1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) 201.18/55.09 U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U42(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U43(x1)) -> MARK(x1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) 201.18/55.09 U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U52(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U53(x1)) -> MARK(x1) 201.18/55.09 MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) 201.18/55.09 MARK(and(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(isNat(x1)) -> ISNATACTIVE(x1) 201.18/55.09 MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) 201.18/55.09 MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) 201.18/55.09 MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) 201.18/55.09 MARK(cons(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(s(x1)) -> MARK(x1) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (33) QDPOrderProof (EQUIVALENT) 201.18/55.09 We use the reduction pair processor [LPAR04,JAR06]. 201.18/55.09 201.18/55.09 201.18/55.09 The following pairs can be oriented strictly and are deleted. 201.18/55.09 201.18/55.09 ISNATACTIVE(s(V1)) -> U21ACTIVE(isNatKindActive(V1), V1) 201.18/55.09 ISNATACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(length(V1)) -> ISNATILISTKINDACTIVE(V1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ANDACTIVE(tt, X) -> MARK(X) 201.18/55.09 MARK(U21(x1, x2)) -> U21ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U41(x1, x2, x3)) -> U41ACTIVE(mark(x1), x2, x3) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> U42ACTIVE(isNatActive(V1), V2) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> U41ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U41ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 ISNATILISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 ISNATKINDACTIVE(s(V1)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U41(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U42(x1, x2)) -> U42ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U42(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> U51ACTIVE(mark(x1), x2, x3) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> U51ACTIVE(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> ISNATACTIVE(V1) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(U51(x1, x2, x3)) -> MARK(x1) 201.18/55.09 MARK(U52(x1, x2)) -> U52ACTIVE(mark(x1), x2) 201.18/55.09 MARK(U52(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U53(x1)) -> MARK(x1) 201.18/55.09 MARK(and(x1, x2)) -> ANDACTIVE(mark(x1), x2) 201.18/55.09 MARK(and(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(isNat(x1)) -> ISNATACTIVE(x1) 201.18/55.09 MARK(isNatIList(x1)) -> ISNATILISTACTIVE(x1) 201.18/55.09 MARK(isNatIListKind(x1)) -> ISNATILISTKINDACTIVE(x1) 201.18/55.09 ISNATILISTKINDACTIVE(cons(V1, V2)) -> ISNATKINDACTIVE(V1) 201.18/55.09 MARK(isNatKind(x1)) -> ISNATKINDACTIVE(x1) 201.18/55.09 MARK(isNatList(x1)) -> ISNATLISTACTIVE(x1) 201.18/55.09 MARK(cons(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(s(x1)) -> MARK(x1) 201.18/55.09 The remaining pairs can at least be oriented weakly. 201.18/55.09 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 201.18/55.09 201.18/55.09 POL( ANDACTIVE_2(x_1, x_2) ) = 2x_2 + 2 201.18/55.09 POL( U21ACTIVE_2(x_1, x_2) ) = 2x_2 201.18/55.09 POL( U41ACTIVE_3(x_1, ..., x_3) ) = 2x_2 + 2x_3 + 2 201.18/55.09 POL( U42ACTIVE_2(x_1, x_2) ) = 2x_2 + 1 201.18/55.09 POL( U51ACTIVE_3(x_1, ..., x_3) ) = 2x_2 + x_3 + 2 201.18/55.09 POL( U52ACTIVE_2(x_1, x_2) ) = x_2 + 2 201.18/55.09 POL( isNatKindActive_1(x_1) ) = 0 201.18/55.09 POL( isNatKind_1(x_1) ) = 2x_1 + 1 201.18/55.09 POL( 0 ) = 0 201.18/55.09 POL( tt ) = 0 201.18/55.09 POL( mark_1(x_1) ) = 0 201.18/55.09 POL( and_2(x_1, x_2) ) = x_1 + x_2 + 1 201.18/55.09 POL( andActive_2(x_1, x_2) ) = max{0, -2} 201.18/55.09 POL( isNatIListKind_1(x_1) ) = x_1 + 1 201.18/55.09 POL( isNatIListKindActive_1(x_1) ) = 2 201.18/55.09 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 201.18/55.09 POL( length_1(x_1) ) = 2x_1 + 1 201.18/55.09 POL( s_1(x_1) ) = 2x_1 + 1 201.18/55.09 POL( zeros ) = 1 201.18/55.09 POL( zerosActive ) = 0 201.18/55.09 POL( U21_2(x_1, x_2) ) = x_1 + x_2 201.18/55.09 POL( U21Active_2(x_1, x_2) ) = max{0, 2x_2 - 2} 201.18/55.09 POL( U22_1(x_1) ) = 2x_1 201.18/55.09 POL( U22Active_1(x_1) ) = 2 201.18/55.09 POL( U41_3(x_1, ..., x_3) ) = x_1 + x_2 + x_3 + 2 201.18/55.09 POL( U41Active_3(x_1, ..., x_3) ) = max{0, 2x_2 + x_3 - 2} 201.18/55.09 POL( U42_2(x_1, x_2) ) = x_1 + 2x_2 + 1 201.18/55.09 POL( U42Active_2(x_1, x_2) ) = max{0, x_2 - 2} 201.18/55.09 POL( U43_1(x_1) ) = x_1 201.18/55.09 POL( U43Active_1(x_1) ) = max{0, -2} 201.18/55.09 POL( U51_3(x_1, ..., x_3) ) = x_1 + 2x_2 + x_3 + 2 201.18/55.09 POL( U51Active_3(x_1, ..., x_3) ) = max{0, 2x_2 - 2} 201.18/55.09 POL( U52_2(x_1, x_2) ) = x_1 + 2x_2 + 2 201.18/55.09 POL( U52Active_2(x_1, x_2) ) = max{0, x_2 - 2} 201.18/55.09 POL( U53_1(x_1) ) = x_1 + 2 201.18/55.09 POL( U53Active_1(x_1) ) = max{0, x_1 - 2} 201.18/55.09 POL( U61_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 201.18/55.09 POL( U61Active_2(x_1, x_2) ) = max{0, x_2 - 2} 201.18/55.09 POL( isNat_1(x_1) ) = 2x_1 201.18/55.09 POL( isNatActive_1(x_1) ) = 0 201.18/55.09 POL( isNatIList_1(x_1) ) = x_1 + 1 201.18/55.09 POL( isNatIListActive_1(x_1) ) = 2x_1 201.18/55.09 POL( isNatList_1(x_1) ) = x_1 + 2 201.18/55.09 POL( isNatListActive_1(x_1) ) = x_1 201.18/55.09 POL( lengthActive_1(x_1) ) = x_1 + 2 201.18/55.09 POL( nil ) = 0 201.18/55.09 POL( ISNATACTIVE_1(x_1) ) = 2x_1 201.18/55.09 POL( ISNATKINDACTIVE_1(x_1) ) = 2x_1 201.18/55.09 POL( ISNATILISTKINDACTIVE_1(x_1) ) = 2x_1 + 1 201.18/55.09 POL( MARK_1(x_1) ) = 2x_1 + 1 201.18/55.09 POL( ISNATILISTACTIVE_1(x_1) ) = 2x_1 + 1 201.18/55.09 POL( ISNATLISTACTIVE_1(x_1) ) = x_1 + 2 201.18/55.09 201.18/55.09 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 201.18/55.09 none 201.18/55.09 201.18/55.09 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (34) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 U21ACTIVE(tt, V1) -> ISNATACTIVE(V1) 201.18/55.09 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U22(x1)) -> MARK(x1) 201.18/55.09 U42ACTIVE(tt, V2) -> ISNATILISTACTIVE(V2) 201.18/55.09 MARK(U43(x1)) -> MARK(x1) 201.18/55.09 U51ACTIVE(tt, V1, V2) -> U52ACTIVE(isNatActive(V1), V2) 201.18/55.09 U52ACTIVE(tt, V2) -> ISNATLISTACTIVE(V2) 201.18/55.09 ISNATLISTACTIVE(cons(V1, V2)) -> ANDACTIVE(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (35) DependencyGraphProof (EQUIVALENT) 201.18/55.09 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (36) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 MARK(U22(x1)) -> MARK(x1) 201.18/55.09 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U43(x1)) -> MARK(x1) 201.18/55.09 201.18/55.09 The TRS R consists of the following rules: 201.18/55.09 201.18/55.09 mark(zeros) -> zerosActive 201.18/55.09 zerosActive -> zeros 201.18/55.09 mark(U21(x1, x2)) -> U21Active(mark(x1), x2) 201.18/55.09 U21Active(x1, x2) -> U21(x1, x2) 201.18/55.09 mark(U22(x1)) -> U22Active(mark(x1)) 201.18/55.09 U22Active(x1) -> U22(x1) 201.18/55.09 mark(U41(x1, x2, x3)) -> U41Active(mark(x1), x2, x3) 201.18/55.09 U41Active(x1, x2, x3) -> U41(x1, x2, x3) 201.18/55.09 mark(U42(x1, x2)) -> U42Active(mark(x1), x2) 201.18/55.09 U42Active(x1, x2) -> U42(x1, x2) 201.18/55.09 mark(U43(x1)) -> U43Active(mark(x1)) 201.18/55.09 U43Active(x1) -> U43(x1) 201.18/55.09 mark(U51(x1, x2, x3)) -> U51Active(mark(x1), x2, x3) 201.18/55.09 U51Active(x1, x2, x3) -> U51(x1, x2, x3) 201.18/55.09 mark(U52(x1, x2)) -> U52Active(mark(x1), x2) 201.18/55.09 U52Active(x1, x2) -> U52(x1, x2) 201.18/55.09 mark(U53(x1)) -> U53Active(mark(x1)) 201.18/55.09 U53Active(x1) -> U53(x1) 201.18/55.09 mark(U61(x1, x2)) -> U61Active(mark(x1), x2) 201.18/55.09 U61Active(x1, x2) -> U61(x1, x2) 201.18/55.09 mark(and(x1, x2)) -> andActive(mark(x1), x2) 201.18/55.09 andActive(x1, x2) -> and(x1, x2) 201.18/55.09 mark(isNat(x1)) -> isNatActive(x1) 201.18/55.09 isNatActive(x1) -> isNat(x1) 201.18/55.09 mark(isNatIList(x1)) -> isNatIListActive(x1) 201.18/55.09 isNatIListActive(x1) -> isNatIList(x1) 201.18/55.09 mark(isNatIListKind(x1)) -> isNatIListKindActive(x1) 201.18/55.09 isNatIListKindActive(x1) -> isNatIListKind(x1) 201.18/55.09 mark(isNatKind(x1)) -> isNatKindActive(x1) 201.18/55.09 isNatKindActive(x1) -> isNatKind(x1) 201.18/55.09 mark(isNatList(x1)) -> isNatListActive(x1) 201.18/55.09 isNatListActive(x1) -> isNatList(x1) 201.18/55.09 mark(length(x1)) -> lengthActive(mark(x1)) 201.18/55.09 lengthActive(x1) -> length(x1) 201.18/55.09 mark(cons(x1, x2)) -> cons(mark(x1), x2) 201.18/55.09 mark(0) -> 0 201.18/55.09 mark(tt) -> tt 201.18/55.09 mark(s(x1)) -> s(mark(x1)) 201.18/55.09 mark(nil) -> nil 201.18/55.09 zerosActive -> cons(0, zeros) 201.18/55.09 U21Active(tt, V1) -> U22Active(isNatActive(V1)) 201.18/55.09 U22Active(tt) -> tt 201.18/55.09 U41Active(tt, V1, V2) -> U42Active(isNatActive(V1), V2) 201.18/55.09 U42Active(tt, V2) -> U43Active(isNatIListActive(V2)) 201.18/55.09 U43Active(tt) -> tt 201.18/55.09 U51Active(tt, V1, V2) -> U52Active(isNatActive(V1), V2) 201.18/55.09 U52Active(tt, V2) -> U53Active(isNatListActive(V2)) 201.18/55.09 U53Active(tt) -> tt 201.18/55.09 U61Active(tt, L) -> s(lengthActive(mark(L))) 201.18/55.09 andActive(tt, X) -> mark(X) 201.18/55.09 isNatActive(0) -> tt 201.18/55.09 isNatActive(s(V1)) -> U21Active(isNatKindActive(V1), V1) 201.18/55.09 isNatIListActive(cons(V1, V2)) -> U41Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 isNatIListKindActive(nil) -> tt 201.18/55.09 isNatIListKindActive(zeros) -> tt 201.18/55.09 isNatIListKindActive(cons(V1, V2)) -> andActive(isNatKindActive(V1), isNatIListKind(V2)) 201.18/55.09 isNatKindActive(0) -> tt 201.18/55.09 isNatKindActive(length(V1)) -> isNatIListKindActive(V1) 201.18/55.09 isNatKindActive(s(V1)) -> isNatKindActive(V1) 201.18/55.09 isNatListActive(cons(V1, V2)) -> U51Active(andActive(isNatKindActive(V1), isNatIListKind(V2)), V1, V2) 201.18/55.09 lengthActive(cons(N, L)) -> U61Active(andActive(andActive(isNatListActive(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 201.18/55.09 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (37) UsableRulesProof (EQUIVALENT) 201.18/55.09 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. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (38) 201.18/55.09 Obligation: 201.18/55.09 Q DP problem: 201.18/55.09 The TRS P consists of the following rules: 201.18/55.09 201.18/55.09 MARK(U22(x1)) -> MARK(x1) 201.18/55.09 MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 MARK(U43(x1)) -> MARK(x1) 201.18/55.09 201.18/55.09 R is empty. 201.18/55.09 Q is empty. 201.18/55.09 We have to consider all minimal (P,Q,R)-chains. 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (39) QDPSizeChangeProof (EQUIVALENT) 201.18/55.09 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. 201.18/55.09 201.18/55.09 From the DPs we obtained the following set of size-change graphs: 201.18/55.09 *MARK(U22(x1)) -> MARK(x1) 201.18/55.09 The graph contains the following edges 1 > 1 201.18/55.09 201.18/55.09 201.18/55.09 *MARK(U21(x1, x2)) -> MARK(x1) 201.18/55.09 The graph contains the following edges 1 > 1 201.18/55.09 201.18/55.09 201.18/55.09 *MARK(U43(x1)) -> MARK(x1) 201.18/55.09 The graph contains the following edges 1 > 1 201.18/55.09 201.18/55.09 201.18/55.09 ---------------------------------------- 201.18/55.09 201.18/55.09 (40) 201.18/55.09 YES 201.18/55.14 EOF