3.80/1.84	YES
3.80/1.86	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.80/1.86	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.80/1.86	
3.80/1.86	
3.80/1.86	Termination w.r.t. Q of the given QTRS could be proven:
3.80/1.86	
3.80/1.86	(0) QTRS
3.80/1.86	(1) DependencyPairsProof [EQUIVALENT, 0 ms]
3.80/1.86	(2) QDP
3.80/1.86	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
3.80/1.86	(4) AND
3.80/1.86	    (5) QDP
3.80/1.86	        (6) UsableRulesProof [EQUIVALENT, 0 ms]
3.80/1.86	        (7) QDP
3.80/1.86	        (8) QReductionProof [EQUIVALENT, 0 ms]
3.80/1.86	        (9) QDP
3.80/1.86	        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.80/1.86	        (11) YES
3.80/1.86	    (12) QDP
3.80/1.86	        (13) QDPOrderProof [EQUIVALENT, 0 ms]
3.80/1.86	        (14) QDP
3.80/1.86	        (15) PisEmptyProof [EQUIVALENT, 0 ms]
3.80/1.86	        (16) YES
3.80/1.86	
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(0)
3.80/1.86	Obligation:
3.80/1.86	Q restricted rewrite system:
3.80/1.86	The TRS R consists of the following rules:
3.80/1.86	
3.80/1.86	   f(0) -> true
3.80/1.86	   f(1) -> false
3.80/1.86	   f(s(x)) -> f(x)
3.80/1.86	   if(true, x, y) -> x
3.80/1.86	   if(false, x, y) -> y
3.80/1.86	   g(s(x), s(y)) -> if(f(x), s(x), s(y))
3.80/1.86	   g(x, c(y)) -> g(x, g(s(c(y)), y))
3.80/1.86	
3.80/1.86	The set Q consists of the following terms:
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(1) DependencyPairsProof (EQUIVALENT)
3.80/1.86	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(2)
3.80/1.86	Obligation:
3.80/1.86	Q DP problem:
3.80/1.86	The TRS P consists of the following rules:
3.80/1.86	
3.80/1.86	   F(s(x)) -> F(x)
3.80/1.86	   G(s(x), s(y)) -> IF(f(x), s(x), s(y))
3.80/1.86	   G(s(x), s(y)) -> F(x)
3.80/1.86	   G(x, c(y)) -> G(x, g(s(c(y)), y))
3.80/1.86	   G(x, c(y)) -> G(s(c(y)), y)
3.80/1.86	
3.80/1.86	The TRS R consists of the following rules:
3.80/1.86	
3.80/1.86	   f(0) -> true
3.80/1.86	   f(1) -> false
3.80/1.86	   f(s(x)) -> f(x)
3.80/1.86	   if(true, x, y) -> x
3.80/1.86	   if(false, x, y) -> y
3.80/1.86	   g(s(x), s(y)) -> if(f(x), s(x), s(y))
3.80/1.86	   g(x, c(y)) -> g(x, g(s(c(y)), y))
3.80/1.86	
3.80/1.86	The set Q consists of the following terms:
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	We have to consider all minimal (P,Q,R)-chains.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(3) DependencyGraphProof (EQUIVALENT)
3.80/1.86	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 2 less nodes.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(4)
3.80/1.86	Complex Obligation (AND)
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(5)
3.80/1.86	Obligation:
3.80/1.86	Q DP problem:
3.80/1.86	The TRS P consists of the following rules:
3.80/1.86	
3.80/1.86	   F(s(x)) -> F(x)
3.80/1.86	
3.80/1.86	The TRS R consists of the following rules:
3.80/1.86	
3.80/1.86	   f(0) -> true
3.80/1.86	   f(1) -> false
3.80/1.86	   f(s(x)) -> f(x)
3.80/1.86	   if(true, x, y) -> x
3.80/1.86	   if(false, x, y) -> y
3.80/1.86	   g(s(x), s(y)) -> if(f(x), s(x), s(y))
3.80/1.86	   g(x, c(y)) -> g(x, g(s(c(y)), y))
3.80/1.86	
3.80/1.86	The set Q consists of the following terms:
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	We have to consider all minimal (P,Q,R)-chains.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(6) UsableRulesProof (EQUIVALENT)
3.80/1.86	As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(7)
3.80/1.86	Obligation:
3.80/1.86	Q DP problem:
3.80/1.86	The TRS P consists of the following rules:
3.80/1.86	
3.80/1.86	   F(s(x)) -> F(x)
3.80/1.86	
3.80/1.86	R is empty.
3.80/1.86	The set Q consists of the following terms:
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	We have to consider all minimal (P,Q,R)-chains.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(8) QReductionProof (EQUIVALENT)
3.80/1.86	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(9)
3.80/1.86	Obligation:
3.80/1.86	Q DP problem:
3.80/1.86	The TRS P consists of the following rules:
3.80/1.86	
3.80/1.86	   F(s(x)) -> F(x)
3.80/1.86	
3.80/1.86	R is empty.
3.80/1.86	Q is empty.
3.80/1.86	We have to consider all minimal (P,Q,R)-chains.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(10) QDPSizeChangeProof (EQUIVALENT)
3.80/1.86	By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 
3.80/1.86	
3.80/1.86	From the DPs we obtained the following set of size-change graphs:
3.80/1.86	*F(s(x)) -> F(x)
3.80/1.86	The graph contains the following edges 1 > 1
3.80/1.86	
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(11)
3.80/1.86	YES
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(12)
3.80/1.86	Obligation:
3.80/1.86	Q DP problem:
3.80/1.86	The TRS P consists of the following rules:
3.80/1.86	
3.80/1.86	   G(x, c(y)) -> G(s(c(y)), y)
3.80/1.86	   G(x, c(y)) -> G(x, g(s(c(y)), y))
3.80/1.86	
3.80/1.86	The TRS R consists of the following rules:
3.80/1.86	
3.80/1.86	   f(0) -> true
3.80/1.86	   f(1) -> false
3.80/1.86	   f(s(x)) -> f(x)
3.80/1.86	   if(true, x, y) -> x
3.80/1.86	   if(false, x, y) -> y
3.80/1.86	   g(s(x), s(y)) -> if(f(x), s(x), s(y))
3.80/1.86	   g(x, c(y)) -> g(x, g(s(c(y)), y))
3.80/1.86	
3.80/1.86	The set Q consists of the following terms:
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	We have to consider all minimal (P,Q,R)-chains.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(13) QDPOrderProof (EQUIVALENT)
3.80/1.86	We use the reduction pair processor [LPAR04,JAR06].
3.80/1.86	
3.80/1.86	
3.80/1.86	The following pairs can be oriented strictly and are deleted.
3.80/1.86	
3.80/1.86	   G(x, c(y)) -> G(s(c(y)), y)
3.80/1.86	   G(x, c(y)) -> G(x, g(s(c(y)), y))
3.80/1.86	The remaining pairs can at least be oriented weakly.
3.80/1.86	Used ordering:  Combined order from the following AFS and order.
3.80/1.86	G(x1, x2)  =  x2
3.80/1.86	
3.80/1.86	c(x1)  =  c(x1)
3.80/1.86	
3.80/1.86	g(x1, x2)  =  g
3.80/1.86	
3.80/1.86	if(x1, x2, x3)  =  if(x2, x3)
3.80/1.86	
3.80/1.86	s(x1)  =  s
3.80/1.86	
3.80/1.86	
3.80/1.86	Knuth-Bendix order [KBO] with precedence:trivial
3.80/1.86	
3.80/1.86	and weight map:
3.80/1.86	
3.80/1.86	   s=1
3.80/1.86	   c_1=4
3.80/1.86	   g=4
3.80/1.86	   if_2=1
3.80/1.86	
3.80/1.86	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
3.80/1.86	
3.80/1.86	   g(s(x), s(y)) -> if(f(x), s(x), s(y))
3.80/1.86	   g(x, c(y)) -> g(x, g(s(c(y)), y))
3.80/1.86	   if(true, x, y) -> x
3.80/1.86	   if(false, x, y) -> y
3.80/1.86	
3.80/1.86	
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(14)
3.80/1.86	Obligation:
3.80/1.86	Q DP problem:
3.80/1.86	P is empty.
3.80/1.86	The TRS R consists of the following rules:
3.80/1.86	
3.80/1.86	   f(0) -> true
3.80/1.86	   f(1) -> false
3.80/1.86	   f(s(x)) -> f(x)
3.80/1.86	   if(true, x, y) -> x
3.80/1.86	   if(false, x, y) -> y
3.80/1.86	   g(s(x), s(y)) -> if(f(x), s(x), s(y))
3.80/1.86	   g(x, c(y)) -> g(x, g(s(c(y)), y))
3.80/1.86	
3.80/1.86	The set Q consists of the following terms:
3.80/1.86	
3.80/1.86	   f(0)
3.80/1.86	   f(1)
3.80/1.86	   f(s(x0))
3.80/1.86	   if(true, x0, x1)
3.80/1.86	   if(false, x0, x1)
3.80/1.86	   g(s(x0), s(x1))
3.80/1.86	   g(x0, c(x1))
3.80/1.86	
3.80/1.86	We have to consider all minimal (P,Q,R)-chains.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(15) PisEmptyProof (EQUIVALENT)
3.80/1.86	The TRS P is empty. Hence, there is no (P,Q,R) chain.
3.80/1.86	----------------------------------------
3.80/1.86	
3.80/1.86	(16)
3.80/1.86	YES
3.80/1.88	EOF