3.24/1.62	YES
3.34/1.63	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.34/1.63	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.34/1.63	
3.34/1.63	
3.34/1.63	Termination of the given CSR could be proven:
3.34/1.63	
3.34/1.63	(0) CSR
3.34/1.63	(1) CSRRRRProof [EQUIVALENT, 46 ms]
3.34/1.63	(2) CSR
3.34/1.63	(3) CSRRRRProof [EQUIVALENT, 0 ms]
3.34/1.63	(4) CSR
3.34/1.63	(5) CSRRRRProof [EQUIVALENT, 11 ms]
3.34/1.63	(6) CSR
3.34/1.63	(7) CSRRRRProof [EQUIVALENT, 0 ms]
3.34/1.63	(8) CSR
3.34/1.63	(9) RisEmptyProof [EQUIVALENT, 0 ms]
3.34/1.63	(10) YES
3.34/1.63	
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(0)
3.34/1.63	Obligation:
3.34/1.63	Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   if(false, X, Y) -> Y
3.34/1.63	   add(0, X) -> X
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(0, X) -> nil
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	and: {1}
3.34/1.63	true: empty set
3.34/1.63	false: empty set
3.34/1.63	if: {1}
3.34/1.63	add: {1}
3.34/1.63	0: empty set
3.34/1.63	s: empty set
3.34/1.63	first: {1, 2}
3.34/1.63	nil: empty set
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(1) CSRRRRProof (EQUIVALENT)
3.34/1.63	The following CSR is given: Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   if(false, X, Y) -> Y
3.34/1.63	   add(0, X) -> X
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(0, X) -> nil
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	and: {1}
3.34/1.63	true: empty set
3.34/1.63	false: empty set
3.34/1.63	if: {1}
3.34/1.63	add: {1}
3.34/1.63	0: empty set
3.34/1.63	s: empty set
3.34/1.63	first: {1, 2}
3.34/1.63	nil: empty set
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	Used ordering:
3.34/1.63	Polynomial interpretation [POLO]:
3.34/1.63	
3.34/1.63	   POL(0) = 1
3.34/1.63	   POL(add(x_1, x_2)) = 1 + x_1 + x_2
3.34/1.63	   POL(and(x_1, x_2)) = x_1 + x_2
3.34/1.63	   POL(cons(x_1, x_2)) = x_2
3.34/1.63	   POL(false) = 0
3.34/1.63	   POL(first(x_1, x_2)) = 1 + x_1 + x_2
3.34/1.63	   POL(from(x_1)) = 1 + x_1
3.34/1.63	   POL(if(x_1, x_2, x_3)) = x_1 + x_2 + x_3
3.34/1.63	   POL(nil) = 0
3.34/1.63	   POL(s(x_1)) = x_1
3.34/1.63	   POL(true) = 0
3.34/1.63	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.34/1.63	
3.34/1.63	   add(0, X) -> X
3.34/1.63	   first(0, X) -> nil
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(2)
3.34/1.63	Obligation:
3.34/1.63	Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   if(false, X, Y) -> Y
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	and: {1}
3.34/1.63	true: empty set
3.34/1.63	false: empty set
3.34/1.63	if: {1}
3.34/1.63	add: {1}
3.34/1.63	s: empty set
3.34/1.63	first: {1, 2}
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(3) CSRRRRProof (EQUIVALENT)
3.34/1.63	The following CSR is given: Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   if(false, X, Y) -> Y
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	and: {1}
3.34/1.63	true: empty set
3.34/1.63	false: empty set
3.34/1.63	if: {1}
3.34/1.63	add: {1}
3.34/1.63	s: empty set
3.34/1.63	first: {1, 2}
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	Used ordering:
3.34/1.63	Polynomial interpretation [POLO]:
3.34/1.63	
3.34/1.63	   POL(add(x_1, x_2)) = 1 + x_1 + x_2
3.34/1.63	   POL(and(x_1, x_2)) = x_1 + x_2
3.34/1.63	   POL(cons(x_1, x_2)) = x_2
3.34/1.63	   POL(false) = 1
3.34/1.63	   POL(first(x_1, x_2)) = 1 + x_1 + x_2
3.34/1.63	   POL(from(x_1)) = 1 + x_1
3.34/1.63	   POL(if(x_1, x_2, x_3)) = x_1 + x_2 + x_3
3.34/1.63	   POL(s(x_1)) = x_1
3.34/1.63	   POL(true) = 0
3.34/1.63	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.34/1.63	
3.34/1.63	   if(false, X, Y) -> Y
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(4)
3.34/1.63	Obligation:
3.34/1.63	Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	and: {1}
3.34/1.63	true: empty set
3.34/1.63	false: empty set
3.34/1.63	if: {1}
3.34/1.63	add: {1}
3.34/1.63	s: empty set
3.34/1.63	first: {1, 2}
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(5) CSRRRRProof (EQUIVALENT)
3.34/1.63	The following CSR is given: Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	and: {1}
3.34/1.63	true: empty set
3.34/1.63	false: empty set
3.34/1.63	if: {1}
3.34/1.63	add: {1}
3.34/1.63	s: empty set
3.34/1.63	first: {1, 2}
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	Used ordering:
3.34/1.63	Polynomial interpretation [POLO]:
3.34/1.63	
3.34/1.63	   POL(add(x_1, x_2)) = 2*x_1 + 2*x_2
3.34/1.63	   POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2
3.34/1.63	   POL(cons(x_1, x_2)) = 0
3.34/1.63	   POL(false) = 2
3.34/1.63	   POL(first(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
3.34/1.63	   POL(from(x_1)) = 0
3.34/1.63	   POL(if(x_1, x_2, x_3)) = 2*x_1 + x_2
3.34/1.63	   POL(s(x_1)) = 2
3.34/1.63	   POL(true) = 2
3.34/1.63	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.34/1.63	
3.34/1.63	   and(true, X) -> X
3.34/1.63	   and(false, Y) -> false
3.34/1.63	   if(true, X, Y) -> X
3.34/1.63	   add(s(X), Y) -> s(add(X, Y))
3.34/1.63	   first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(6)
3.34/1.63	Obligation:
3.34/1.63	Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	s: empty set
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(7) CSRRRRProof (EQUIVALENT)
3.34/1.63	The following CSR is given: Context-sensitive rewrite system:
3.34/1.63	The TRS R consists of the following rules:
3.34/1.63	
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	The replacement map contains the following entries:
3.34/1.63	
3.34/1.63	s: empty set
3.34/1.63	cons: empty set
3.34/1.63	from: empty set
3.34/1.63	Used ordering:
3.34/1.63	Polynomial interpretation [POLO]:
3.34/1.63	
3.34/1.63	   POL(cons(x_1, x_2)) = 2*x_1
3.34/1.63	   POL(from(x_1)) = 1 + 2*x_1
3.34/1.63	   POL(s(x_1)) = 0
3.34/1.63	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.34/1.63	
3.34/1.63	   from(X) -> cons(X, from(s(X)))
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(8)
3.34/1.63	Obligation:
3.34/1.63	Context-sensitive rewrite system:
3.34/1.63	R is empty.
3.34/1.63	
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(9) RisEmptyProof (EQUIVALENT)
3.34/1.63	The CSR R is empty. Hence, termination is trivially proven.
3.34/1.63	----------------------------------------
3.34/1.63	
3.34/1.63	(10)
3.34/1.63	YES
3.34/1.68	EOF