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