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