3.53/1.74	YES
3.53/1.74	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.53/1.74	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.53/1.74	
3.53/1.74	
3.53/1.74	Termination w.r.t. Q of the given QTRS could be proven:
3.53/1.74	
3.53/1.74	(0) QTRS
3.53/1.74	(1) DependencyPairsProof [EQUIVALENT, 0 ms]
3.53/1.74	(2) QDP
3.53/1.74	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
3.53/1.74	(4) QDP
3.53/1.74	(5) UsableRulesProof [EQUIVALENT, 0 ms]
3.53/1.74	(6) QDP
3.53/1.74	(7) QReductionProof [EQUIVALENT, 0 ms]
3.53/1.74	(8) QDP
3.53/1.74	(9) QDPSizeChangeProof [EQUIVALENT, 1 ms]
3.53/1.74	(10) YES
3.53/1.74	
3.53/1.74	
3.53/1.74	----------------------------------------
3.53/1.74	
3.53/1.74	(0)
3.53/1.74	Obligation:
3.53/1.74	Q restricted rewrite system:
3.53/1.74	The TRS R consists of the following rules:
3.53/1.74	
3.53/1.74	   f(0, 1, g(x, y), z) -> f(g(x, y), g(x, y), g(x, y), h(x))
3.53/1.74	   g(0, 1) -> 0
3.53/1.74	   g(0, 1) -> 1
3.53/1.74	   h(g(x, y)) -> h(x)
3.53/1.74	
3.53/1.74	The set Q consists of the following terms:
3.53/1.74	
3.53/1.74	   f(0, 1, g(x0, x1), x2)
3.53/1.74	   g(0, 1)
3.53/1.74	   h(g(x0, x1))
3.53/1.74	
3.53/1.74	
3.53/1.74	----------------------------------------
3.53/1.74	
3.53/1.74	(1) DependencyPairsProof (EQUIVALENT)
3.53/1.74	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.53/1.74	----------------------------------------
3.53/1.75	
3.53/1.75	(2)
3.53/1.75	Obligation:
3.53/1.75	Q DP problem:
3.53/1.75	The TRS P consists of the following rules:
3.53/1.75	
3.53/1.75	   F(0, 1, g(x, y), z) -> F(g(x, y), g(x, y), g(x, y), h(x))
3.53/1.75	   F(0, 1, g(x, y), z) -> H(x)
3.53/1.75	   H(g(x, y)) -> H(x)
3.53/1.75	
3.53/1.75	The TRS R consists of the following rules:
3.53/1.75	
3.53/1.75	   f(0, 1, g(x, y), z) -> f(g(x, y), g(x, y), g(x, y), h(x))
3.53/1.75	   g(0, 1) -> 0
3.53/1.75	   g(0, 1) -> 1
3.53/1.75	   h(g(x, y)) -> h(x)
3.53/1.75	
3.53/1.75	The set Q consists of the following terms:
3.53/1.75	
3.53/1.75	   f(0, 1, g(x0, x1), x2)
3.53/1.75	   g(0, 1)
3.53/1.75	   h(g(x0, x1))
3.53/1.75	
3.53/1.75	We have to consider all minimal (P,Q,R)-chains.
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(3) DependencyGraphProof (EQUIVALENT)
3.53/1.75	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes.
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(4)
3.53/1.75	Obligation:
3.53/1.75	Q DP problem:
3.53/1.75	The TRS P consists of the following rules:
3.53/1.75	
3.53/1.75	   H(g(x, y)) -> H(x)
3.53/1.75	
3.53/1.75	The TRS R consists of the following rules:
3.53/1.75	
3.53/1.75	   f(0, 1, g(x, y), z) -> f(g(x, y), g(x, y), g(x, y), h(x))
3.53/1.75	   g(0, 1) -> 0
3.53/1.75	   g(0, 1) -> 1
3.53/1.75	   h(g(x, y)) -> h(x)
3.53/1.75	
3.53/1.75	The set Q consists of the following terms:
3.53/1.75	
3.53/1.75	   f(0, 1, g(x0, x1), x2)
3.53/1.75	   g(0, 1)
3.53/1.75	   h(g(x0, x1))
3.53/1.75	
3.53/1.75	We have to consider all minimal (P,Q,R)-chains.
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(5) UsableRulesProof (EQUIVALENT)
3.53/1.75	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.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(6)
3.53/1.75	Obligation:
3.53/1.75	Q DP problem:
3.53/1.75	The TRS P consists of the following rules:
3.53/1.75	
3.53/1.75	   H(g(x, y)) -> H(x)
3.53/1.75	
3.53/1.75	R is empty.
3.53/1.75	The set Q consists of the following terms:
3.53/1.75	
3.53/1.75	   f(0, 1, g(x0, x1), x2)
3.53/1.75	   g(0, 1)
3.53/1.75	   h(g(x0, x1))
3.53/1.75	
3.53/1.75	We have to consider all minimal (P,Q,R)-chains.
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(7) QReductionProof (EQUIVALENT)
3.53/1.75	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.53/1.75	
3.53/1.75	   f(0, 1, g(x0, x1), x2)
3.53/1.75	   h(g(x0, x1))
3.53/1.75	
3.53/1.75	
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(8)
3.53/1.75	Obligation:
3.53/1.75	Q DP problem:
3.53/1.75	The TRS P consists of the following rules:
3.53/1.75	
3.53/1.75	   H(g(x, y)) -> H(x)
3.53/1.75	
3.53/1.75	R is empty.
3.53/1.75	The set Q consists of the following terms:
3.53/1.75	
3.53/1.75	   g(0, 1)
3.53/1.75	
3.53/1.75	We have to consider all minimal (P,Q,R)-chains.
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(9) QDPSizeChangeProof (EQUIVALENT)
3.53/1.75	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.53/1.75	
3.53/1.75	From the DPs we obtained the following set of size-change graphs:
3.53/1.75	*H(g(x, y)) -> H(x)
3.53/1.75	The graph contains the following edges 1 > 1
3.53/1.75	
3.53/1.75	
3.53/1.75	----------------------------------------
3.53/1.75	
3.53/1.75	(10)
3.53/1.75	YES
3.53/1.77	EOF