6.00/2.48	YES
6.00/2.49	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.00/2.49	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.00/2.49	
6.00/2.49	
6.00/2.49	Termination w.r.t. Q of the given QTRS could be proven:
6.00/2.49	
6.00/2.49	(0) QTRS
6.00/2.49	(1) QTRSToCSRProof [SOUND, 0 ms]
6.00/2.49	(2) CSR
6.00/2.49	(3) CSRRRRProof [EQUIVALENT, 54 ms]
6.00/2.49	(4) CSR
6.00/2.49	(5) CSRRRRProof [EQUIVALENT, 16 ms]
6.00/2.49	(6) CSR
6.00/2.49	(7) CSRRRRProof [EQUIVALENT, 0 ms]
6.00/2.49	(8) CSR
6.00/2.49	(9) CSRRRRProof [EQUIVALENT, 13 ms]
6.00/2.49	(10) CSR
6.00/2.49	(11) CSRInnermostProof [EQUIVALENT, 0 ms]
6.00/2.49	(12) CSR
6.00/2.49	(13) CSDependencyPairsProof [EQUIVALENT, 0 ms]
6.00/2.49	(14) QCSDP
6.00/2.49	(15) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
6.00/2.49	(16) AND
6.00/2.49	    (17) QCSDP
6.00/2.49	        (18) QCSDPSubtermProof [EQUIVALENT, 2 ms]
6.00/2.49	        (19) QCSDP
6.00/2.49	        (20) PIsEmptyProof [EQUIVALENT, 0 ms]
6.00/2.49	        (21) YES
6.00/2.49	    (22) QCSDP
6.00/2.49	        (23) QCSUsableRulesProof [EQUIVALENT, 0 ms]
6.00/2.49	        (24) QCSDP
6.00/2.49	        (25) QCSDPMuMonotonicPoloProof [EQUIVALENT, 0 ms]
6.00/2.49	        (26) QCSDP
6.00/2.49	        (27) PIsEmptyProof [EQUIVALENT, 0 ms]
6.00/2.49	        (28) YES
6.00/2.49	    (29) QCSDP
6.00/2.49	        (30) QCSDPReductionPairProof [EQUIVALENT, 20 ms]
6.00/2.49	        (31) QCSDP
6.00/2.49	        (32) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
6.00/2.49	        (33) TRUE
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(0)
6.00/2.49	Obligation:
6.00/2.49	Q restricted rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   active(zeros) -> mark(cons(0, zeros))
6.00/2.49	   active(U11(tt, L)) -> mark(s(length(L)))
6.00/2.49	   active(and(tt, X)) -> mark(X)
6.00/2.49	   active(isNat(0)) -> mark(tt)
6.00/2.49	   active(isNat(length(V1))) -> mark(isNatList(V1))
6.00/2.49	   active(isNat(s(V1))) -> mark(isNat(V1))
6.00/2.49	   active(isNatIList(V)) -> mark(isNatList(V))
6.00/2.49	   active(isNatIList(zeros)) -> mark(tt)
6.00/2.49	   active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2)))
6.00/2.49	   active(isNatList(nil)) -> mark(tt)
6.00/2.49	   active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2)))
6.00/2.49	   active(length(nil)) -> mark(0)
6.00/2.49	   active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L))
6.00/2.49	   active(cons(X1, X2)) -> cons(active(X1), X2)
6.00/2.49	   active(U11(X1, X2)) -> U11(active(X1), X2)
6.00/2.49	   active(s(X)) -> s(active(X))
6.00/2.49	   active(length(X)) -> length(active(X))
6.00/2.49	   active(and(X1, X2)) -> and(active(X1), X2)
6.00/2.49	   cons(mark(X1), X2) -> mark(cons(X1, X2))
6.00/2.49	   U11(mark(X1), X2) -> mark(U11(X1, X2))
6.00/2.49	   s(mark(X)) -> mark(s(X))
6.00/2.49	   length(mark(X)) -> mark(length(X))
6.00/2.49	   and(mark(X1), X2) -> mark(and(X1, X2))
6.00/2.49	   proper(zeros) -> ok(zeros)
6.00/2.49	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
6.00/2.49	   proper(0) -> ok(0)
6.00/2.49	   proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
6.00/2.49	   proper(tt) -> ok(tt)
6.00/2.49	   proper(s(X)) -> s(proper(X))
6.00/2.49	   proper(length(X)) -> length(proper(X))
6.00/2.49	   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
6.00/2.49	   proper(isNat(X)) -> isNat(proper(X))
6.00/2.49	   proper(isNatList(X)) -> isNatList(proper(X))
6.00/2.49	   proper(isNatIList(X)) -> isNatIList(proper(X))
6.00/2.49	   proper(nil) -> ok(nil)
6.00/2.49	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
6.00/2.49	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
6.00/2.49	   s(ok(X)) -> ok(s(X))
6.00/2.49	   length(ok(X)) -> ok(length(X))
6.00/2.49	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
6.00/2.49	   isNat(ok(X)) -> ok(isNat(X))
6.00/2.49	   isNatList(ok(X)) -> ok(isNatList(X))
6.00/2.49	   isNatIList(ok(X)) -> ok(isNatIList(X))
6.00/2.49	   top(mark(X)) -> top(proper(X))
6.00/2.49	   top(ok(X)) -> top(active(X))
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   active(zeros)
6.00/2.49	   active(isNat(0))
6.00/2.49	   active(isNat(length(x0)))
6.00/2.49	   active(isNat(s(x0)))
6.00/2.49	   active(isNatIList(x0))
6.00/2.49	   active(isNatList(nil))
6.00/2.49	   active(isNatList(cons(x0, x1)))
6.00/2.49	   active(cons(x0, x1))
6.00/2.49	   active(U11(x0, x1))
6.00/2.49	   active(s(x0))
6.00/2.49	   active(length(x0))
6.00/2.49	   active(and(x0, x1))
6.00/2.49	   cons(mark(x0), x1)
6.00/2.49	   U11(mark(x0), x1)
6.00/2.49	   s(mark(x0))
6.00/2.49	   length(mark(x0))
6.00/2.49	   and(mark(x0), x1)
6.00/2.49	   proper(zeros)
6.00/2.49	   proper(cons(x0, x1))
6.00/2.49	   proper(0)
6.00/2.49	   proper(U11(x0, x1))
6.00/2.49	   proper(tt)
6.00/2.49	   proper(s(x0))
6.00/2.49	   proper(length(x0))
6.00/2.49	   proper(and(x0, x1))
6.00/2.49	   proper(isNat(x0))
6.00/2.49	   proper(isNatList(x0))
6.00/2.49	   proper(isNatIList(x0))
6.00/2.49	   proper(nil)
6.00/2.49	   cons(ok(x0), ok(x1))
6.00/2.49	   U11(ok(x0), ok(x1))
6.00/2.49	   s(ok(x0))
6.00/2.49	   length(ok(x0))
6.00/2.49	   and(ok(x0), ok(x1))
6.00/2.49	   isNat(ok(x0))
6.00/2.49	   isNatList(ok(x0))
6.00/2.49	   isNatIList(ok(x0))
6.00/2.49	   top(mark(x0))
6.00/2.49	   top(ok(x0))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(1) QTRSToCSRProof (SOUND)
6.00/2.49	The following Q TRS is given: Q restricted rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   active(zeros) -> mark(cons(0, zeros))
6.00/2.49	   active(U11(tt, L)) -> mark(s(length(L)))
6.00/2.49	   active(and(tt, X)) -> mark(X)
6.00/2.49	   active(isNat(0)) -> mark(tt)
6.00/2.49	   active(isNat(length(V1))) -> mark(isNatList(V1))
6.00/2.49	   active(isNat(s(V1))) -> mark(isNat(V1))
6.00/2.49	   active(isNatIList(V)) -> mark(isNatList(V))
6.00/2.49	   active(isNatIList(zeros)) -> mark(tt)
6.00/2.49	   active(isNatIList(cons(V1, V2))) -> mark(and(isNat(V1), isNatIList(V2)))
6.00/2.49	   active(isNatList(nil)) -> mark(tt)
6.00/2.49	   active(isNatList(cons(V1, V2))) -> mark(and(isNat(V1), isNatList(V2)))
6.00/2.49	   active(length(nil)) -> mark(0)
6.00/2.49	   active(length(cons(N, L))) -> mark(U11(and(isNatList(L), isNat(N)), L))
6.00/2.49	   active(cons(X1, X2)) -> cons(active(X1), X2)
6.00/2.49	   active(U11(X1, X2)) -> U11(active(X1), X2)
6.00/2.49	   active(s(X)) -> s(active(X))
6.00/2.49	   active(length(X)) -> length(active(X))
6.00/2.49	   active(and(X1, X2)) -> and(active(X1), X2)
6.00/2.49	   cons(mark(X1), X2) -> mark(cons(X1, X2))
6.00/2.49	   U11(mark(X1), X2) -> mark(U11(X1, X2))
6.00/2.49	   s(mark(X)) -> mark(s(X))
6.00/2.49	   length(mark(X)) -> mark(length(X))
6.00/2.49	   and(mark(X1), X2) -> mark(and(X1, X2))
6.00/2.49	   proper(zeros) -> ok(zeros)
6.00/2.49	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
6.00/2.49	   proper(0) -> ok(0)
6.00/2.49	   proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
6.00/2.49	   proper(tt) -> ok(tt)
6.00/2.49	   proper(s(X)) -> s(proper(X))
6.00/2.49	   proper(length(X)) -> length(proper(X))
6.00/2.49	   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
6.00/2.49	   proper(isNat(X)) -> isNat(proper(X))
6.00/2.49	   proper(isNatList(X)) -> isNatList(proper(X))
6.00/2.49	   proper(isNatIList(X)) -> isNatIList(proper(X))
6.00/2.49	   proper(nil) -> ok(nil)
6.00/2.49	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
6.00/2.49	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
6.00/2.49	   s(ok(X)) -> ok(s(X))
6.00/2.49	   length(ok(X)) -> ok(length(X))
6.00/2.49	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
6.00/2.49	   isNat(ok(X)) -> ok(isNat(X))
6.00/2.49	   isNatList(ok(X)) -> ok(isNatList(X))
6.00/2.49	   isNatIList(ok(X)) -> ok(isNatIList(X))
6.00/2.49	   top(mark(X)) -> top(proper(X))
6.00/2.49	   top(ok(X)) -> top(active(X))
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   active(zeros)
6.00/2.49	   active(isNat(0))
6.00/2.49	   active(isNat(length(x0)))
6.00/2.49	   active(isNat(s(x0)))
6.00/2.49	   active(isNatIList(x0))
6.00/2.49	   active(isNatList(nil))
6.00/2.49	   active(isNatList(cons(x0, x1)))
6.00/2.49	   active(cons(x0, x1))
6.00/2.49	   active(U11(x0, x1))
6.00/2.49	   active(s(x0))
6.00/2.49	   active(length(x0))
6.00/2.49	   active(and(x0, x1))
6.00/2.49	   cons(mark(x0), x1)
6.00/2.49	   U11(mark(x0), x1)
6.00/2.49	   s(mark(x0))
6.00/2.49	   length(mark(x0))
6.00/2.49	   and(mark(x0), x1)
6.00/2.49	   proper(zeros)
6.00/2.49	   proper(cons(x0, x1))
6.00/2.49	   proper(0)
6.00/2.49	   proper(U11(x0, x1))
6.00/2.49	   proper(tt)
6.00/2.49	   proper(s(x0))
6.00/2.49	   proper(length(x0))
6.00/2.49	   proper(and(x0, x1))
6.00/2.49	   proper(isNat(x0))
6.00/2.49	   proper(isNatList(x0))
6.00/2.49	   proper(isNatIList(x0))
6.00/2.49	   proper(nil)
6.00/2.49	   cons(ok(x0), ok(x1))
6.00/2.49	   U11(ok(x0), ok(x1))
6.00/2.49	   s(ok(x0))
6.00/2.49	   length(ok(x0))
6.00/2.49	   and(ok(x0), ok(x1))
6.00/2.49	   isNat(ok(x0))
6.00/2.49	   isNatList(ok(x0))
6.00/2.49	   isNatIList(ok(x0))
6.00/2.49	   top(mark(x0))
6.00/2.49	   top(ok(x0))
6.00/2.49	
6.00/2.49	Special symbols used for the transformation (see [GM04]):
6.00/2.49	top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete.
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(2)
6.00/2.49	Obligation:
6.00/2.49	Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(V) -> isNatList(V)
6.00/2.49	   isNatIList(zeros) -> tt
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(nil) -> 0
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(3) CSRRRRProof (EQUIVALENT)
6.00/2.49	The following CSR is given: Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(V) -> isNatList(V)
6.00/2.49	   isNatIList(zeros) -> tt
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(nil) -> 0
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	Used ordering:
6.00/2.49	Polynomial interpretation [POLO]:
6.00/2.49	
6.00/2.49	   POL(0) = 0
6.00/2.49	   POL(U11(x_1, x_2)) = 1 + x_1 + x_2
6.00/2.49	   POL(and(x_1, x_2)) = x_1 + x_2
6.00/2.49	   POL(cons(x_1, x_2)) = x_1 + x_2
6.00/2.49	   POL(isNat(x_1)) = 0
6.00/2.49	   POL(isNatIList(x_1)) = x_1
6.00/2.49	   POL(isNatList(x_1)) = 0
6.00/2.49	   POL(length(x_1)) = 1 + x_1
6.00/2.49	   POL(nil) = 1
6.00/2.49	   POL(s(x_1)) = x_1
6.00/2.49	   POL(tt) = 0
6.00/2.49	   POL(zeros) = 1
6.00/2.49	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.00/2.49	
6.00/2.49	   isNatIList(zeros) -> tt
6.00/2.49	   length(nil) -> 0
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(4)
6.00/2.49	Obligation:
6.00/2.49	Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(V) -> isNatList(V)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(5) CSRRRRProof (EQUIVALENT)
6.00/2.49	The following CSR is given: Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(V) -> isNatList(V)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	Used ordering:
6.00/2.49	Polynomial interpretation [POLO]:
6.00/2.49	
6.00/2.49	   POL(0) = 0
6.00/2.49	   POL(U11(x_1, x_2)) = x_1 + 2*x_2
6.00/2.49	   POL(and(x_1, x_2)) = x_1 + x_2
6.00/2.49	   POL(cons(x_1, x_2)) = 2*x_1 + x_2
6.00/2.49	   POL(isNat(x_1)) = 0
6.00/2.49	   POL(isNatIList(x_1)) = 1 + x_1
6.00/2.49	   POL(isNatList(x_1)) = 0
6.00/2.49	   POL(length(x_1)) = 2*x_1
6.00/2.49	   POL(nil) = 2
6.00/2.49	   POL(s(x_1)) = x_1
6.00/2.49	   POL(tt) = 0
6.00/2.49	   POL(zeros) = 0
6.00/2.49	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.00/2.49	
6.00/2.49	   isNatIList(V) -> isNatList(V)
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(6)
6.00/2.49	Obligation:
6.00/2.49	Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(7) CSRRRRProof (EQUIVALENT)
6.00/2.49	The following CSR is given: Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	nil: empty set
6.00/2.49	Used ordering:
6.00/2.49	Polynomial interpretation [POLO]:
6.00/2.49	
6.00/2.49	   POL(0) = 0
6.00/2.49	   POL(U11(x_1, x_2)) = x_1 + 2*x_2
6.00/2.49	   POL(and(x_1, x_2)) = x_1 + x_2
6.00/2.49	   POL(cons(x_1, x_2)) = x_1 + 2*x_2
6.00/2.49	   POL(isNat(x_1)) = 2*x_1
6.00/2.49	   POL(isNatIList(x_1)) = 2*x_1
6.00/2.49	   POL(isNatList(x_1)) = 2*x_1
6.00/2.49	   POL(length(x_1)) = 2*x_1
6.00/2.49	   POL(nil) = 1
6.00/2.49	   POL(s(x_1)) = x_1
6.00/2.49	   POL(tt) = 0
6.00/2.49	   POL(zeros) = 0
6.00/2.49	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.00/2.49	
6.00/2.49	   isNatList(nil) -> tt
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(8)
6.00/2.49	Obligation:
6.00/2.49	Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(9) CSRRRRProof (EQUIVALENT)
6.00/2.49	The following CSR is given: Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	Used ordering:
6.00/2.49	Polynomial interpretation [POLO]:
6.00/2.49	
6.00/2.49	   POL(0) = 0
6.00/2.49	   POL(U11(x_1, x_2)) = 1 + x_1 + 2*x_2
6.00/2.49	   POL(and(x_1, x_2)) = 2*x_1 + 2*x_2
6.00/2.49	   POL(cons(x_1, x_2)) = 2*x_1 + 2*x_2
6.00/2.49	   POL(isNat(x_1)) = x_1
6.00/2.49	   POL(isNatIList(x_1)) = x_1
6.00/2.49	   POL(isNatList(x_1)) = x_1
6.00/2.49	   POL(length(x_1)) = 1 + 2*x_1
6.00/2.49	   POL(s(x_1)) = x_1
6.00/2.49	   POL(tt) = 0
6.00/2.49	   POL(zeros) = 0
6.00/2.49	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.00/2.49	
6.00/2.49	   isNat(length(V1)) -> isNatList(V1)
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(10)
6.00/2.49	Obligation:
6.00/2.49	Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(11) CSRInnermostProof (EQUIVALENT)
6.00/2.49	The CSR is orthogonal. By [CS_Inn] we can switch to innermost.
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(12)
6.00/2.49	Obligation:
6.00/2.49	Context-sensitive rewrite system:
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The replacement map contains the following entries:
6.00/2.49	
6.00/2.49	zeros: empty set
6.00/2.49	cons: {1}
6.00/2.49	0: empty set
6.00/2.49	U11: {1}
6.00/2.49	tt: empty set
6.00/2.49	s: {1}
6.00/2.49	length: {1}
6.00/2.49	and: {1}
6.00/2.49	isNat: empty set
6.00/2.49	isNatList: empty set
6.00/2.49	isNatIList: empty set
6.00/2.49	
6.00/2.49	
6.00/2.49	Innermost Strategy.
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(13) CSDependencyPairsProof (EQUIVALENT)
6.00/2.49	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(14)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1, LENGTH_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, U11_2, and_2, U11'_2, AND_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1, ISNAT_1, ISNATILIST_1, ISNATLIST_1, U_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The ordinary context-sensitive dependency pairs DP_o are:
6.00/2.49	   U11'(tt, L) -> LENGTH(L)
6.00/2.49	   ISNAT(s(V1)) -> ISNAT(V1)
6.00/2.49	   ISNATILIST(cons(V1, V2)) -> AND(isNat(V1), isNatIList(V2))
6.00/2.49	   ISNATILIST(cons(V1, V2)) -> ISNAT(V1)
6.00/2.49	   ISNATLIST(cons(V1, V2)) -> AND(isNat(V1), isNatList(V2))
6.00/2.49	   ISNATLIST(cons(V1, V2)) -> ISNAT(V1)
6.00/2.49	   LENGTH(cons(N, L)) -> U11'(and(isNatList(L), isNat(N)), L)
6.00/2.49	   LENGTH(cons(N, L)) -> AND(isNatList(L), isNat(N))
6.00/2.49	   LENGTH(cons(N, L)) -> ISNATLIST(L)
6.00/2.49	
6.00/2.49	The collapsing dependency pairs are DP_c:
6.00/2.49	   U11'(tt, L) -> L
6.00/2.49	   AND(tt, X) -> X
6.00/2.49	
6.00/2.49	
6.00/2.49	The hidden terms of R are:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   isNatIList(x0)
6.00/2.49	   isNatList(x0)
6.00/2.49	   isNat(x0)
6.00/2.49	
6.00/2.49	Every hiding context is built from:none
6.00/2.49	
6.00/2.49	Hence, the new unhiding pairs DP_u are :
6.00/2.49	   U11'(tt, L) -> U(L)
6.00/2.49	   AND(tt, X) -> U(X)
6.00/2.49	   U(zeros) -> ZEROS
6.00/2.49	   U(isNatIList(x0)) -> ISNATILIST(x0)
6.00/2.49	   U(isNatList(x0)) -> ISNATLIST(x0)
6.00/2.49	   U(isNat(x0)) -> ISNAT(x0)
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(15) QCSDependencyGraphProof (EQUIVALENT)
6.00/2.49	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 7 less nodes.
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(16)
6.00/2.49	Complex Obligation (AND)
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(17)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, U11_2, and_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1, ISNAT_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	
6.00/2.49	   ISNAT(s(V1)) -> ISNAT(V1)
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(18) QCSDPSubtermProof (EQUIVALENT)
6.00/2.49	We use the subterm processor [DA_EMMES].
6.00/2.49	
6.00/2.49	
6.00/2.49	The following pairs can be oriented strictly and are deleted.
6.00/2.49	
6.00/2.49	   ISNAT(s(V1)) -> ISNAT(V1)
6.00/2.49	The remaining pairs can at least be oriented weakly.
6.00/2.49	none
6.00/2.49	Used ordering:  Combined order from the following AFS and order.
6.00/2.49	ISNAT(x1)  =  x1
6.00/2.49	
6.00/2.49	
6.00/2.49	Subterm Order
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(19)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, U11_2, and_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	none
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(20) PIsEmptyProof (EQUIVALENT)
6.00/2.49	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(21)
6.00/2.49	YES
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(22)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, U11_2, and_2, AND_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1, ISNATILIST_1, U_1, ISNATLIST_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	
6.00/2.49	   ISNATILIST(cons(V1, V2)) -> AND(isNat(V1), isNatIList(V2))
6.00/2.49	   AND(tt, X) -> U(X)
6.00/2.49	   U(isNatIList(x0)) -> ISNATILIST(x0)
6.00/2.49	   U(isNatList(x0)) -> ISNATLIST(x0)
6.00/2.49	   ISNATLIST(cons(V1, V2)) -> AND(isNat(V1), isNatList(V2))
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(23) QCSUsableRulesProof (EQUIVALENT)
6.00/2.49	The following rules are not useable [DA_EMMES] and can be deleted:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, x0) -> s(length(x0))
6.00/2.49	   and(tt, x0) -> x0
6.00/2.49	   isNatIList(cons(x0, x1)) -> and(isNat(x0), isNatIList(x1))
6.00/2.49	   isNatList(cons(x0, x1)) -> and(isNat(x0), isNatList(x1))
6.00/2.49	   length(cons(x0, x1)) -> U11(and(isNatList(x1), isNat(x0)), x1)
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(24)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, AND_2, U11_2, and_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1, ISNATILIST_1, U_1, ISNATLIST_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	
6.00/2.49	   ISNATILIST(cons(V1, V2)) -> AND(isNat(V1), isNatIList(V2))
6.00/2.49	   AND(tt, X) -> U(X)
6.00/2.49	   U(isNatIList(x0)) -> ISNATILIST(x0)
6.00/2.49	   U(isNatList(x0)) -> ISNATLIST(x0)
6.00/2.49	   ISNATLIST(cons(V1, V2)) -> AND(isNat(V1), isNatList(V2))
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(25) QCSDPMuMonotonicPoloProof (EQUIVALENT)
6.00/2.49	By using the following mu-monotonic polynomial ordering [POLO], at least one Dependency Pair or term rewrite system rule of this Q-CSDP problem can be strictly oriented and thus deleted.
6.00/2.49	
6.00/2.49	Strictly oriented dependency pairs:
6.00/2.49	
6.00/2.49	   ISNATILIST(cons(V1, V2)) -> AND(isNat(V1), isNatIList(V2))
6.00/2.49	   AND(tt, X) -> U(X)
6.00/2.49	   U(isNatIList(x0)) -> ISNATILIST(x0)
6.00/2.49	   U(isNatList(x0)) -> ISNATLIST(x0)
6.00/2.49	   ISNATLIST(cons(V1, V2)) -> AND(isNat(V1), isNatList(V2))
6.00/2.49	
6.00/2.49	Strictly oriented rules of the TRS R:
6.00/2.49	
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	
6.00/2.49	Used ordering: POLO with Polynomial interpretation [POLO]:
6.00/2.49	
6.00/2.49	   POL(0) = 1
6.00/2.49	   POL(AND(x_1, x_2)) = 2 + x_1 + 2*x_2
6.00/2.49	   POL(ISNATILIST(x_1)) = 1 + 2*x_1
6.00/2.49	   POL(ISNATLIST(x_1)) = 1 + 2*x_1
6.00/2.49	   POL(U(x_1)) = 2 + 2*x_1
6.00/2.49	   POL(cons(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
6.00/2.49	   POL(isNat(x_1)) = 2*x_1
6.00/2.49	   POL(isNatIList(x_1)) = 2*x_1
6.00/2.49	   POL(isNatList(x_1)) = 2*x_1
6.00/2.49	   POL(s(x_1)) = 1 + 2*x_1
6.00/2.49	   POL(tt) = 1
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(26)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1} are replacing on all positions.
6.00/2.49	For all symbols f in {U11_2, and_2, cons_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	none
6.00/2.49	
6.00/2.49	R is empty.
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(27) PIsEmptyProof (EQUIVALENT)
6.00/2.49	The TRS P is empty. Hence, there is no (P,Q,R,mu)-chain.
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(28)
6.00/2.49	YES
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(29)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1, LENGTH_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, U11_2, and_2, U11'_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	
6.00/2.49	   LENGTH(cons(N, L)) -> U11'(and(isNatList(L), isNat(N)), L)
6.00/2.49	   U11'(tt, L) -> LENGTH(L)
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(30) QCSDPReductionPairProof (EQUIVALENT)
6.00/2.49	Using the order
6.00/2.49	
6.00/2.49	Polynomial Order [NEGPOLO,POLO] with Interpretation:
6.00/2.49	
6.00/2.49	POL( and_2(x_1, x_2) ) = max{0, x_1 + x_2 - 1}
6.00/2.49	POL( tt ) = 1
6.00/2.49	POL( isNatList_1(x_1) ) = 0
6.00/2.49	POL( cons_2(x_1, x_2) ) = max{0, -1}
6.00/2.49	POL( isNat_1(x_1) ) = 1
6.00/2.49	POL( 0 ) = 0
6.00/2.49	POL( s_1(x_1) ) = x_1 + 2
6.00/2.49	POL( zeros ) = 0
6.00/2.49	POL( isNatIList_1(x_1) ) = 1
6.00/2.49	POL( LENGTH_1(x_1) ) = 0
6.00/2.49	POL( U11'_2(x_1, x_2) ) = max{0, 2x_1 - 1}
6.00/2.49	
6.00/2.49	
6.00/2.49	the following usable rules
6.00/2.49	
6.00/2.49	
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	
6.00/2.49	
6.00/2.49	could all be oriented weakly.
6.00/2.49	
6.00/2.49	Furthermore, the pairs
6.00/2.49	
6.00/2.49	
6.00/2.49	   U11'(tt, L) -> LENGTH(L)
6.00/2.49	
6.00/2.49	
6.00/2.49	could be oriented strictly and thus removed by the CS-Reduction Pair Processor [LPAR08,DA_EMMES].
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(31)
6.00/2.49	Obligation:
6.00/2.49	Q-restricted context-sensitive dependency pair problem:
6.00/2.49	The symbols in {s_1, length_1, LENGTH_1} are replacing on all positions.
6.00/2.49	For all symbols f in {cons_2, U11_2, and_2, U11'_2} we have mu(f) = {1}.
6.00/2.49	The symbols in {isNat_1, isNatIList_1, isNatList_1} are not replacing on any position.
6.00/2.49	
6.00/2.49	The TRS P consists of the following rules:
6.00/2.49	
6.00/2.49	   LENGTH(cons(N, L)) -> U11'(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The TRS R consists of the following rules:
6.00/2.49	
6.00/2.49	   zeros -> cons(0, zeros)
6.00/2.49	   U11(tt, L) -> s(length(L))
6.00/2.49	   and(tt, X) -> X
6.00/2.49	   isNat(0) -> tt
6.00/2.49	   isNat(s(V1)) -> isNat(V1)
6.00/2.49	   isNatIList(cons(V1, V2)) -> and(isNat(V1), isNatIList(V2))
6.00/2.49	   isNatList(cons(V1, V2)) -> and(isNat(V1), isNatList(V2))
6.00/2.49	   length(cons(N, L)) -> U11(and(isNatList(L), isNat(N)), L)
6.00/2.49	
6.00/2.49	The set Q consists of the following terms:
6.00/2.49	
6.00/2.49	   zeros
6.00/2.49	   U11(tt, x0)
6.00/2.49	   and(tt, x0)
6.00/2.49	   isNat(0)
6.00/2.49	   isNat(s(x0))
6.00/2.49	   isNatIList(cons(x0, x1))
6.00/2.49	   isNatList(cons(x0, x1))
6.00/2.49	   length(cons(x0, x1))
6.00/2.49	
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(32) QCSDependencyGraphProof (EQUIVALENT)
6.00/2.49	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 1 less node.
6.00/2.49	
6.00/2.49	----------------------------------------
6.00/2.49	
6.00/2.49	(33)
6.00/2.49	TRUE
6.28/2.57	EOF