30.58/11.44 YES 30.91/11.49 proof of /export/starexec/sandbox/benchmark/theBenchmark.xml 30.91/11.49 # AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty 30.91/11.49 30.91/11.49 30.91/11.49 Termination w.r.t. Q of the given QTRS could be proven: 30.91/11.49 30.91/11.49 (0) QTRS 30.91/11.49 (1) DependencyPairsProof [EQUIVALENT, 107 ms] 30.91/11.49 (2) QDP 30.91/11.49 (3) DependencyGraphProof [EQUIVALENT, 0 ms] 30.91/11.49 (4) QDP 30.91/11.49 (5) QDPOrderProof [EQUIVALENT, 353 ms] 30.91/11.49 (6) QDP 30.91/11.49 (7) DependencyGraphProof [EQUIVALENT, 0 ms] 30.91/11.49 (8) AND 30.91/11.49 (9) QDP 30.91/11.49 (10) QDPOrderProof [EQUIVALENT, 198 ms] 30.91/11.49 (11) QDP 30.91/11.49 (12) QDPOrderProof [EQUIVALENT, 242 ms] 30.91/11.49 (13) QDP 30.91/11.49 (14) DependencyGraphProof [EQUIVALENT, 0 ms] 30.91/11.49 (15) QDP 30.91/11.49 (16) UsableRulesProof [EQUIVALENT, 0 ms] 30.91/11.49 (17) QDP 30.91/11.49 (18) QReductionProof [EQUIVALENT, 0 ms] 30.91/11.49 (19) QDP 30.91/11.49 (20) QDPSizeChangeProof [EQUIVALENT, 0 ms] 30.91/11.49 (21) YES 30.91/11.49 (22) QDP 30.91/11.49 (23) QDPQMonotonicMRRProof [EQUIVALENT, 205 ms] 30.91/11.49 (24) QDP 30.91/11.49 (25) UsableRulesProof [EQUIVALENT, 0 ms] 30.91/11.49 (26) QDP 30.91/11.49 (27) QReductionProof [EQUIVALENT, 0 ms] 30.91/11.49 (28) QDP 30.91/11.49 (29) QDPQMonotonicMRRProof [EQUIVALENT, 107 ms] 30.91/11.49 (30) QDP 30.91/11.49 (31) DependencyGraphProof [EQUIVALENT, 0 ms] 30.91/11.49 (32) TRUE 30.91/11.49 30.91/11.49 30.91/11.49 ---------------------------------------- 30.91/11.49 30.91/11.49 (0) 30.91/11.49 Obligation: 30.91/11.49 Q restricted rewrite system: 30.91/11.49 The TRS R consists of the following rules: 30.91/11.49 30.91/11.49 a__zeros -> cons(0, zeros) 30.91/11.49 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.49 a__U12(tt) -> tt 30.91/11.49 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.49 a__U22(tt) -> tt 30.91/11.49 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.49 a__U32(tt) -> tt 30.91/11.49 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.49 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.49 a__U43(tt) -> tt 30.91/11.49 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.49 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.49 a__U53(tt) -> tt 30.91/11.49 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.49 a__and(tt, X) -> mark(X) 30.91/11.49 a__isNat(0) -> tt 30.91/11.49 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.49 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.49 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.49 a__isNatIList(zeros) -> tt 30.91/11.49 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 a__isNatIListKind(nil) -> tt 30.91/11.49 a__isNatIListKind(zeros) -> tt 30.91/11.49 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 a__isNatKind(0) -> tt 30.91/11.49 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.49 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.49 a__isNatList(nil) -> tt 30.91/11.49 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 a__length(nil) -> 0 30.91/11.49 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.49 mark(zeros) -> a__zeros 30.91/11.49 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.49 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.49 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.49 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.49 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.49 mark(isNat(X)) -> a__isNat(X) 30.91/11.49 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.49 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.49 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.49 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.49 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.49 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.49 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.49 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.49 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.49 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.49 mark(length(X)) -> a__length(mark(X)) 30.91/11.49 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.49 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.49 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.49 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.49 mark(0) -> 0 30.91/11.49 mark(tt) -> tt 30.91/11.49 mark(s(X)) -> s(mark(X)) 30.91/11.49 mark(nil) -> nil 30.91/11.49 a__zeros -> zeros 30.91/11.49 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.49 a__U12(X) -> U12(X) 30.91/11.49 a__isNatList(X) -> isNatList(X) 30.91/11.49 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.49 a__U22(X) -> U22(X) 30.91/11.49 a__isNat(X) -> isNat(X) 30.91/11.49 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.49 a__U32(X) -> U32(X) 30.91/11.49 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.49 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.49 a__U43(X) -> U43(X) 30.91/11.49 a__isNatIList(X) -> isNatIList(X) 30.91/11.49 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.49 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.49 a__U53(X) -> U53(X) 30.91/11.49 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.49 a__length(X) -> length(X) 30.91/11.49 a__and(X1, X2) -> and(X1, X2) 30.91/11.49 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.49 a__isNatKind(X) -> isNatKind(X) 30.91/11.49 30.91/11.49 The set Q consists of the following terms: 30.91/11.49 30.91/11.49 a__zeros 30.91/11.49 a__isNatIList(x0) 30.91/11.49 mark(zeros) 30.91/11.49 mark(U11(x0, x1)) 30.91/11.49 mark(U12(x0)) 30.91/11.49 mark(isNatList(x0)) 30.91/11.49 mark(U21(x0, x1)) 30.91/11.49 mark(U22(x0)) 30.91/11.49 mark(isNat(x0)) 30.91/11.49 mark(U31(x0, x1)) 30.91/11.49 mark(U32(x0)) 30.91/11.49 mark(U41(x0, x1, x2)) 30.91/11.49 mark(U42(x0, x1)) 30.91/11.49 mark(U43(x0)) 30.91/11.49 mark(isNatIList(x0)) 30.91/11.49 mark(U51(x0, x1, x2)) 30.91/11.49 mark(U52(x0, x1)) 30.91/11.49 mark(U53(x0)) 30.91/11.49 mark(U61(x0, x1)) 30.91/11.49 mark(length(x0)) 30.91/11.49 mark(and(x0, x1)) 30.91/11.49 mark(isNatIListKind(x0)) 30.91/11.49 mark(isNatKind(x0)) 30.91/11.49 mark(cons(x0, x1)) 30.91/11.49 mark(0) 30.91/11.49 mark(tt) 30.91/11.49 mark(s(x0)) 30.91/11.49 mark(nil) 30.91/11.49 a__U11(x0, x1) 30.91/11.49 a__U12(x0) 30.91/11.49 a__isNatList(x0) 30.91/11.49 a__U21(x0, x1) 30.91/11.49 a__U22(x0) 30.91/11.49 a__isNat(x0) 30.91/11.49 a__U31(x0, x1) 30.91/11.49 a__U32(x0) 30.91/11.49 a__U41(x0, x1, x2) 30.91/11.49 a__U42(x0, x1) 30.91/11.49 a__U43(x0) 30.91/11.49 a__U51(x0, x1, x2) 30.91/11.49 a__U52(x0, x1) 30.91/11.49 a__U53(x0) 30.91/11.49 a__U61(x0, x1) 30.91/11.49 a__length(x0) 30.91/11.49 a__and(x0, x1) 30.91/11.49 a__isNatIListKind(x0) 30.91/11.49 a__isNatKind(x0) 30.91/11.49 30.91/11.49 30.91/11.49 ---------------------------------------- 30.91/11.49 30.91/11.49 (1) DependencyPairsProof (EQUIVALENT) 30.91/11.49 Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem. 30.91/11.49 ---------------------------------------- 30.91/11.49 30.91/11.49 (2) 30.91/11.49 Obligation: 30.91/11.49 Q DP problem: 30.91/11.49 The TRS P consists of the following rules: 30.91/11.49 30.91/11.49 A__U11(tt, V1) -> A__U12(a__isNatList(V1)) 30.91/11.49 A__U11(tt, V1) -> A__ISNATLIST(V1) 30.91/11.49 A__U21(tt, V1) -> A__U22(a__isNat(V1)) 30.91/11.49 A__U21(tt, V1) -> A__ISNAT(V1) 30.91/11.49 A__U31(tt, V) -> A__U32(a__isNatList(V)) 30.91/11.49 A__U31(tt, V) -> A__ISNATLIST(V) 30.91/11.49 A__U41(tt, V1, V2) -> A__U42(a__isNat(V1), V2) 30.91/11.49 A__U41(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.49 A__U42(tt, V2) -> A__U43(a__isNatIList(V2)) 30.91/11.49 A__U42(tt, V2) -> A__ISNATILIST(V2) 30.91/11.49 A__U51(tt, V1, V2) -> A__U52(a__isNat(V1), V2) 30.91/11.49 A__U51(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.49 A__U52(tt, V2) -> A__U53(a__isNatList(V2)) 30.91/11.49 A__U52(tt, V2) -> A__ISNATLIST(V2) 30.91/11.49 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.49 A__U61(tt, L) -> MARK(L) 30.91/11.49 A__AND(tt, X) -> MARK(X) 30.91/11.49 A__ISNAT(length(V1)) -> A__U11(a__isNatIListKind(V1), V1) 30.91/11.49 A__ISNAT(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.49 A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) 30.91/11.49 A__ISNAT(s(V1)) -> A__ISNATKIND(V1) 30.91/11.49 A__ISNATILIST(V) -> A__U31(a__isNatIListKind(V), V) 30.91/11.49 A__ISNATILIST(V) -> A__ISNATILISTKIND(V) 30.91/11.49 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 A__ISNATILIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 A__ISNATILIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.49 A__ISNATILISTKIND(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 A__ISNATILISTKIND(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.49 A__ISNATKIND(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.49 A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) 30.91/11.49 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 A__ISNATLIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 A__ISNATLIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__AND(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__AND(a__isNatList(L), isNatIListKind(L)) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 30.91/11.49 MARK(zeros) -> A__ZEROS 30.91/11.49 MARK(U11(X1, X2)) -> A__U11(mark(X1), X2) 30.91/11.49 MARK(U11(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U12(X)) -> A__U12(mark(X)) 30.91/11.49 MARK(U12(X)) -> MARK(X) 30.91/11.49 MARK(isNatList(X)) -> A__ISNATLIST(X) 30.91/11.49 MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) 30.91/11.49 MARK(U21(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U22(X)) -> A__U22(mark(X)) 30.91/11.49 MARK(U22(X)) -> MARK(X) 30.91/11.49 MARK(isNat(X)) -> A__ISNAT(X) 30.91/11.49 MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) 30.91/11.49 MARK(U31(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U32(X)) -> A__U32(mark(X)) 30.91/11.49 MARK(U32(X)) -> MARK(X) 30.91/11.49 MARK(U41(X1, X2, X3)) -> A__U41(mark(X1), X2, X3) 30.91/11.49 MARK(U41(X1, X2, X3)) -> MARK(X1) 30.91/11.49 MARK(U42(X1, X2)) -> A__U42(mark(X1), X2) 30.91/11.49 MARK(U42(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U43(X)) -> A__U43(mark(X)) 30.91/11.49 MARK(U43(X)) -> MARK(X) 30.91/11.49 MARK(isNatIList(X)) -> A__ISNATILIST(X) 30.91/11.49 MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) 30.91/11.49 MARK(U51(X1, X2, X3)) -> MARK(X1) 30.91/11.49 MARK(U52(X1, X2)) -> A__U52(mark(X1), X2) 30.91/11.49 MARK(U52(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U53(X)) -> A__U53(mark(X)) 30.91/11.49 MARK(U53(X)) -> MARK(X) 30.91/11.49 MARK(U61(X1, X2)) -> A__U61(mark(X1), X2) 30.91/11.49 MARK(U61(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(length(X)) -> A__LENGTH(mark(X)) 30.91/11.49 MARK(length(X)) -> MARK(X) 30.91/11.49 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 30.91/11.49 MARK(and(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(isNatIListKind(X)) -> A__ISNATILISTKIND(X) 30.91/11.49 MARK(isNatKind(X)) -> A__ISNATKIND(X) 30.91/11.49 MARK(cons(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(s(X)) -> MARK(X) 30.91/11.49 30.91/11.49 The TRS R consists of the following rules: 30.91/11.49 30.91/11.49 a__zeros -> cons(0, zeros) 30.91/11.49 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.49 a__U12(tt) -> tt 30.91/11.49 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.49 a__U22(tt) -> tt 30.91/11.49 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.49 a__U32(tt) -> tt 30.91/11.49 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.49 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.49 a__U43(tt) -> tt 30.91/11.49 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.49 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.49 a__U53(tt) -> tt 30.91/11.49 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.49 a__and(tt, X) -> mark(X) 30.91/11.49 a__isNat(0) -> tt 30.91/11.49 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.49 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.49 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.49 a__isNatIList(zeros) -> tt 30.91/11.49 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 a__isNatIListKind(nil) -> tt 30.91/11.49 a__isNatIListKind(zeros) -> tt 30.91/11.49 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 a__isNatKind(0) -> tt 30.91/11.49 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.49 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.49 a__isNatList(nil) -> tt 30.91/11.49 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 a__length(nil) -> 0 30.91/11.49 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.49 mark(zeros) -> a__zeros 30.91/11.49 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.49 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.49 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.49 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.49 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.49 mark(isNat(X)) -> a__isNat(X) 30.91/11.49 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.49 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.49 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.49 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.49 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.49 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.49 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.49 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.49 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.49 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.49 mark(length(X)) -> a__length(mark(X)) 30.91/11.49 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.49 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.49 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.49 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.49 mark(0) -> 0 30.91/11.49 mark(tt) -> tt 30.91/11.49 mark(s(X)) -> s(mark(X)) 30.91/11.49 mark(nil) -> nil 30.91/11.49 a__zeros -> zeros 30.91/11.49 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.49 a__U12(X) -> U12(X) 30.91/11.49 a__isNatList(X) -> isNatList(X) 30.91/11.49 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.49 a__U22(X) -> U22(X) 30.91/11.49 a__isNat(X) -> isNat(X) 30.91/11.49 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.49 a__U32(X) -> U32(X) 30.91/11.49 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.49 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.49 a__U43(X) -> U43(X) 30.91/11.49 a__isNatIList(X) -> isNatIList(X) 30.91/11.49 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.49 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.49 a__U53(X) -> U53(X) 30.91/11.49 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.49 a__length(X) -> length(X) 30.91/11.49 a__and(X1, X2) -> and(X1, X2) 30.91/11.49 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.49 a__isNatKind(X) -> isNatKind(X) 30.91/11.49 30.91/11.49 The set Q consists of the following terms: 30.91/11.49 30.91/11.49 a__zeros 30.91/11.49 a__isNatIList(x0) 30.91/11.49 mark(zeros) 30.91/11.49 mark(U11(x0, x1)) 30.91/11.49 mark(U12(x0)) 30.91/11.49 mark(isNatList(x0)) 30.91/11.49 mark(U21(x0, x1)) 30.91/11.49 mark(U22(x0)) 30.91/11.49 mark(isNat(x0)) 30.91/11.49 mark(U31(x0, x1)) 30.91/11.49 mark(U32(x0)) 30.91/11.49 mark(U41(x0, x1, x2)) 30.91/11.49 mark(U42(x0, x1)) 30.91/11.49 mark(U43(x0)) 30.91/11.49 mark(isNatIList(x0)) 30.91/11.49 mark(U51(x0, x1, x2)) 30.91/11.49 mark(U52(x0, x1)) 30.91/11.49 mark(U53(x0)) 30.91/11.49 mark(U61(x0, x1)) 30.91/11.49 mark(length(x0)) 30.91/11.49 mark(and(x0, x1)) 30.91/11.49 mark(isNatIListKind(x0)) 30.91/11.49 mark(isNatKind(x0)) 30.91/11.49 mark(cons(x0, x1)) 30.91/11.49 mark(0) 30.91/11.49 mark(tt) 30.91/11.49 mark(s(x0)) 30.91/11.49 mark(nil) 30.91/11.49 a__U11(x0, x1) 30.91/11.49 a__U12(x0) 30.91/11.49 a__isNatList(x0) 30.91/11.49 a__U21(x0, x1) 30.91/11.49 a__U22(x0) 30.91/11.49 a__isNat(x0) 30.91/11.49 a__U31(x0, x1) 30.91/11.49 a__U32(x0) 30.91/11.49 a__U41(x0, x1, x2) 30.91/11.49 a__U42(x0, x1) 30.91/11.49 a__U43(x0) 30.91/11.49 a__U51(x0, x1, x2) 30.91/11.49 a__U52(x0, x1) 30.91/11.49 a__U53(x0) 30.91/11.49 a__U61(x0, x1) 30.91/11.49 a__length(x0) 30.91/11.49 a__and(x0, x1) 30.91/11.49 a__isNatIListKind(x0) 30.91/11.49 a__isNatKind(x0) 30.91/11.49 30.91/11.49 We have to consider all minimal (P,Q,R)-chains. 30.91/11.49 ---------------------------------------- 30.91/11.49 30.91/11.49 (3) DependencyGraphProof (EQUIVALENT) 30.91/11.49 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 11 less nodes. 30.91/11.49 ---------------------------------------- 30.91/11.49 30.91/11.49 (4) 30.91/11.49 Obligation: 30.91/11.49 Q DP problem: 30.91/11.49 The TRS P consists of the following rules: 30.91/11.49 30.91/11.49 A__U11(tt, V1) -> A__ISNATLIST(V1) 30.91/11.49 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 A__U51(tt, V1, V2) -> A__U52(a__isNat(V1), V2) 30.91/11.49 A__U52(tt, V2) -> A__ISNATLIST(V2) 30.91/11.49 A__ISNATLIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 A__AND(tt, X) -> MARK(X) 30.91/11.49 MARK(U11(X1, X2)) -> A__U11(mark(X1), X2) 30.91/11.49 MARK(U11(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U12(X)) -> MARK(X) 30.91/11.49 MARK(isNatList(X)) -> A__ISNATLIST(X) 30.91/11.49 A__ISNATLIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.49 A__ISNATKIND(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.49 A__ISNATILISTKIND(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 A__ISNATILISTKIND(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.49 A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) 30.91/11.49 MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) 30.91/11.49 A__U21(tt, V1) -> A__ISNAT(V1) 30.91/11.49 A__ISNAT(length(V1)) -> A__U11(a__isNatIListKind(V1), V1) 30.91/11.49 A__ISNAT(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.49 A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) 30.91/11.49 A__ISNAT(s(V1)) -> A__ISNATKIND(V1) 30.91/11.49 MARK(U21(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U22(X)) -> MARK(X) 30.91/11.49 MARK(isNat(X)) -> A__ISNAT(X) 30.91/11.49 MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) 30.91/11.49 A__U31(tt, V) -> A__ISNATLIST(V) 30.91/11.49 MARK(U31(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U32(X)) -> MARK(X) 30.91/11.49 MARK(U41(X1, X2, X3)) -> A__U41(mark(X1), X2, X3) 30.91/11.49 A__U41(tt, V1, V2) -> A__U42(a__isNat(V1), V2) 30.91/11.49 A__U42(tt, V2) -> A__ISNATILIST(V2) 30.91/11.49 A__ISNATILIST(V) -> A__U31(a__isNatIListKind(V), V) 30.91/11.49 A__ISNATILIST(V) -> A__ISNATILISTKIND(V) 30.91/11.49 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.49 A__U41(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.49 A__ISNATILIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.49 A__ISNATILIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.49 MARK(U41(X1, X2, X3)) -> MARK(X1) 30.91/11.49 MARK(U42(X1, X2)) -> A__U42(mark(X1), X2) 30.91/11.49 MARK(U42(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U43(X)) -> MARK(X) 30.91/11.49 MARK(isNatIList(X)) -> A__ISNATILIST(X) 30.91/11.49 MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) 30.91/11.49 A__U51(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.49 MARK(U51(X1, X2, X3)) -> MARK(X1) 30.91/11.49 MARK(U52(X1, X2)) -> A__U52(mark(X1), X2) 30.91/11.49 MARK(U52(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(U53(X)) -> MARK(X) 30.91/11.49 MARK(U61(X1, X2)) -> A__U61(mark(X1), X2) 30.91/11.49 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.49 A__U61(tt, L) -> MARK(L) 30.91/11.49 MARK(U61(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(length(X)) -> A__LENGTH(mark(X)) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__AND(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__AND(a__isNatList(L), isNatIListKind(L)) 30.91/11.49 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 30.91/11.49 MARK(length(X)) -> MARK(X) 30.91/11.49 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 30.91/11.49 MARK(and(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(isNatIListKind(X)) -> A__ISNATILISTKIND(X) 30.91/11.49 MARK(isNatKind(X)) -> A__ISNATKIND(X) 30.91/11.49 MARK(cons(X1, X2)) -> MARK(X1) 30.91/11.49 MARK(s(X)) -> MARK(X) 30.91/11.49 30.91/11.49 The TRS R consists of the following rules: 30.91/11.49 30.91/11.49 a__zeros -> cons(0, zeros) 30.91/11.49 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.51 a__U12(tt) -> tt 30.91/11.51 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.51 a__U22(tt) -> tt 30.91/11.51 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.51 a__U32(tt) -> tt 30.91/11.51 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.51 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.51 a__U43(tt) -> tt 30.91/11.51 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.51 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.51 a__U53(tt) -> tt 30.91/11.51 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.51 a__and(tt, X) -> mark(X) 30.91/11.51 a__isNat(0) -> tt 30.91/11.51 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.51 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.51 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.51 a__isNatIList(zeros) -> tt 30.91/11.51 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 a__isNatIListKind(nil) -> tt 30.91/11.51 a__isNatIListKind(zeros) -> tt 30.91/11.51 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.51 a__isNatKind(0) -> tt 30.91/11.51 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.51 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.51 a__isNatList(nil) -> tt 30.91/11.51 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 a__length(nil) -> 0 30.91/11.51 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.51 mark(zeros) -> a__zeros 30.91/11.51 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.51 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.51 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.51 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.51 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.51 mark(isNat(X)) -> a__isNat(X) 30.91/11.51 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.51 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.51 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.51 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.51 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.51 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.51 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.51 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.51 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.51 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.51 mark(length(X)) -> a__length(mark(X)) 30.91/11.51 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.51 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.51 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.51 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.51 mark(0) -> 0 30.91/11.51 mark(tt) -> tt 30.91/11.51 mark(s(X)) -> s(mark(X)) 30.91/11.51 mark(nil) -> nil 30.91/11.51 a__zeros -> zeros 30.91/11.51 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.51 a__U12(X) -> U12(X) 30.91/11.51 a__isNatList(X) -> isNatList(X) 30.91/11.51 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.51 a__U22(X) -> U22(X) 30.91/11.51 a__isNat(X) -> isNat(X) 30.91/11.51 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.51 a__U32(X) -> U32(X) 30.91/11.51 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.51 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.51 a__U43(X) -> U43(X) 30.91/11.51 a__isNatIList(X) -> isNatIList(X) 30.91/11.51 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.51 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.51 a__U53(X) -> U53(X) 30.91/11.51 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.51 a__length(X) -> length(X) 30.91/11.51 a__and(X1, X2) -> and(X1, X2) 30.91/11.51 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.51 a__isNatKind(X) -> isNatKind(X) 30.91/11.51 30.91/11.51 The set Q consists of the following terms: 30.91/11.51 30.91/11.51 a__zeros 30.91/11.51 a__isNatIList(x0) 30.91/11.51 mark(zeros) 30.91/11.51 mark(U11(x0, x1)) 30.91/11.51 mark(U12(x0)) 30.91/11.51 mark(isNatList(x0)) 30.91/11.51 mark(U21(x0, x1)) 30.91/11.51 mark(U22(x0)) 30.91/11.51 mark(isNat(x0)) 30.91/11.51 mark(U31(x0, x1)) 30.91/11.51 mark(U32(x0)) 30.91/11.51 mark(U41(x0, x1, x2)) 30.91/11.51 mark(U42(x0, x1)) 30.91/11.51 mark(U43(x0)) 30.91/11.51 mark(isNatIList(x0)) 30.91/11.51 mark(U51(x0, x1, x2)) 30.91/11.51 mark(U52(x0, x1)) 30.91/11.51 mark(U53(x0)) 30.91/11.51 mark(U61(x0, x1)) 30.91/11.51 mark(length(x0)) 30.91/11.51 mark(and(x0, x1)) 30.91/11.51 mark(isNatIListKind(x0)) 30.91/11.51 mark(isNatKind(x0)) 30.91/11.51 mark(cons(x0, x1)) 30.91/11.51 mark(0) 30.91/11.51 mark(tt) 30.91/11.51 mark(s(x0)) 30.91/11.51 mark(nil) 30.91/11.51 a__U11(x0, x1) 30.91/11.51 a__U12(x0) 30.91/11.51 a__isNatList(x0) 30.91/11.51 a__U21(x0, x1) 30.91/11.51 a__U22(x0) 30.91/11.51 a__isNat(x0) 30.91/11.51 a__U31(x0, x1) 30.91/11.51 a__U32(x0) 30.91/11.51 a__U41(x0, x1, x2) 30.91/11.51 a__U42(x0, x1) 30.91/11.51 a__U43(x0) 30.91/11.51 a__U51(x0, x1, x2) 30.91/11.51 a__U52(x0, x1) 30.91/11.51 a__U53(x0) 30.91/11.51 a__U61(x0, x1) 30.91/11.51 a__length(x0) 30.91/11.51 a__and(x0, x1) 30.91/11.51 a__isNatIListKind(x0) 30.91/11.51 a__isNatKind(x0) 30.91/11.51 30.91/11.51 We have to consider all minimal (P,Q,R)-chains. 30.91/11.51 ---------------------------------------- 30.91/11.51 30.91/11.51 (5) QDPOrderProof (EQUIVALENT) 30.91/11.51 We use the reduction pair processor [LPAR04,JAR06]. 30.91/11.51 30.91/11.51 30.91/11.51 The following pairs can be oriented strictly and are deleted. 30.91/11.51 30.91/11.51 MARK(U61(X1, X2)) -> A__U61(mark(X1), X2) 30.91/11.51 MARK(U61(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(length(X)) -> A__LENGTH(mark(X)) 30.91/11.51 MARK(length(X)) -> MARK(X) 30.91/11.51 The remaining pairs can at least be oriented weakly. 30.91/11.51 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 30.91/11.51 30.91/11.51 POL( A__AND_2(x_1, x_2) ) = x_2 30.91/11.51 POL( A__LENGTH_1(x_1) ) = x_1 30.91/11.51 POL( A__U11_2(x_1, x_2) ) = max{0, -2} 30.91/11.51 POL( A__U21_2(x_1, x_2) ) = max{0, -2} 30.91/11.51 POL( A__U31_2(x_1, x_2) ) = max{0, -2} 30.91/11.51 POL( A__U41_3(x_1, ..., x_3) ) = max{0, -2} 30.91/11.51 POL( A__U42_2(x_1, x_2) ) = max{0, -2} 30.91/11.51 POL( A__U51_3(x_1, ..., x_3) ) = max{0, -2} 30.91/11.51 POL( A__U52_2(x_1, x_2) ) = max{0, -2} 30.91/11.51 POL( A__U61_2(x_1, x_2) ) = x_2 30.91/11.51 POL( a__isNatKind_1(x_1) ) = 0 30.91/11.51 POL( 0 ) = 0 30.91/11.51 POL( tt ) = 0 30.91/11.51 POL( mark_1(x_1) ) = x_1 30.91/11.51 POL( and_2(x_1, x_2) ) = x_1 + x_2 30.91/11.51 POL( a__and_2(x_1, x_2) ) = x_1 + x_2 30.91/11.51 POL( isNatIListKind_1(x_1) ) = 0 30.91/11.51 POL( a__isNatIListKind_1(x_1) ) = 0 30.91/11.51 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 30.91/11.51 POL( isNatKind_1(x_1) ) = 0 30.91/11.51 POL( length_1(x_1) ) = x_1 + 1 30.91/11.51 POL( s_1(x_1) ) = x_1 30.91/11.51 POL( a__isNat_1(x_1) ) = 0 30.91/11.51 POL( a__U11_2(x_1, x_2) ) = x_1 30.91/11.51 POL( a__U21_2(x_1, x_2) ) = 2x_1 30.91/11.51 POL( isNat_1(x_1) ) = 0 30.91/11.51 POL( zeros ) = 0 30.91/11.51 POL( a__zeros ) = 0 30.91/11.51 POL( U11_2(x_1, x_2) ) = x_1 30.91/11.51 POL( U12_1(x_1) ) = x_1 30.91/11.51 POL( a__U12_1(x_1) ) = x_1 30.91/11.51 POL( isNatList_1(x_1) ) = 0 30.91/11.51 POL( a__isNatList_1(x_1) ) = 0 30.91/11.51 POL( U21_2(x_1, x_2) ) = 2x_1 30.91/11.51 POL( U22_1(x_1) ) = 2x_1 30.91/11.51 POL( a__U22_1(x_1) ) = 2x_1 30.91/11.51 POL( U31_2(x_1, x_2) ) = x_1 30.91/11.51 POL( a__U31_2(x_1, x_2) ) = x_1 30.91/11.51 POL( U32_1(x_1) ) = 2x_1 30.91/11.51 POL( a__U32_1(x_1) ) = 2x_1 30.91/11.51 POL( U41_3(x_1, ..., x_3) ) = x_1 30.91/11.51 POL( a__U41_3(x_1, ..., x_3) ) = x_1 30.91/11.51 POL( U42_2(x_1, x_2) ) = x_1 30.91/11.51 POL( a__U42_2(x_1, x_2) ) = x_1 30.91/11.51 POL( U43_1(x_1) ) = 2x_1 30.91/11.51 POL( a__U43_1(x_1) ) = 2x_1 30.91/11.51 POL( isNatIList_1(x_1) ) = 0 30.91/11.51 POL( a__isNatIList_1(x_1) ) = 0 30.91/11.51 POL( U51_3(x_1, ..., x_3) ) = 2x_1 30.91/11.51 POL( a__U51_3(x_1, ..., x_3) ) = 2x_1 30.91/11.51 POL( U52_2(x_1, x_2) ) = 2x_1 30.91/11.51 POL( a__U52_2(x_1, x_2) ) = 2x_1 30.91/11.51 POL( U53_1(x_1) ) = 2x_1 30.91/11.51 POL( a__U53_1(x_1) ) = 2x_1 30.91/11.51 POL( U61_2(x_1, x_2) ) = 2x_1 + x_2 + 1 30.91/11.51 POL( a__U61_2(x_1, x_2) ) = 2x_1 + x_2 + 1 30.91/11.51 POL( a__length_1(x_1) ) = x_1 + 1 30.91/11.51 POL( nil ) = 0 30.91/11.51 POL( A__ISNATLIST_1(x_1) ) = 0 30.91/11.51 POL( MARK_1(x_1) ) = x_1 30.91/11.51 POL( A__ISNATKIND_1(x_1) ) = 0 30.91/11.51 POL( A__ISNATILISTKIND_1(x_1) ) = 0 30.91/11.51 POL( A__ISNAT_1(x_1) ) = 0 30.91/11.51 POL( A__ISNATILIST_1(x_1) ) = 0 30.91/11.51 30.91/11.51 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 30.91/11.51 30.91/11.51 a__isNatKind(0) -> tt 30.91/11.51 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.51 a__and(tt, X) -> mark(X) 30.91/11.51 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.51 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.51 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.51 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.51 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.51 a__isNatKind(X) -> isNatKind(X) 30.91/11.51 a__and(X1, X2) -> and(X1, X2) 30.91/11.51 a__isNat(0) -> tt 30.91/11.51 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.51 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.51 a__isNat(X) -> isNat(X) 30.91/11.51 mark(zeros) -> a__zeros 30.91/11.51 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.51 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.51 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.51 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.51 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.51 mark(isNat(X)) -> a__isNat(X) 30.91/11.51 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.51 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.51 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.51 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.51 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.51 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.51 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.51 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.51 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.51 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.51 mark(length(X)) -> a__length(mark(X)) 30.91/11.51 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.51 mark(0) -> 0 30.91/11.51 mark(tt) -> tt 30.91/11.51 mark(s(X)) -> s(mark(X)) 30.91/11.51 mark(nil) -> nil 30.91/11.51 a__isNatIListKind(nil) -> tt 30.91/11.51 a__isNatIListKind(zeros) -> tt 30.91/11.51 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.51 a__isNatList(nil) -> tt 30.91/11.51 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 a__isNatList(X) -> isNatList(X) 30.91/11.51 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.51 a__U12(tt) -> tt 30.91/11.51 a__U12(X) -> U12(X) 30.91/11.51 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.51 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.51 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.51 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.51 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.51 a__U22(tt) -> tt 30.91/11.51 a__U22(X) -> U22(X) 30.91/11.51 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.51 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.51 a__U32(tt) -> tt 30.91/11.51 a__U32(X) -> U32(X) 30.91/11.51 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.51 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.51 a__U43(tt) -> tt 30.91/11.51 a__U43(X) -> U43(X) 30.91/11.51 a__isNatIList(zeros) -> tt 30.91/11.51 a__isNatIList(X) -> isNatIList(X) 30.91/11.51 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.51 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.51 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.51 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.51 a__U53(tt) -> tt 30.91/11.51 a__U53(X) -> U53(X) 30.91/11.51 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.51 a__length(nil) -> 0 30.91/11.51 a__length(X) -> length(X) 30.91/11.51 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.51 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.51 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.51 a__zeros -> cons(0, zeros) 30.91/11.51 a__zeros -> zeros 30.91/11.51 30.91/11.51 30.91/11.51 ---------------------------------------- 30.91/11.51 30.91/11.51 (6) 30.91/11.51 Obligation: 30.91/11.51 Q DP problem: 30.91/11.51 The TRS P consists of the following rules: 30.91/11.51 30.91/11.51 A__U11(tt, V1) -> A__ISNATLIST(V1) 30.91/11.51 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 A__U51(tt, V1, V2) -> A__U52(a__isNat(V1), V2) 30.91/11.51 A__U52(tt, V2) -> A__ISNATLIST(V2) 30.91/11.51 A__ISNATLIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.51 A__AND(tt, X) -> MARK(X) 30.91/11.51 MARK(U11(X1, X2)) -> A__U11(mark(X1), X2) 30.91/11.51 MARK(U11(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(U12(X)) -> MARK(X) 30.91/11.51 MARK(isNatList(X)) -> A__ISNATLIST(X) 30.91/11.51 A__ISNATLIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.51 A__ISNATKIND(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.51 A__ISNATILISTKIND(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.51 A__ISNATILISTKIND(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.51 A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) 30.91/11.51 MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) 30.91/11.51 A__U21(tt, V1) -> A__ISNAT(V1) 30.91/11.51 A__ISNAT(length(V1)) -> A__U11(a__isNatIListKind(V1), V1) 30.91/11.51 A__ISNAT(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.51 A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) 30.91/11.51 A__ISNAT(s(V1)) -> A__ISNATKIND(V1) 30.91/11.51 MARK(U21(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(U22(X)) -> MARK(X) 30.91/11.51 MARK(isNat(X)) -> A__ISNAT(X) 30.91/11.51 MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) 30.91/11.51 A__U31(tt, V) -> A__ISNATLIST(V) 30.91/11.51 MARK(U31(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(U32(X)) -> MARK(X) 30.91/11.51 MARK(U41(X1, X2, X3)) -> A__U41(mark(X1), X2, X3) 30.91/11.51 A__U41(tt, V1, V2) -> A__U42(a__isNat(V1), V2) 30.91/11.51 A__U42(tt, V2) -> A__ISNATILIST(V2) 30.91/11.51 A__ISNATILIST(V) -> A__U31(a__isNatIListKind(V), V) 30.91/11.51 A__ISNATILIST(V) -> A__ISNATILISTKIND(V) 30.91/11.51 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 A__U41(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.51 A__ISNATILIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.51 A__ISNATILIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.51 MARK(U41(X1, X2, X3)) -> MARK(X1) 30.91/11.51 MARK(U42(X1, X2)) -> A__U42(mark(X1), X2) 30.91/11.51 MARK(U42(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(U43(X)) -> MARK(X) 30.91/11.51 MARK(isNatIList(X)) -> A__ISNATILIST(X) 30.91/11.51 MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) 30.91/11.51 A__U51(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.51 MARK(U51(X1, X2, X3)) -> MARK(X1) 30.91/11.51 MARK(U52(X1, X2)) -> A__U52(mark(X1), X2) 30.91/11.51 MARK(U52(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(U53(X)) -> MARK(X) 30.91/11.51 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.51 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.51 A__U61(tt, L) -> MARK(L) 30.91/11.51 A__LENGTH(cons(N, L)) -> A__AND(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))) 30.91/11.51 A__LENGTH(cons(N, L)) -> A__AND(a__isNatList(L), isNatIListKind(L)) 30.91/11.51 A__LENGTH(cons(N, L)) -> A__ISNATLIST(L) 30.91/11.51 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 30.91/11.51 MARK(and(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(isNatIListKind(X)) -> A__ISNATILISTKIND(X) 30.91/11.51 MARK(isNatKind(X)) -> A__ISNATKIND(X) 30.91/11.51 MARK(cons(X1, X2)) -> MARK(X1) 30.91/11.51 MARK(s(X)) -> MARK(X) 30.91/11.51 30.91/11.51 The TRS R consists of the following rules: 30.91/11.51 30.91/11.51 a__zeros -> cons(0, zeros) 30.91/11.51 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.51 a__U12(tt) -> tt 30.91/11.51 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.51 a__U22(tt) -> tt 30.91/11.51 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.51 a__U32(tt) -> tt 30.91/11.51 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.51 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.51 a__U43(tt) -> tt 30.91/11.51 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.51 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.51 a__U53(tt) -> tt 30.91/11.51 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.51 a__and(tt, X) -> mark(X) 30.91/11.51 a__isNat(0) -> tt 30.91/11.51 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.51 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.51 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.51 a__isNatIList(zeros) -> tt 30.91/11.51 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 a__isNatIListKind(nil) -> tt 30.91/11.51 a__isNatIListKind(zeros) -> tt 30.91/11.51 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.51 a__isNatKind(0) -> tt 30.91/11.51 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.51 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.51 a__isNatList(nil) -> tt 30.91/11.51 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.51 a__length(nil) -> 0 30.91/11.51 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.51 mark(zeros) -> a__zeros 30.91/11.51 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.51 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.51 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.51 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.51 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.51 mark(isNat(X)) -> a__isNat(X) 30.91/11.51 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.51 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.51 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.51 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.51 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.51 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.51 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.51 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.51 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.51 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.51 mark(length(X)) -> a__length(mark(X)) 30.91/11.51 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.51 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.51 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.51 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.51 mark(0) -> 0 30.91/11.51 mark(tt) -> tt 30.91/11.51 mark(s(X)) -> s(mark(X)) 30.91/11.51 mark(nil) -> nil 30.91/11.51 a__zeros -> zeros 30.91/11.51 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.51 a__U12(X) -> U12(X) 30.91/11.51 a__isNatList(X) -> isNatList(X) 30.91/11.51 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.51 a__U22(X) -> U22(X) 30.91/11.51 a__isNat(X) -> isNat(X) 30.91/11.51 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.51 a__U32(X) -> U32(X) 30.91/11.51 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.51 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.51 a__U43(X) -> U43(X) 30.91/11.51 a__isNatIList(X) -> isNatIList(X) 30.91/11.51 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.51 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.51 a__U53(X) -> U53(X) 30.91/11.51 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.51 a__length(X) -> length(X) 30.91/11.51 a__and(X1, X2) -> and(X1, X2) 30.91/11.51 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.51 a__isNatKind(X) -> isNatKind(X) 30.91/11.51 30.91/11.51 The set Q consists of the following terms: 30.91/11.51 30.91/11.51 a__zeros 30.91/11.51 a__isNatIList(x0) 30.91/11.51 mark(zeros) 30.91/11.51 mark(U11(x0, x1)) 30.91/11.51 mark(U12(x0)) 30.91/11.51 mark(isNatList(x0)) 30.91/11.51 mark(U21(x0, x1)) 30.91/11.51 mark(U22(x0)) 30.91/11.51 mark(isNat(x0)) 30.91/11.51 mark(U31(x0, x1)) 30.91/11.51 mark(U32(x0)) 30.91/11.51 mark(U41(x0, x1, x2)) 30.91/11.51 mark(U42(x0, x1)) 30.91/11.51 mark(U43(x0)) 30.91/11.51 mark(isNatIList(x0)) 30.91/11.51 mark(U51(x0, x1, x2)) 30.91/11.51 mark(U52(x0, x1)) 30.91/11.51 mark(U53(x0)) 30.91/11.51 mark(U61(x0, x1)) 30.91/11.51 mark(length(x0)) 30.91/11.51 mark(and(x0, x1)) 30.91/11.51 mark(isNatIListKind(x0)) 30.91/11.51 mark(isNatKind(x0)) 30.91/11.51 mark(cons(x0, x1)) 30.91/11.51 mark(0) 30.91/11.51 mark(tt) 30.91/11.51 mark(s(x0)) 30.91/11.51 mark(nil) 30.91/11.51 a__U11(x0, x1) 30.91/11.51 a__U12(x0) 30.91/11.51 a__isNatList(x0) 30.91/11.51 a__U21(x0, x1) 30.91/11.51 a__U22(x0) 30.91/11.51 a__isNat(x0) 30.91/11.51 a__U31(x0, x1) 30.91/11.51 a__U32(x0) 30.91/11.51 a__U41(x0, x1, x2) 30.91/11.51 a__U42(x0, x1) 30.91/11.51 a__U43(x0) 30.91/11.51 a__U51(x0, x1, x2) 30.91/11.51 a__U52(x0, x1) 30.91/11.51 a__U53(x0) 30.91/11.51 a__U61(x0, x1) 30.91/11.51 a__length(x0) 30.91/11.52 a__and(x0, x1) 30.91/11.52 a__isNatIListKind(x0) 30.91/11.52 a__isNatKind(x0) 30.91/11.52 30.91/11.52 We have to consider all minimal (P,Q,R)-chains. 30.91/11.52 ---------------------------------------- 30.91/11.52 30.91/11.52 (7) DependencyGraphProof (EQUIVALENT) 30.91/11.52 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 4 less nodes. 30.91/11.52 ---------------------------------------- 30.91/11.52 30.91/11.52 (8) 30.91/11.52 Complex Obligation (AND) 30.91/11.52 30.91/11.52 ---------------------------------------- 30.91/11.52 30.91/11.52 (9) 30.91/11.52 Obligation: 30.91/11.52 Q DP problem: 30.91/11.52 The TRS P consists of the following rules: 30.91/11.52 30.91/11.52 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 A__U51(tt, V1, V2) -> A__U52(a__isNat(V1), V2) 30.91/11.52 A__U52(tt, V2) -> A__ISNATLIST(V2) 30.91/11.52 A__ISNATLIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 A__AND(tt, X) -> MARK(X) 30.91/11.52 MARK(U11(X1, X2)) -> A__U11(mark(X1), X2) 30.91/11.52 A__U11(tt, V1) -> A__ISNATLIST(V1) 30.91/11.52 A__ISNATLIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.52 A__ISNATKIND(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.52 A__ISNATILISTKIND(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 A__ISNATILISTKIND(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.52 A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) 30.91/11.52 MARK(U11(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U12(X)) -> MARK(X) 30.91/11.52 MARK(isNatList(X)) -> A__ISNATLIST(X) 30.91/11.52 MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) 30.91/11.52 A__U21(tt, V1) -> A__ISNAT(V1) 30.91/11.52 A__ISNAT(length(V1)) -> A__U11(a__isNatIListKind(V1), V1) 30.91/11.52 A__ISNAT(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.52 A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) 30.91/11.52 A__ISNAT(s(V1)) -> A__ISNATKIND(V1) 30.91/11.52 MARK(U21(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U22(X)) -> MARK(X) 30.91/11.52 MARK(isNat(X)) -> A__ISNAT(X) 30.91/11.52 MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) 30.91/11.52 A__U31(tt, V) -> A__ISNATLIST(V) 30.91/11.52 MARK(U31(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U32(X)) -> MARK(X) 30.91/11.52 MARK(U41(X1, X2, X3)) -> A__U41(mark(X1), X2, X3) 30.91/11.52 A__U41(tt, V1, V2) -> A__U42(a__isNat(V1), V2) 30.91/11.52 A__U42(tt, V2) -> A__ISNATILIST(V2) 30.91/11.52 A__ISNATILIST(V) -> A__U31(a__isNatIListKind(V), V) 30.91/11.52 A__ISNATILIST(V) -> A__ISNATILISTKIND(V) 30.91/11.52 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 A__U41(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.52 A__ISNATILIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 A__ISNATILIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.52 MARK(U41(X1, X2, X3)) -> MARK(X1) 30.91/11.52 MARK(U42(X1, X2)) -> A__U42(mark(X1), X2) 30.91/11.52 MARK(U42(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U43(X)) -> MARK(X) 30.91/11.52 MARK(isNatIList(X)) -> A__ISNATILIST(X) 30.91/11.52 MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) 30.91/11.52 A__U51(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.52 MARK(U51(X1, X2, X3)) -> MARK(X1) 30.91/11.52 MARK(U52(X1, X2)) -> A__U52(mark(X1), X2) 30.91/11.52 MARK(U52(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U53(X)) -> MARK(X) 30.91/11.52 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 30.91/11.52 MARK(and(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(isNatIListKind(X)) -> A__ISNATILISTKIND(X) 30.91/11.52 MARK(isNatKind(X)) -> A__ISNATKIND(X) 30.91/11.52 MARK(cons(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(s(X)) -> MARK(X) 30.91/11.52 30.91/11.52 The TRS R consists of the following rules: 30.91/11.52 30.91/11.52 a__zeros -> cons(0, zeros) 30.91/11.52 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.52 a__U12(tt) -> tt 30.91/11.52 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.52 a__U22(tt) -> tt 30.91/11.52 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.52 a__U32(tt) -> tt 30.91/11.52 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.52 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.52 a__U43(tt) -> tt 30.91/11.52 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.52 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.52 a__U53(tt) -> tt 30.91/11.52 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.52 a__and(tt, X) -> mark(X) 30.91/11.52 a__isNat(0) -> tt 30.91/11.52 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.52 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.52 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.52 a__isNatIList(zeros) -> tt 30.91/11.52 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 a__isNatIListKind(nil) -> tt 30.91/11.52 a__isNatIListKind(zeros) -> tt 30.91/11.52 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 a__isNatKind(0) -> tt 30.91/11.52 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.52 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.52 a__isNatList(nil) -> tt 30.91/11.52 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 a__length(nil) -> 0 30.91/11.52 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.52 mark(zeros) -> a__zeros 30.91/11.52 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.52 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.52 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.52 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.52 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.52 mark(isNat(X)) -> a__isNat(X) 30.91/11.52 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.52 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.52 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.52 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.52 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.52 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.52 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.52 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.52 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.52 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.52 mark(length(X)) -> a__length(mark(X)) 30.91/11.52 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.52 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.52 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.52 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.52 mark(0) -> 0 30.91/11.52 mark(tt) -> tt 30.91/11.52 mark(s(X)) -> s(mark(X)) 30.91/11.52 mark(nil) -> nil 30.91/11.52 a__zeros -> zeros 30.91/11.52 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.52 a__U12(X) -> U12(X) 30.91/11.52 a__isNatList(X) -> isNatList(X) 30.91/11.52 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.52 a__U22(X) -> U22(X) 30.91/11.52 a__isNat(X) -> isNat(X) 30.91/11.52 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.52 a__U32(X) -> U32(X) 30.91/11.52 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.52 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.52 a__U43(X) -> U43(X) 30.91/11.52 a__isNatIList(X) -> isNatIList(X) 30.91/11.52 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.52 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.52 a__U53(X) -> U53(X) 30.91/11.52 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.52 a__length(X) -> length(X) 30.91/11.52 a__and(X1, X2) -> and(X1, X2) 30.91/11.52 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.52 a__isNatKind(X) -> isNatKind(X) 30.91/11.52 30.91/11.52 The set Q consists of the following terms: 30.91/11.52 30.91/11.52 a__zeros 30.91/11.52 a__isNatIList(x0) 30.91/11.52 mark(zeros) 30.91/11.52 mark(U11(x0, x1)) 30.91/11.52 mark(U12(x0)) 30.91/11.52 mark(isNatList(x0)) 30.91/11.52 mark(U21(x0, x1)) 30.91/11.52 mark(U22(x0)) 30.91/11.52 mark(isNat(x0)) 30.91/11.52 mark(U31(x0, x1)) 30.91/11.52 mark(U32(x0)) 30.91/11.52 mark(U41(x0, x1, x2)) 30.91/11.52 mark(U42(x0, x1)) 30.91/11.52 mark(U43(x0)) 30.91/11.52 mark(isNatIList(x0)) 30.91/11.52 mark(U51(x0, x1, x2)) 30.91/11.52 mark(U52(x0, x1)) 30.91/11.52 mark(U53(x0)) 30.91/11.52 mark(U61(x0, x1)) 30.91/11.52 mark(length(x0)) 30.91/11.52 mark(and(x0, x1)) 30.91/11.52 mark(isNatIListKind(x0)) 30.91/11.52 mark(isNatKind(x0)) 30.91/11.52 mark(cons(x0, x1)) 30.91/11.52 mark(0) 30.91/11.52 mark(tt) 30.91/11.52 mark(s(x0)) 30.91/11.52 mark(nil) 30.91/11.52 a__U11(x0, x1) 30.91/11.52 a__U12(x0) 30.91/11.52 a__isNatList(x0) 30.91/11.52 a__U21(x0, x1) 30.91/11.52 a__U22(x0) 30.91/11.52 a__isNat(x0) 30.91/11.52 a__U31(x0, x1) 30.91/11.52 a__U32(x0) 30.91/11.52 a__U41(x0, x1, x2) 30.91/11.52 a__U42(x0, x1) 30.91/11.52 a__U43(x0) 30.91/11.52 a__U51(x0, x1, x2) 30.91/11.52 a__U52(x0, x1) 30.91/11.52 a__U53(x0) 30.91/11.52 a__U61(x0, x1) 30.91/11.52 a__length(x0) 30.91/11.52 a__and(x0, x1) 30.91/11.52 a__isNatIListKind(x0) 30.91/11.52 a__isNatKind(x0) 30.91/11.52 30.91/11.52 We have to consider all minimal (P,Q,R)-chains. 30.91/11.52 ---------------------------------------- 30.91/11.52 30.91/11.52 (10) QDPOrderProof (EQUIVALENT) 30.91/11.52 We use the reduction pair processor [LPAR04,JAR06]. 30.91/11.52 30.91/11.52 30.91/11.52 The following pairs can be oriented strictly and are deleted. 30.91/11.52 30.91/11.52 MARK(U11(X1, X2)) -> A__U11(mark(X1), X2) 30.91/11.52 MARK(U11(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U12(X)) -> MARK(X) 30.91/11.52 The remaining pairs can at least be oriented weakly. 30.91/11.52 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 30.91/11.52 30.91/11.52 POL( A__AND_2(x_1, x_2) ) = 2x_2 30.91/11.52 POL( A__U11_2(x_1, x_2) ) = max{0, -2} 30.91/11.52 POL( A__U21_2(x_1, x_2) ) = max{0, -2} 30.91/11.52 POL( A__U31_2(x_1, x_2) ) = max{0, -2} 30.91/11.52 POL( A__U41_3(x_1, ..., x_3) ) = max{0, x_1 - 2} 30.91/11.52 POL( A__U42_2(x_1, x_2) ) = max{0, -2} 30.91/11.52 POL( A__U51_3(x_1, ..., x_3) ) = max{0, -2} 30.91/11.52 POL( A__U52_2(x_1, x_2) ) = max{0, -2} 30.91/11.52 POL( a__isNatKind_1(x_1) ) = 0 30.91/11.52 POL( 0 ) = 0 30.91/11.52 POL( tt ) = 0 30.91/11.52 POL( mark_1(x_1) ) = 2x_1 30.91/11.52 POL( and_2(x_1, x_2) ) = 2x_1 + x_2 30.91/11.52 POL( a__and_2(x_1, x_2) ) = 2x_1 + 2x_2 30.91/11.52 POL( isNatIListKind_1(x_1) ) = 0 30.91/11.52 POL( a__isNatIListKind_1(x_1) ) = 0 30.91/11.52 POL( cons_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( isNatKind_1(x_1) ) = 0 30.91/11.52 POL( length_1(x_1) ) = x_1 + 1 30.91/11.52 POL( s_1(x_1) ) = x_1 30.91/11.52 POL( a__isNat_1(x_1) ) = 2x_1 30.91/11.52 POL( a__U11_2(x_1, x_2) ) = x_1 + 2x_2 + 2 30.91/11.52 POL( a__U21_2(x_1, x_2) ) = 2x_1 + 2x_2 30.91/11.52 POL( isNat_1(x_1) ) = 2x_1 30.91/11.52 POL( zeros ) = 0 30.91/11.52 POL( a__zeros ) = 0 30.91/11.52 POL( U11_2(x_1, x_2) ) = x_1 + 2x_2 + 1 30.91/11.52 POL( U12_1(x_1) ) = x_1 + 2 30.91/11.52 POL( a__U12_1(x_1) ) = x_1 + 2 30.91/11.52 POL( isNatList_1(x_1) ) = 2x_1 30.91/11.52 POL( a__isNatList_1(x_1) ) = 2x_1 30.91/11.52 POL( U21_2(x_1, x_2) ) = 2x_1 + x_2 30.91/11.52 POL( U22_1(x_1) ) = x_1 30.91/11.52 POL( a__U22_1(x_1) ) = x_1 30.91/11.52 POL( U31_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( a__U31_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( U32_1(x_1) ) = x_1 30.91/11.52 POL( a__U32_1(x_1) ) = x_1 30.91/11.52 POL( U41_3(x_1, ..., x_3) ) = x_1 + x_2 + 2x_3 30.91/11.52 POL( a__U41_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2x_3 30.91/11.52 POL( U42_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( a__U42_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( U43_1(x_1) ) = x_1 30.91/11.52 POL( a__U43_1(x_1) ) = x_1 30.91/11.52 POL( isNatIList_1(x_1) ) = 2x_1 30.91/11.52 POL( a__isNatIList_1(x_1) ) = 2x_1 30.91/11.52 POL( U51_3(x_1, ..., x_3) ) = x_1 + x_2 + x_3 30.91/11.52 POL( a__U51_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2x_3 30.91/11.52 POL( U52_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( a__U52_2(x_1, x_2) ) = x_1 + 2x_2 30.91/11.52 POL( U53_1(x_1) ) = x_1 30.91/11.52 POL( a__U53_1(x_1) ) = x_1 30.91/11.52 POL( U61_2(x_1, x_2) ) = x_2 + 1 30.91/11.52 POL( a__U61_2(x_1, x_2) ) = 2x_2 + 2 30.91/11.52 POL( a__length_1(x_1) ) = x_1 + 2 30.91/11.52 POL( nil ) = 0 30.91/11.52 POL( A__ISNATLIST_1(x_1) ) = 0 30.91/11.52 POL( MARK_1(x_1) ) = 2x_1 30.91/11.52 POL( A__ISNATKIND_1(x_1) ) = 0 30.91/11.52 POL( A__ISNATILISTKIND_1(x_1) ) = 0 30.91/11.52 POL( A__ISNAT_1(x_1) ) = 0 30.91/11.52 POL( A__ISNATILIST_1(x_1) ) = 0 30.91/11.52 30.91/11.52 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 30.91/11.52 30.91/11.52 a__isNatKind(0) -> tt 30.91/11.52 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.52 a__and(tt, X) -> mark(X) 30.91/11.52 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.52 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.52 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.52 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.52 a__isNatKind(X) -> isNatKind(X) 30.91/11.52 a__and(X1, X2) -> and(X1, X2) 30.91/11.52 a__isNat(0) -> tt 30.91/11.52 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.52 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.52 a__isNat(X) -> isNat(X) 30.91/11.52 mark(zeros) -> a__zeros 30.91/11.52 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.52 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.52 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.52 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.52 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.52 mark(isNat(X)) -> a__isNat(X) 30.91/11.52 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.52 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.52 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.52 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.52 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.52 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.52 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.52 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.52 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.52 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.52 mark(length(X)) -> a__length(mark(X)) 30.91/11.52 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.52 mark(0) -> 0 30.91/11.52 mark(tt) -> tt 30.91/11.52 mark(s(X)) -> s(mark(X)) 30.91/11.52 mark(nil) -> nil 30.91/11.52 a__isNatIListKind(nil) -> tt 30.91/11.52 a__isNatIListKind(zeros) -> tt 30.91/11.52 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.52 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.52 a__U12(tt) -> tt 30.91/11.52 a__U12(X) -> U12(X) 30.91/11.52 a__isNatList(nil) -> tt 30.91/11.52 a__isNatList(X) -> isNatList(X) 30.91/11.52 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.52 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.52 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.52 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.52 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.52 a__U22(tt) -> tt 30.91/11.52 a__U22(X) -> U22(X) 30.91/11.52 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.52 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.52 a__U32(tt) -> tt 30.91/11.52 a__U32(X) -> U32(X) 30.91/11.52 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.52 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.52 a__U43(tt) -> tt 30.91/11.52 a__U43(X) -> U43(X) 30.91/11.52 a__isNatIList(zeros) -> tt 30.91/11.52 a__isNatIList(X) -> isNatIList(X) 30.91/11.52 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.52 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.52 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.52 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.52 a__U53(tt) -> tt 30.91/11.52 a__U53(X) -> U53(X) 30.91/11.52 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.52 a__length(nil) -> 0 30.91/11.52 a__length(X) -> length(X) 30.91/11.52 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.52 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.52 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.52 a__zeros -> cons(0, zeros) 30.91/11.52 a__zeros -> zeros 30.91/11.52 30.91/11.52 30.91/11.52 ---------------------------------------- 30.91/11.52 30.91/11.52 (11) 30.91/11.52 Obligation: 30.91/11.52 Q DP problem: 30.91/11.52 The TRS P consists of the following rules: 30.91/11.52 30.91/11.52 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 A__U51(tt, V1, V2) -> A__U52(a__isNat(V1), V2) 30.91/11.52 A__U52(tt, V2) -> A__ISNATLIST(V2) 30.91/11.52 A__ISNATLIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 A__AND(tt, X) -> MARK(X) 30.91/11.52 A__U11(tt, V1) -> A__ISNATLIST(V1) 30.91/11.52 A__ISNATLIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.52 A__ISNATKIND(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.52 A__ISNATILISTKIND(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 A__ISNATILISTKIND(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.52 A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) 30.91/11.52 MARK(isNatList(X)) -> A__ISNATLIST(X) 30.91/11.52 MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) 30.91/11.52 A__U21(tt, V1) -> A__ISNAT(V1) 30.91/11.52 A__ISNAT(length(V1)) -> A__U11(a__isNatIListKind(V1), V1) 30.91/11.52 A__ISNAT(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.52 A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) 30.91/11.52 A__ISNAT(s(V1)) -> A__ISNATKIND(V1) 30.91/11.52 MARK(U21(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U22(X)) -> MARK(X) 30.91/11.52 MARK(isNat(X)) -> A__ISNAT(X) 30.91/11.52 MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) 30.91/11.52 A__U31(tt, V) -> A__ISNATLIST(V) 30.91/11.52 MARK(U31(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U32(X)) -> MARK(X) 30.91/11.52 MARK(U41(X1, X2, X3)) -> A__U41(mark(X1), X2, X3) 30.91/11.52 A__U41(tt, V1, V2) -> A__U42(a__isNat(V1), V2) 30.91/11.52 A__U42(tt, V2) -> A__ISNATILIST(V2) 30.91/11.52 A__ISNATILIST(V) -> A__U31(a__isNatIListKind(V), V) 30.91/11.52 A__ISNATILIST(V) -> A__ISNATILISTKIND(V) 30.91/11.52 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 A__U41(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.52 A__ISNATILIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 A__ISNATILIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.52 MARK(U41(X1, X2, X3)) -> MARK(X1) 30.91/11.52 MARK(U42(X1, X2)) -> A__U42(mark(X1), X2) 30.91/11.52 MARK(U42(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U43(X)) -> MARK(X) 30.91/11.52 MARK(isNatIList(X)) -> A__ISNATILIST(X) 30.91/11.52 MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) 30.91/11.52 A__U51(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.52 MARK(U51(X1, X2, X3)) -> MARK(X1) 30.91/11.52 MARK(U52(X1, X2)) -> A__U52(mark(X1), X2) 30.91/11.52 MARK(U52(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(U53(X)) -> MARK(X) 30.91/11.52 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 30.91/11.52 MARK(and(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(isNatIListKind(X)) -> A__ISNATILISTKIND(X) 30.91/11.52 MARK(isNatKind(X)) -> A__ISNATKIND(X) 30.91/11.52 MARK(cons(X1, X2)) -> MARK(X1) 30.91/11.52 MARK(s(X)) -> MARK(X) 30.91/11.52 30.91/11.52 The TRS R consists of the following rules: 30.91/11.52 30.91/11.52 a__zeros -> cons(0, zeros) 30.91/11.52 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.52 a__U12(tt) -> tt 30.91/11.52 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.52 a__U22(tt) -> tt 30.91/11.52 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.52 a__U32(tt) -> tt 30.91/11.52 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.52 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.52 a__U43(tt) -> tt 30.91/11.52 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.52 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.52 a__U53(tt) -> tt 30.91/11.52 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.52 a__and(tt, X) -> mark(X) 30.91/11.52 a__isNat(0) -> tt 30.91/11.52 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.52 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.52 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.52 a__isNatIList(zeros) -> tt 30.91/11.52 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 a__isNatIListKind(nil) -> tt 30.91/11.52 a__isNatIListKind(zeros) -> tt 30.91/11.52 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.52 a__isNatKind(0) -> tt 30.91/11.52 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.52 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.52 a__isNatList(nil) -> tt 30.91/11.52 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.52 a__length(nil) -> 0 30.91/11.52 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.53 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.53 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.53 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__zeros -> zeros 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.53 a__U32(X) -> U32(X) 30.91/11.53 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.53 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__isNatIList(X) -> isNatIList(X) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (12) QDPOrderProof (EQUIVALENT) 30.91/11.53 We use the reduction pair processor [LPAR04,JAR06]. 30.91/11.53 30.91/11.53 30.91/11.53 The following pairs can be oriented strictly and are deleted. 30.91/11.53 30.91/11.53 A__ISNATLIST(cons(V1, V2)) -> A__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 A__U52(tt, V2) -> A__ISNATLIST(V2) 30.91/11.53 A__ISNATLIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 A__AND(tt, X) -> MARK(X) 30.91/11.53 A__U11(tt, V1) -> A__ISNATLIST(V1) 30.91/11.53 A__ISNATLIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.53 A__ISNATKIND(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.53 A__ISNATILISTKIND(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 A__ISNATILISTKIND(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.53 A__ISNATKIND(s(V1)) -> A__ISNATKIND(V1) 30.91/11.53 MARK(isNatList(X)) -> A__ISNATLIST(X) 30.91/11.53 MARK(U21(X1, X2)) -> A__U21(mark(X1), X2) 30.91/11.53 A__U21(tt, V1) -> A__ISNAT(V1) 30.91/11.53 A__ISNAT(length(V1)) -> A__U11(a__isNatIListKind(V1), V1) 30.91/11.53 A__ISNAT(length(V1)) -> A__ISNATILISTKIND(V1) 30.91/11.53 A__ISNAT(s(V1)) -> A__U21(a__isNatKind(V1), V1) 30.91/11.53 A__ISNAT(s(V1)) -> A__ISNATKIND(V1) 30.91/11.53 MARK(U21(X1, X2)) -> MARK(X1) 30.91/11.53 MARK(isNat(X)) -> A__ISNAT(X) 30.91/11.53 MARK(U31(X1, X2)) -> A__U31(mark(X1), X2) 30.91/11.53 A__U31(tt, V) -> A__ISNATLIST(V) 30.91/11.53 MARK(U31(X1, X2)) -> MARK(X1) 30.91/11.53 MARK(U32(X)) -> MARK(X) 30.91/11.53 MARK(U41(X1, X2, X3)) -> A__U41(mark(X1), X2, X3) 30.91/11.53 A__ISNATILIST(V) -> A__ISNATILISTKIND(V) 30.91/11.53 A__ISNATILIST(cons(V1, V2)) -> A__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 A__U41(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.53 A__ISNATILIST(cons(V1, V2)) -> A__AND(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 A__ISNATILIST(cons(V1, V2)) -> A__ISNATKIND(V1) 30.91/11.53 MARK(U41(X1, X2, X3)) -> MARK(X1) 30.91/11.53 MARK(U42(X1, X2)) -> A__U42(mark(X1), X2) 30.91/11.53 MARK(U42(X1, X2)) -> MARK(X1) 30.91/11.53 MARK(isNatIList(X)) -> A__ISNATILIST(X) 30.91/11.53 MARK(U51(X1, X2, X3)) -> A__U51(mark(X1), X2, X3) 30.91/11.53 A__U51(tt, V1, V2) -> A__ISNAT(V1) 30.91/11.53 MARK(U51(X1, X2, X3)) -> MARK(X1) 30.91/11.53 MARK(U52(X1, X2)) -> A__U52(mark(X1), X2) 30.91/11.53 MARK(U52(X1, X2)) -> MARK(X1) 30.91/11.53 MARK(and(X1, X2)) -> A__AND(mark(X1), X2) 30.91/11.53 MARK(and(X1, X2)) -> MARK(X1) 30.91/11.53 MARK(isNatKind(X)) -> A__ISNATKIND(X) 30.91/11.53 MARK(cons(X1, X2)) -> MARK(X1) 30.91/11.53 MARK(s(X)) -> MARK(X) 30.91/11.53 The remaining pairs can at least be oriented weakly. 30.91/11.53 Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation: 30.91/11.53 30.91/11.53 POL( A__AND_2(x_1, x_2) ) = 2x_2 + 2 30.91/11.53 POL( A__U11_2(x_1, x_2) ) = 2x_2 + 1 30.91/11.53 POL( A__U21_2(x_1, x_2) ) = 2x_2 + 1 30.91/11.53 POL( A__U31_2(x_1, x_2) ) = 2x_2 + 2 30.91/11.53 POL( A__U41_3(x_1, ..., x_3) ) = 2x_2 + 2x_3 + 2 30.91/11.53 POL( A__U42_2(x_1, x_2) ) = 2x_2 + 2 30.91/11.53 POL( A__U51_3(x_1, ..., x_3) ) = 2x_2 + 2x_3 + 2 30.91/11.53 POL( A__U52_2(x_1, x_2) ) = 2x_2 + 2 30.91/11.53 POL( a__isNatKind_1(x_1) ) = 0 30.91/11.53 POL( 0 ) = 2 30.91/11.53 POL( tt ) = 0 30.91/11.53 POL( mark_1(x_1) ) = 0 30.91/11.53 POL( and_2(x_1, x_2) ) = x_1 + x_2 + 2 30.91/11.53 POL( a__and_2(x_1, x_2) ) = max{0, -2} 30.91/11.53 POL( isNatIListKind_1(x_1) ) = 2x_1 30.91/11.53 POL( a__isNatIListKind_1(x_1) ) = 0 30.91/11.53 POL( cons_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 30.91/11.53 POL( isNatKind_1(x_1) ) = x_1 + 1 30.91/11.53 POL( length_1(x_1) ) = x_1 + 1 30.91/11.53 POL( s_1(x_1) ) = 2x_1 + 2 30.91/11.53 POL( a__isNat_1(x_1) ) = 0 30.91/11.53 POL( a__U11_2(x_1, x_2) ) = max{0, x_2 - 2} 30.91/11.53 POL( a__U21_2(x_1, x_2) ) = 1 30.91/11.53 POL( isNat_1(x_1) ) = 2x_1 + 1 30.91/11.53 POL( zeros ) = 0 30.91/11.53 POL( a__zeros ) = 0 30.91/11.53 POL( U11_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 30.91/11.53 POL( U12_1(x_1) ) = 2x_1 + 2 30.91/11.53 POL( a__U12_1(x_1) ) = max{0, -2} 30.91/11.53 POL( isNatList_1(x_1) ) = 2x_1 + 1 30.91/11.53 POL( a__isNatList_1(x_1) ) = 0 30.91/11.53 POL( U21_2(x_1, x_2) ) = 2x_1 + x_2 + 1 30.91/11.53 POL( U22_1(x_1) ) = x_1 30.91/11.53 POL( a__U22_1(x_1) ) = max{0, -2} 30.91/11.53 POL( U31_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2 30.91/11.53 POL( a__U31_2(x_1, x_2) ) = 2 30.91/11.53 POL( U32_1(x_1) ) = 2x_1 + 1 30.91/11.53 POL( a__U32_1(x_1) ) = 0 30.91/11.53 POL( U41_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2x_3 + 2 30.91/11.53 POL( a__U41_3(x_1, ..., x_3) ) = max{0, x_3 - 2} 30.91/11.53 POL( U42_2(x_1, x_2) ) = x_1 + 2x_2 + 2 30.91/11.53 POL( a__U42_2(x_1, x_2) ) = max{0, x_2 - 2} 30.91/11.53 POL( U43_1(x_1) ) = x_1 30.91/11.53 POL( a__U43_1(x_1) ) = 2 30.91/11.53 POL( isNatIList_1(x_1) ) = 2x_1 + 2 30.91/11.53 POL( a__isNatIList_1(x_1) ) = 0 30.91/11.53 POL( U51_3(x_1, ..., x_3) ) = x_1 + 2x_2 + 2x_3 + 2 30.91/11.53 POL( a__U51_3(x_1, ..., x_3) ) = x_2 + 2x_3 + 1 30.91/11.53 POL( U52_2(x_1, x_2) ) = x_1 + 2x_2 + 2 30.91/11.53 POL( a__U52_2(x_1, x_2) ) = max{0, 2x_2 - 2} 30.91/11.53 POL( U53_1(x_1) ) = 2x_1 30.91/11.53 POL( a__U53_1(x_1) ) = max{0, -2} 30.91/11.53 POL( U61_2(x_1, x_2) ) = 2x_1 + 2x_2 30.91/11.53 POL( a__U61_2(x_1, x_2) ) = max{0, x_2 - 2} 30.91/11.53 POL( a__length_1(x_1) ) = max{0, x_1 - 2} 30.91/11.53 POL( nil ) = 2 30.91/11.53 POL( A__ISNATLIST_1(x_1) ) = 2x_1 30.91/11.53 POL( MARK_1(x_1) ) = 2x_1 + 1 30.91/11.53 POL( A__ISNATKIND_1(x_1) ) = 2x_1 30.91/11.53 POL( A__ISNATILISTKIND_1(x_1) ) = 2x_1 + 1 30.91/11.53 POL( A__ISNAT_1(x_1) ) = 2x_1 30.91/11.53 POL( A__ISNATILIST_1(x_1) ) = 2x_1 + 2 30.91/11.53 30.91/11.53 The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented: 30.91/11.53 none 30.91/11.53 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (13) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 A__U51(tt, V1, V2) -> A__U52(a__isNat(V1), V2) 30.91/11.53 MARK(U22(X)) -> MARK(X) 30.91/11.53 A__U41(tt, V1, V2) -> A__U42(a__isNat(V1), V2) 30.91/11.53 A__U42(tt, V2) -> A__ISNATILIST(V2) 30.91/11.53 A__ISNATILIST(V) -> A__U31(a__isNatIListKind(V), V) 30.91/11.53 MARK(U43(X)) -> MARK(X) 30.91/11.53 MARK(U53(X)) -> MARK(X) 30.91/11.53 MARK(isNatIListKind(X)) -> A__ISNATILISTKIND(X) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.53 a__U32(tt) -> tt 30.91/11.53 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.53 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.53 a__isNatIList(zeros) -> tt 30.91/11.53 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.53 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.53 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.53 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__zeros -> zeros 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.53 a__U32(X) -> U32(X) 30.91/11.53 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.53 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__isNatIList(X) -> isNatIList(X) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (14) DependencyGraphProof (EQUIVALENT) 30.91/11.53 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (15) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 MARK(U43(X)) -> MARK(X) 30.91/11.53 MARK(U22(X)) -> MARK(X) 30.91/11.53 MARK(U53(X)) -> MARK(X) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.53 a__U32(tt) -> tt 30.91/11.53 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.53 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.53 a__isNatIList(zeros) -> tt 30.91/11.53 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.53 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.53 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.53 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__zeros -> zeros 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.53 a__U32(X) -> U32(X) 30.91/11.53 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.53 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__isNatIList(X) -> isNatIList(X) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (16) UsableRulesProof (EQUIVALENT) 30.91/11.53 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (17) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 MARK(U43(X)) -> MARK(X) 30.91/11.53 MARK(U22(X)) -> MARK(X) 30.91/11.53 MARK(U53(X)) -> MARK(X) 30.91/11.53 30.91/11.53 R is empty. 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (18) QReductionProof (EQUIVALENT) 30.91/11.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (19) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 MARK(U43(X)) -> MARK(X) 30.91/11.53 MARK(U22(X)) -> MARK(X) 30.91/11.53 MARK(U53(X)) -> MARK(X) 30.91/11.53 30.91/11.53 R is empty. 30.91/11.53 Q is empty. 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (20) QDPSizeChangeProof (EQUIVALENT) 30.91/11.53 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. 30.91/11.53 30.91/11.53 From the DPs we obtained the following set of size-change graphs: 30.91/11.53 *MARK(U43(X)) -> MARK(X) 30.91/11.53 The graph contains the following edges 1 > 1 30.91/11.53 30.91/11.53 30.91/11.53 *MARK(U22(X)) -> MARK(X) 30.91/11.53 The graph contains the following edges 1 > 1 30.91/11.53 30.91/11.53 30.91/11.53 *MARK(U53(X)) -> MARK(X) 30.91/11.53 The graph contains the following edges 1 > 1 30.91/11.53 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (21) 30.91/11.53 YES 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (22) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.53 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.53 a__U32(tt) -> tt 30.91/11.53 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.53 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.53 a__isNatIList(zeros) -> tt 30.91/11.53 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.53 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.53 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.53 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__zeros -> zeros 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.53 a__U32(X) -> U32(X) 30.91/11.53 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.53 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__isNatIList(X) -> isNatIList(X) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (23) QDPQMonotonicMRRProof (EQUIVALENT) 30.91/11.53 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 30.91/11.53 30.91/11.53 30.91/11.53 Strictly oriented rules of the TRS R: 30.91/11.53 30.91/11.53 a__U31(tt, V) -> a__U32(a__isNatList(V)) 30.91/11.53 a__U32(tt) -> tt 30.91/11.53 a__isNatIList(zeros) -> tt 30.91/11.53 mark(U31(X1, X2)) -> a__U31(mark(X1), X2) 30.91/11.53 mark(U32(X)) -> a__U32(mark(X)) 30.91/11.53 mark(U41(X1, X2, X3)) -> a__U41(mark(X1), X2, X3) 30.91/11.53 mark(U42(X1, X2)) -> a__U42(mark(X1), X2) 30.91/11.53 mark(isNatIList(X)) -> a__isNatIList(X) 30.91/11.53 30.91/11.53 Used ordering: Polynomial interpretation [POLO]: 30.91/11.53 30.91/11.53 POL(0) = 0 30.91/11.53 POL(A__LENGTH(x_1)) = x_1 30.91/11.53 POL(A__U61(x_1, x_2)) = 2*x_1 + 2*x_2 30.91/11.53 POL(U11(x_1, x_2)) = x_1 30.91/11.53 POL(U12(x_1)) = x_1 30.91/11.53 POL(U21(x_1, x_2)) = x_1 30.91/11.53 POL(U22(x_1)) = x_1 30.91/11.53 POL(U31(x_1, x_2)) = 2 + 2*x_1 30.91/11.53 POL(U32(x_1)) = 1 + 2*x_1 30.91/11.53 POL(U41(x_1, x_2, x_3)) = 2 + x_1 30.91/11.53 POL(U42(x_1, x_2)) = 2 + x_1 30.91/11.53 POL(U43(x_1)) = x_1 30.91/11.53 POL(U51(x_1, x_2, x_3)) = x_1 30.91/11.53 POL(U52(x_1, x_2)) = 2*x_1 30.91/11.53 POL(U53(x_1)) = x_1 30.91/11.53 POL(U61(x_1, x_2)) = 2*x_1 + x_2 30.91/11.53 POL(a__U11(x_1, x_2)) = x_1 30.91/11.53 POL(a__U12(x_1)) = x_1 30.91/11.53 POL(a__U21(x_1, x_2)) = x_1 30.91/11.53 POL(a__U22(x_1)) = x_1 30.91/11.53 POL(a__U31(x_1, x_2)) = 2 + 2*x_1 30.91/11.53 POL(a__U32(x_1)) = 1 + 2*x_1 30.91/11.53 POL(a__U41(x_1, x_2, x_3)) = 2 + x_1 30.91/11.53 POL(a__U42(x_1, x_2)) = 2 + x_1 30.91/11.53 POL(a__U43(x_1)) = x_1 30.91/11.53 POL(a__U51(x_1, x_2, x_3)) = x_1 30.91/11.53 POL(a__U52(x_1, x_2)) = 2*x_1 30.91/11.53 POL(a__U53(x_1)) = x_1 30.91/11.53 POL(a__U61(x_1, x_2)) = 2*x_1 + 2*x_2 30.91/11.53 POL(a__and(x_1, x_2)) = x_1 + 2*x_2 30.91/11.53 POL(a__isNat(x_1)) = 0 30.91/11.53 POL(a__isNatIList(x_1)) = 2 30.91/11.53 POL(a__isNatIListKind(x_1)) = 0 30.91/11.53 POL(a__isNatKind(x_1)) = 0 30.91/11.53 POL(a__isNatList(x_1)) = 0 30.91/11.53 POL(a__length(x_1)) = x_1 30.91/11.53 POL(a__zeros) = 0 30.91/11.53 POL(and(x_1, x_2)) = x_1 + 2*x_2 30.91/11.53 POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2 30.91/11.53 POL(isNat(x_1)) = 0 30.91/11.53 POL(isNatIList(x_1)) = 2 30.91/11.53 POL(isNatIListKind(x_1)) = 0 30.91/11.53 POL(isNatKind(x_1)) = 0 30.91/11.53 POL(isNatList(x_1)) = 0 30.91/11.53 POL(length(x_1)) = x_1 30.91/11.53 POL(mark(x_1)) = 2*x_1 30.91/11.53 POL(nil) = 0 30.91/11.53 POL(s(x_1)) = x_1 30.91/11.53 POL(tt) = 0 30.91/11.53 POL(zeros) = 0 30.91/11.53 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (24) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.53 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U41(tt, V1, V2) -> a__U42(a__isNat(V1), V2) 30.91/11.53 a__U42(tt, V2) -> a__U43(a__isNatIList(V2)) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNatIList(V) -> a__U31(a__isNatIListKind(V), V) 30.91/11.53 a__isNatIList(cons(V1, V2)) -> a__U41(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__zeros -> zeros 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U31(X1, X2) -> U31(X1, X2) 30.91/11.53 a__U32(X) -> U32(X) 30.91/11.53 a__U41(X1, X2, X3) -> U41(X1, X2, X3) 30.91/11.53 a__U42(X1, X2) -> U42(X1, X2) 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__isNatIList(X) -> isNatIList(X) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (25) UsableRulesProof (EQUIVALENT) 30.91/11.53 As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (26) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.53 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__zeros -> zeros 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 a__isNatIList(x0) 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (27) QReductionProof (EQUIVALENT) 30.91/11.53 We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN]. 30.91/11.53 30.91/11.53 a__isNatIList(x0) 30.91/11.53 a__U31(x0, x1) 30.91/11.53 a__U32(x0) 30.91/11.53 a__U41(x0, x1, x2) 30.91/11.53 a__U42(x0, x1) 30.91/11.53 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (28) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.53 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__zeros -> zeros 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (29) QDPQMonotonicMRRProof (EQUIVALENT) 30.91/11.53 By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain. 30.91/11.53 30.91/11.53 Strictly oriented dependency pairs: 30.91/11.53 30.91/11.53 A__U61(tt, L) -> A__LENGTH(mark(L)) 30.91/11.53 30.91/11.53 30.91/11.53 Used ordering: Polynomial interpretation [POLO]: 30.91/11.53 30.91/11.53 POL(0) = 0 30.91/11.53 POL(A__LENGTH(x_1)) = 2*x_1 30.91/11.53 POL(A__U61(x_1, x_2)) = 2 + 2*x_1 + 2*x_2 30.91/11.53 POL(U11(x_1, x_2)) = 2 30.91/11.53 POL(U12(x_1)) = 2 30.91/11.53 POL(U21(x_1, x_2)) = 1 30.91/11.53 POL(U22(x_1)) = 2 30.91/11.53 POL(U43(x_1)) = 0 30.91/11.53 POL(U51(x_1, x_2, x_3)) = 2*x_3 30.91/11.53 POL(U52(x_1, x_2)) = 1 + 2*x_2 30.91/11.53 POL(U53(x_1)) = 0 30.91/11.53 POL(U61(x_1, x_2)) = 0 30.91/11.53 POL(a__U11(x_1, x_2)) = 2 30.91/11.53 POL(a__U12(x_1)) = 2 30.91/11.53 POL(a__U21(x_1, x_2)) = 2 30.91/11.53 POL(a__U22(x_1)) = 2 30.91/11.53 POL(a__U43(x_1)) = 2 30.91/11.53 POL(a__U51(x_1, x_2, x_3)) = 2 + 2*x_3 30.91/11.53 POL(a__U52(x_1, x_2)) = 2 + 2*x_2 30.91/11.53 POL(a__U53(x_1)) = 2 30.91/11.53 POL(a__U61(x_1, x_2)) = 0 30.91/11.53 POL(a__and(x_1, x_2)) = x_1 + x_2 30.91/11.53 POL(a__isNat(x_1)) = 2 30.91/11.53 POL(a__isNatIListKind(x_1)) = 2 30.91/11.53 POL(a__isNatKind(x_1)) = 2 30.91/11.53 POL(a__isNatList(x_1)) = x_1 30.91/11.53 POL(a__length(x_1)) = 1 30.91/11.53 POL(a__zeros) = 2 30.91/11.53 POL(and(x_1, x_2)) = x_1 + x_2 30.91/11.53 POL(cons(x_1, x_2)) = 2 + 2*x_2 30.91/11.53 POL(isNat(x_1)) = 1 30.91/11.53 POL(isNatIListKind(x_1)) = 0 30.91/11.53 POL(isNatKind(x_1)) = 0 30.91/11.53 POL(isNatList(x_1)) = x_1 30.91/11.53 POL(length(x_1)) = 0 30.91/11.53 POL(mark(x_1)) = 2 + x_1 30.91/11.53 POL(nil) = 2 30.91/11.53 POL(s(x_1)) = 0 30.91/11.53 POL(tt) = 2 30.91/11.53 POL(zeros) = 0 30.91/11.53 30.91/11.53 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (30) 30.91/11.53 Obligation: 30.91/11.53 Q DP problem: 30.91/11.53 The TRS P consists of the following rules: 30.91/11.53 30.91/11.53 A__LENGTH(cons(N, L)) -> A__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 30.91/11.53 The TRS R consists of the following rules: 30.91/11.53 30.91/11.53 a__isNatList(nil) -> tt 30.91/11.53 a__isNatList(cons(V1, V2)) -> a__U51(a__and(a__isNatKind(V1), isNatIListKind(V2)), V1, V2) 30.91/11.53 a__isNatList(X) -> isNatList(X) 30.91/11.53 mark(and(X1, X2)) -> a__and(mark(X1), X2) 30.91/11.53 a__and(tt, X) -> mark(X) 30.91/11.53 mark(isNatIListKind(X)) -> a__isNatIListKind(X) 30.91/11.53 a__isNatIListKind(cons(V1, V2)) -> a__and(a__isNatKind(V1), isNatIListKind(V2)) 30.91/11.53 mark(isNatKind(X)) -> a__isNatKind(X) 30.91/11.53 a__isNatKind(length(V1)) -> a__isNatIListKind(V1) 30.91/11.53 a__isNatKind(s(V1)) -> a__isNatKind(V1) 30.91/11.53 a__and(X1, X2) -> and(X1, X2) 30.91/11.53 mark(zeros) -> a__zeros 30.91/11.53 mark(U11(X1, X2)) -> a__U11(mark(X1), X2) 30.91/11.53 mark(U12(X)) -> a__U12(mark(X)) 30.91/11.53 mark(isNatList(X)) -> a__isNatList(X) 30.91/11.53 mark(U21(X1, X2)) -> a__U21(mark(X1), X2) 30.91/11.53 mark(U22(X)) -> a__U22(mark(X)) 30.91/11.53 mark(isNat(X)) -> a__isNat(X) 30.91/11.53 mark(U43(X)) -> a__U43(mark(X)) 30.91/11.53 mark(U51(X1, X2, X3)) -> a__U51(mark(X1), X2, X3) 30.91/11.53 mark(U52(X1, X2)) -> a__U52(mark(X1), X2) 30.91/11.53 mark(U53(X)) -> a__U53(mark(X)) 30.91/11.53 mark(U61(X1, X2)) -> a__U61(mark(X1), X2) 30.91/11.53 mark(length(X)) -> a__length(mark(X)) 30.91/11.53 mark(cons(X1, X2)) -> cons(mark(X1), X2) 30.91/11.53 mark(0) -> 0 30.91/11.53 mark(tt) -> tt 30.91/11.53 mark(s(X)) -> s(mark(X)) 30.91/11.53 mark(nil) -> nil 30.91/11.53 a__isNatIListKind(nil) -> tt 30.91/11.53 a__isNatIListKind(zeros) -> tt 30.91/11.53 a__isNatIListKind(X) -> isNatIListKind(X) 30.91/11.53 a__isNatKind(0) -> tt 30.91/11.53 a__isNatKind(X) -> isNatKind(X) 30.91/11.53 a__length(nil) -> 0 30.91/11.53 a__length(cons(N, L)) -> a__U61(a__and(a__and(a__isNatList(L), isNatIListKind(L)), and(isNat(N), isNatKind(N))), L) 30.91/11.53 a__length(X) -> length(X) 30.91/11.53 a__U61(tt, L) -> s(a__length(mark(L))) 30.91/11.53 a__U61(X1, X2) -> U61(X1, X2) 30.91/11.53 a__U53(tt) -> tt 30.91/11.53 a__U53(X) -> U53(X) 30.91/11.53 a__U52(tt, V2) -> a__U53(a__isNatList(V2)) 30.91/11.53 a__U52(X1, X2) -> U52(X1, X2) 30.91/11.53 a__U51(tt, V1, V2) -> a__U52(a__isNat(V1), V2) 30.91/11.53 a__U51(X1, X2, X3) -> U51(X1, X2, X3) 30.91/11.53 a__isNat(0) -> tt 30.91/11.53 a__isNat(length(V1)) -> a__U11(a__isNatIListKind(V1), V1) 30.91/11.53 a__isNat(s(V1)) -> a__U21(a__isNatKind(V1), V1) 30.91/11.53 a__isNat(X) -> isNat(X) 30.91/11.53 a__U21(tt, V1) -> a__U22(a__isNat(V1)) 30.91/11.53 a__U21(X1, X2) -> U21(X1, X2) 30.91/11.53 a__U22(tt) -> tt 30.91/11.53 a__U22(X) -> U22(X) 30.91/11.53 a__U11(tt, V1) -> a__U12(a__isNatList(V1)) 30.91/11.53 a__U11(X1, X2) -> U11(X1, X2) 30.91/11.53 a__U12(tt) -> tt 30.91/11.53 a__U12(X) -> U12(X) 30.91/11.53 a__U43(tt) -> tt 30.91/11.53 a__U43(X) -> U43(X) 30.91/11.53 a__zeros -> cons(0, zeros) 30.91/11.53 a__zeros -> zeros 30.91/11.53 30.91/11.53 The set Q consists of the following terms: 30.91/11.53 30.91/11.53 a__zeros 30.91/11.53 mark(zeros) 30.91/11.53 mark(U11(x0, x1)) 30.91/11.53 mark(U12(x0)) 30.91/11.53 mark(isNatList(x0)) 30.91/11.53 mark(U21(x0, x1)) 30.91/11.53 mark(U22(x0)) 30.91/11.53 mark(isNat(x0)) 30.91/11.53 mark(U31(x0, x1)) 30.91/11.53 mark(U32(x0)) 30.91/11.53 mark(U41(x0, x1, x2)) 30.91/11.53 mark(U42(x0, x1)) 30.91/11.53 mark(U43(x0)) 30.91/11.53 mark(isNatIList(x0)) 30.91/11.53 mark(U51(x0, x1, x2)) 30.91/11.53 mark(U52(x0, x1)) 30.91/11.53 mark(U53(x0)) 30.91/11.53 mark(U61(x0, x1)) 30.91/11.53 mark(length(x0)) 30.91/11.53 mark(and(x0, x1)) 30.91/11.53 mark(isNatIListKind(x0)) 30.91/11.53 mark(isNatKind(x0)) 30.91/11.53 mark(cons(x0, x1)) 30.91/11.53 mark(0) 30.91/11.53 mark(tt) 30.91/11.53 mark(s(x0)) 30.91/11.53 mark(nil) 30.91/11.53 a__U11(x0, x1) 30.91/11.53 a__U12(x0) 30.91/11.53 a__isNatList(x0) 30.91/11.53 a__U21(x0, x1) 30.91/11.53 a__U22(x0) 30.91/11.53 a__isNat(x0) 30.91/11.53 a__U43(x0) 30.91/11.53 a__U51(x0, x1, x2) 30.91/11.53 a__U52(x0, x1) 30.91/11.53 a__U53(x0) 30.91/11.53 a__U61(x0, x1) 30.91/11.53 a__length(x0) 30.91/11.53 a__and(x0, x1) 30.91/11.53 a__isNatIListKind(x0) 30.91/11.53 a__isNatKind(x0) 30.91/11.53 30.91/11.53 We have to consider all minimal (P,Q,R)-chains. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (31) DependencyGraphProof (EQUIVALENT) 30.91/11.53 The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node. 30.91/11.53 ---------------------------------------- 30.91/11.53 30.91/11.53 (32) 30.91/11.53 TRUE 31.26/11.61 EOF