4.17/1.93	YES
4.17/1.94	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
4.17/1.94	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.17/1.94	
4.17/1.94	
4.17/1.94	Termination of the given RelTRS could be proven:
4.17/1.94	
4.17/1.94	(0) RelTRS
4.17/1.94	(1) RelTRStoQDPProof [SOUND, 0 ms]
4.17/1.94	(2) QDP
4.17/1.94	(3) MRRProof [EQUIVALENT, 53 ms]
4.17/1.94	(4) QDP
4.17/1.94	(5) QDPOrderProof [EQUIVALENT, 36 ms]
4.17/1.94	(6) QDP
4.17/1.94	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
4.17/1.94	(8) AND
4.17/1.94	    (9) QDP
4.17/1.94	        (10) QDPOrderProof [EQUIVALENT, 6 ms]
4.17/1.94	        (11) QDP
4.17/1.94	        (12) PisEmptyProof [EQUIVALENT, 0 ms]
4.17/1.94	        (13) YES
4.17/1.94	    (14) QDP
4.17/1.94	        (15) QDPOrderProof [EQUIVALENT, 0 ms]
4.17/1.94	        (16) QDP
4.17/1.94	        (17) PisEmptyProof [EQUIVALENT, 0 ms]
4.17/1.94	        (18) YES
4.17/1.94	
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(0)
4.17/1.94	Obligation:
4.17/1.94	Relative term rewrite system:
4.17/1.94	The relative TRS consists of the following R rules:
4.17/1.94	
4.17/1.94	   f(c(s(x), y)) -> f(c(x, s(y)))
4.17/1.94	   f(c(s(x), s(y))) -> g(c(x, y))
4.17/1.94	   g(c(x, s(y))) -> g(c(s(x), y))
4.17/1.94	   g(c(s(x), s(y))) -> f(c(x, y))
4.17/1.94	
4.17/1.94	The relative TRS consists of the following S rules:
4.17/1.94	
4.17/1.94	   rand(x) -> x
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(1) RelTRStoQDPProof (SOUND)
4.17/1.94	The relative termination problem is root-restricted. We can therefore treat it as a dependency pair problem.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(2)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	The TRS P consists of the following rules:
4.17/1.94	
4.17/1.94	   f(c(s(x), y)) -> f(c(x, s(y)))
4.17/1.94	   f(c(s(x), s(y))) -> g(c(x, y))
4.17/1.94	   g(c(x, s(y))) -> g(c(s(x), y))
4.17/1.94	   g(c(s(x), s(y))) -> f(c(x, y))
4.17/1.94	
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> x
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(3) MRRProof (EQUIVALENT)
4.17/1.94	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
4.17/1.94	
4.17/1.94	
4.17/1.94	Strictly oriented rules of the TRS R:
4.17/1.94	
4.17/1.94	   rand(x) -> x
4.17/1.94	
4.17/1.94	Used ordering: Polynomial interpretation [POLO]:
4.17/1.94	
4.17/1.94	   POL(c(x_1, x_2)) = x_1 + 2*x_2
4.17/1.94	   POL(f(x_1)) = 2*x_1
4.17/1.94	   POL(g(x_1)) = 2*x_1
4.17/1.94	   POL(rand(x_1)) = 1 + 2*x_1
4.17/1.94	   POL(s(x_1)) = x_1
4.17/1.94	
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(4)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	The TRS P consists of the following rules:
4.17/1.94	
4.17/1.94	   f(c(s(x), y)) -> f(c(x, s(y)))
4.17/1.94	   f(c(s(x), s(y))) -> g(c(x, y))
4.17/1.94	   g(c(x, s(y))) -> g(c(s(x), y))
4.17/1.94	   g(c(s(x), s(y))) -> f(c(x, y))
4.17/1.94	
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(5) QDPOrderProof (EQUIVALENT)
4.17/1.94	We use the reduction pair processor [LPAR04,JAR06].
4.17/1.94	
4.17/1.94	
4.17/1.94	The following pairs can be oriented strictly and are deleted.
4.17/1.94	
4.17/1.94	   f(c(s(x), s(y))) -> g(c(x, y))
4.17/1.94	   g(c(s(x), s(y))) -> f(c(x, y))
4.17/1.94	The remaining pairs can at least be oriented weakly.
4.17/1.94	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
4.17/1.94	
4.17/1.94	POL( rand_1(x_1) ) = 2
4.17/1.94	POL( s_1(x_1) ) = x_1 + 2
4.17/1.94	POL( f_1(x_1) ) = x_1 + 2
4.17/1.94	POL( c_2(x_1, x_2) ) = 2x_1 + 2x_2 + 2
4.17/1.94	POL( g_1(x_1) ) = max{0, x_1 - 2}
4.17/1.94	
4.17/1.94	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(6)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	The TRS P consists of the following rules:
4.17/1.94	
4.17/1.94	   f(c(s(x), y)) -> f(c(x, s(y)))
4.17/1.94	   g(c(x, s(y))) -> g(c(s(x), y))
4.17/1.94	
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(7) DependencyGraphProof (EQUIVALENT)
4.17/1.94	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(8)
4.17/1.94	Complex Obligation (AND)
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(9)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	The TRS P consists of the following rules:
4.17/1.94	
4.17/1.94	   g(c(x, s(y))) -> g(c(s(x), y))
4.17/1.94	
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(10) QDPOrderProof (EQUIVALENT)
4.17/1.94	We use the reduction pair processor [LPAR04,JAR06].
4.17/1.94	
4.17/1.94	
4.17/1.94	The following pairs can be oriented strictly and are deleted.
4.17/1.94	
4.17/1.94	   g(c(x, s(y))) -> g(c(s(x), y))
4.17/1.94	The remaining pairs can at least be oriented weakly.
4.17/1.94	Used ordering:  Combined order from the following AFS and order.
4.17/1.94	g(x1)  =  x1
4.17/1.94	
4.17/1.94	c(x1, x2)  =  x2
4.17/1.94	
4.17/1.94	s(x1)  =  s(x1)
4.17/1.94	
4.17/1.94	rand(x1)  =  rand
4.17/1.94	
4.17/1.94	
4.17/1.94	Knuth-Bendix order [KBO] with precedence:trivial
4.17/1.94	
4.17/1.94	and weight map:
4.17/1.94	
4.17/1.94	   s_1=1
4.17/1.94	   rand=1
4.17/1.94	
4.17/1.94	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(11)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	P is empty.
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(12) PisEmptyProof (EQUIVALENT)
4.17/1.94	The TRS P is empty. Hence, there is no (P,Q,R) chain.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(13)
4.17/1.94	YES
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(14)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	The TRS P consists of the following rules:
4.17/1.94	
4.17/1.94	   f(c(s(x), y)) -> f(c(x, s(y)))
4.17/1.94	
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(15) QDPOrderProof (EQUIVALENT)
4.17/1.94	We use the reduction pair processor [LPAR04,JAR06].
4.17/1.94	
4.17/1.94	
4.17/1.94	The following pairs can be oriented strictly and are deleted.
4.17/1.94	
4.17/1.94	   f(c(s(x), y)) -> f(c(x, s(y)))
4.17/1.94	The remaining pairs can at least be oriented weakly.
4.17/1.94	Used ordering:  Combined order from the following AFS and order.
4.17/1.94	f(x1)  =  x1
4.17/1.94	
4.17/1.94	c(x1, x2)  =  x1
4.17/1.94	
4.17/1.94	s(x1)  =  s(x1)
4.17/1.94	
4.17/1.94	rand(x1)  =  rand
4.17/1.94	
4.17/1.94	
4.17/1.94	Knuth-Bendix order [KBO] with precedence:trivial
4.17/1.94	
4.17/1.94	and weight map:
4.17/1.94	
4.17/1.94	   s_1=1
4.17/1.94	   rand=1
4.17/1.94	
4.17/1.94	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(16)
4.17/1.94	Obligation:
4.17/1.94	Q DP problem:
4.17/1.94	P is empty.
4.17/1.94	The TRS R consists of the following rules:
4.17/1.94	
4.17/1.94	   rand(x) -> rand(s(x))
4.17/1.94	
4.17/1.94	Q is empty.
4.17/1.94	We have to consider all (P,Q,R)-chains.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(17) PisEmptyProof (EQUIVALENT)
4.17/1.94	The TRS P is empty. Hence, there is no (P,Q,R) chain.
4.17/1.94	----------------------------------------
4.17/1.94	
4.17/1.94	(18)
4.17/1.94	YES
4.17/1.97	EOF