3.46/1.57	YES
3.46/1.58	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.46/1.58	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.46/1.58	
3.46/1.58	
3.46/1.58	Termination of the given CSR could be proven:
3.46/1.58	
3.46/1.58	(0) CSR
3.46/1.58	(1) CSRRRRProof [EQUIVALENT, 76 ms]
3.46/1.58	(2) CSR
3.46/1.58	(3) CSRRRRProof [EQUIVALENT, 19 ms]
3.46/1.58	(4) CSR
3.46/1.58	(5) CSRRRRProof [EQUIVALENT, 0 ms]
3.46/1.58	(6) CSR
3.46/1.58	(7) CSRRRRProof [EQUIVALENT, 6 ms]
3.46/1.58	(8) CSR
3.46/1.58	(9) CSRRRRProof [EQUIVALENT, 0 ms]
3.46/1.58	(10) CSR
3.46/1.58	(11) RisEmptyProof [EQUIVALENT, 0 ms]
3.46/1.58	(12) YES
3.46/1.58	
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(0)
3.46/1.58	Obligation:
3.46/1.58	Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   tail(cons(X, XS)) -> XS
3.46/1.58	   repItems(nil) -> nil
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	zip: {1, 2}
3.46/1.58	pair: {1, 2}
3.46/1.58	tail: {1}
3.46/1.58	repItems: {1}
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(1) CSRRRRProof (EQUIVALENT)
3.46/1.58	The following CSR is given: Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   tail(cons(X, XS)) -> XS
3.46/1.58	   repItems(nil) -> nil
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	zip: {1, 2}
3.46/1.58	pair: {1, 2}
3.46/1.58	tail: {1}
3.46/1.58	repItems: {1}
3.46/1.58	Used ordering:
3.46/1.58	Polynomial interpretation [POLO]:
3.46/1.58	
3.46/1.58	   POL(0) = 0
3.46/1.58	   POL(cons(x_1, x_2)) = 2*x_1 + x_2
3.46/1.58	   POL(incr(x_1)) = 2*x_1
3.46/1.58	   POL(nil) = 0
3.46/1.58	   POL(oddNs) = 0
3.46/1.58	   POL(pair(x_1, x_2)) = x_1 + x_2
3.46/1.58	   POL(pairNs) = 0
3.46/1.58	   POL(repItems(x_1)) = 2 + 2*x_1
3.46/1.58	   POL(s(x_1)) = 2*x_1
3.46/1.58	   POL(tail(x_1)) = 2*x_1
3.46/1.58	   POL(take(x_1, x_2)) = x_1 + 2*x_2
3.46/1.58	   POL(zip(x_1, x_2)) = 2*x_1 + 2*x_2
3.46/1.58	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.46/1.58	
3.46/1.58	   repItems(nil) -> nil
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(2)
3.46/1.58	Obligation:
3.46/1.58	Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   tail(cons(X, XS)) -> XS
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	zip: {1, 2}
3.46/1.58	pair: {1, 2}
3.46/1.58	tail: {1}
3.46/1.58	repItems: {1}
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(3) CSRRRRProof (EQUIVALENT)
3.46/1.58	The following CSR is given: Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   tail(cons(X, XS)) -> XS
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	zip: {1, 2}
3.46/1.58	pair: {1, 2}
3.46/1.58	tail: {1}
3.46/1.58	repItems: {1}
3.46/1.58	Used ordering:
3.46/1.58	Polynomial interpretation [POLO]:
3.46/1.58	
3.46/1.58	   POL(0) = 0
3.46/1.58	   POL(cons(x_1, x_2)) = 2*x_1 + x_2
3.46/1.58	   POL(incr(x_1)) = x_1
3.46/1.58	   POL(nil) = 0
3.46/1.58	   POL(oddNs) = 0
3.46/1.58	   POL(pair(x_1, x_2)) = x_1 + x_2
3.46/1.58	   POL(pairNs) = 0
3.46/1.58	   POL(repItems(x_1)) = 2 + 2*x_1
3.46/1.58	   POL(s(x_1)) = x_1
3.46/1.58	   POL(tail(x_1)) = 1 + 2*x_1
3.46/1.58	   POL(take(x_1, x_2)) = x_1 + 2*x_2
3.46/1.58	   POL(zip(x_1, x_2)) = x_1 + 2*x_2
3.46/1.58	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.46/1.58	
3.46/1.58	   tail(cons(X, XS)) -> XS
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(4)
3.46/1.58	Obligation:
3.46/1.58	Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	zip: {1, 2}
3.46/1.58	pair: {1, 2}
3.46/1.58	repItems: {1}
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(5) CSRRRRProof (EQUIVALENT)
3.46/1.58	The following CSR is given: Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	zip: {1, 2}
3.46/1.58	pair: {1, 2}
3.46/1.58	repItems: {1}
3.46/1.58	Used ordering:
3.46/1.58	Polynomial interpretation [POLO]:
3.46/1.58	
3.46/1.58	   POL(0) = 0
3.46/1.58	   POL(cons(x_1, x_2)) = 2 + 2*x_1
3.46/1.58	   POL(incr(x_1)) = x_1
3.46/1.58	   POL(nil) = 1
3.46/1.58	   POL(oddNs) = 2
3.46/1.58	   POL(pair(x_1, x_2)) = 2*x_1 + x_2
3.46/1.58	   POL(pairNs) = 2
3.46/1.58	   POL(repItems(x_1)) = 1 + 2*x_1
3.46/1.58	   POL(s(x_1)) = x_1
3.46/1.58	   POL(take(x_1, x_2)) = 1 + x_1 + 2*x_2
3.46/1.58	   POL(zip(x_1, x_2)) = 2*x_1 + 2*x_2
3.46/1.58	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.46/1.58	
3.46/1.58	   take(s(N), cons(X, XS)) -> cons(X, take(N, XS))
3.46/1.58	   zip(nil, XS) -> nil
3.46/1.58	   zip(X, nil) -> nil
3.46/1.58	   zip(cons(X, XS), cons(Y, YS)) -> cons(pair(X, Y), zip(XS, YS))
3.46/1.58	   repItems(cons(X, XS)) -> cons(X, cons(X, repItems(XS)))
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(6)
3.46/1.58	Obligation:
3.46/1.58	Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(7) CSRRRRProof (EQUIVALENT)
3.46/1.58	The following CSR is given: Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	s: {1}
3.46/1.58	take: {1, 2}
3.46/1.58	nil: empty set
3.46/1.58	Used ordering:
3.46/1.58	Polynomial interpretation [POLO]:
3.46/1.58	
3.46/1.58	   POL(0) = 0
3.46/1.58	   POL(cons(x_1, x_2)) = 2*x_1
3.46/1.58	   POL(incr(x_1)) = 1 + 2*x_1
3.46/1.58	   POL(nil) = 1
3.46/1.58	   POL(oddNs) = 2
3.46/1.58	   POL(pairNs) = 0
3.46/1.58	   POL(s(x_1)) = 2*x_1
3.46/1.58	   POL(take(x_1, x_2)) = 2 + x_1 + x_2
3.46/1.58	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.46/1.58	
3.46/1.58	   oddNs -> incr(pairNs)
3.46/1.58	   incr(cons(X, XS)) -> cons(s(X), incr(XS))
3.46/1.58	   take(0, XS) -> nil
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(8)
3.46/1.58	Obligation:
3.46/1.58	Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(9) CSRRRRProof (EQUIVALENT)
3.46/1.58	The following CSR is given: Context-sensitive rewrite system:
3.46/1.58	The TRS R consists of the following rules:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	
3.46/1.58	The replacement map contains the following entries:
3.46/1.58	
3.46/1.58	pairNs: empty set
3.46/1.58	cons: {1}
3.46/1.58	0: empty set
3.46/1.58	incr: {1}
3.46/1.58	oddNs: empty set
3.46/1.58	Used ordering:
3.46/1.58	Polynomial interpretation [POLO]:
3.46/1.58	
3.46/1.58	   POL(0) = 0
3.46/1.58	   POL(cons(x_1, x_2)) = 1 + x_1
3.46/1.58	   POL(incr(x_1)) = 1 + 2*x_1
3.46/1.58	   POL(oddNs) = 0
3.46/1.58	   POL(pairNs) = 2
3.46/1.58	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.46/1.58	
3.46/1.58	   pairNs -> cons(0, incr(oddNs))
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(10)
3.46/1.58	Obligation:
3.46/1.58	Context-sensitive rewrite system:
3.46/1.58	R is empty.
3.46/1.58	
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(11) RisEmptyProof (EQUIVALENT)
3.46/1.58	The CSR R is empty. Hence, termination is trivially proven.
3.46/1.58	----------------------------------------
3.46/1.58	
3.46/1.58	(12)
3.46/1.58	YES
3.46/1.60	EOF