3.64/1.75	YES
3.64/1.75	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.64/1.75	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.64/1.75	
3.64/1.75	
3.64/1.75	Termination w.r.t. Q of the given QTRS could be proven:
3.64/1.75	
3.64/1.75	(0) QTRS
3.64/1.75	(1) QTRSRRRProof [EQUIVALENT, 59 ms]
3.64/1.75	(2) QTRS
3.64/1.75	(3) DependencyPairsProof [EQUIVALENT, 4 ms]
3.64/1.75	(4) QDP
3.64/1.75	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.64/1.75	(6) QDP
3.64/1.75	(7) UsableRulesProof [EQUIVALENT, 0 ms]
3.64/1.75	(8) QDP
3.64/1.75	(9) QReductionProof [EQUIVALENT, 0 ms]
3.64/1.75	(10) QDP
3.64/1.75	(11) QDPSizeChangeProof [EQUIVALENT, 0 ms]
3.64/1.75	(12) YES
3.64/1.75	
3.64/1.75	
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(0)
3.64/1.75	Obligation:
3.64/1.75	Q restricted rewrite system:
3.64/1.75	The TRS R consists of the following rules:
3.64/1.75	
3.64/1.75	   h(X, Z) -> f(X, s(X), Z)
3.64/1.75	   f(X, Y, g(X, Y)) -> h(0, g(X, Y))
3.64/1.75	   g(0, Y) -> 0
3.64/1.75	   g(X, s(Y)) -> g(X, Y)
3.64/1.75	
3.64/1.75	The set Q consists of the following terms:
3.64/1.75	
3.64/1.75	   h(x0, x1)
3.64/1.75	   f(x0, x1, g(x0, x1))
3.64/1.75	   g(0, x0)
3.64/1.75	   g(x0, s(x1))
3.64/1.75	
3.64/1.75	
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(1) QTRSRRRProof (EQUIVALENT)
3.64/1.75	Used ordering:
3.64/1.75	Polynomial interpretation [POLO]:
3.64/1.75	
3.64/1.75	   POL(0) = 0
3.64/1.75	   POL(f(x_1, x_2, x_3)) = x_1 + x_2 + x_3
3.64/1.75	   POL(g(x_1, x_2)) = 2 + 2*x_1 + x_2
3.64/1.75	   POL(h(x_1, x_2)) = 2*x_1 + x_2
3.64/1.75	   POL(s(x_1)) = x_1
3.64/1.75	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.64/1.75	
3.64/1.75	   g(0, Y) -> 0
3.64/1.75	
3.64/1.75	
3.64/1.75	
3.64/1.75	
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(2)
3.64/1.75	Obligation:
3.64/1.75	Q restricted rewrite system:
3.64/1.75	The TRS R consists of the following rules:
3.64/1.75	
3.64/1.75	   h(X, Z) -> f(X, s(X), Z)
3.64/1.75	   f(X, Y, g(X, Y)) -> h(0, g(X, Y))
3.64/1.75	   g(X, s(Y)) -> g(X, Y)
3.64/1.75	
3.64/1.75	The set Q consists of the following terms:
3.64/1.75	
3.64/1.75	   h(x0, x1)
3.64/1.75	   f(x0, x1, g(x0, x1))
3.64/1.75	   g(0, x0)
3.64/1.75	   g(x0, s(x1))
3.64/1.75	
3.64/1.75	
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(3) DependencyPairsProof (EQUIVALENT)
3.64/1.75	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(4)
3.64/1.75	Obligation:
3.64/1.75	Q DP problem:
3.64/1.75	The TRS P consists of the following rules:
3.64/1.75	
3.64/1.75	   H(X, Z) -> F(X, s(X), Z)
3.64/1.75	   F(X, Y, g(X, Y)) -> H(0, g(X, Y))
3.64/1.75	   G(X, s(Y)) -> G(X, Y)
3.64/1.75	
3.64/1.75	The TRS R consists of the following rules:
3.64/1.75	
3.64/1.75	   h(X, Z) -> f(X, s(X), Z)
3.64/1.75	   f(X, Y, g(X, Y)) -> h(0, g(X, Y))
3.64/1.75	   g(X, s(Y)) -> g(X, Y)
3.64/1.75	
3.64/1.75	The set Q consists of the following terms:
3.64/1.75	
3.64/1.75	   h(x0, x1)
3.64/1.75	   f(x0, x1, g(x0, x1))
3.64/1.75	   g(0, x0)
3.64/1.75	   g(x0, s(x1))
3.64/1.75	
3.64/1.75	We have to consider all minimal (P,Q,R)-chains.
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(5) DependencyGraphProof (EQUIVALENT)
3.64/1.75	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 2 less nodes.
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(6)
3.64/1.75	Obligation:
3.64/1.75	Q DP problem:
3.64/1.75	The TRS P consists of the following rules:
3.64/1.75	
3.64/1.75	   G(X, s(Y)) -> G(X, Y)
3.64/1.75	
3.64/1.75	The TRS R consists of the following rules:
3.64/1.75	
3.64/1.75	   h(X, Z) -> f(X, s(X), Z)
3.64/1.75	   f(X, Y, g(X, Y)) -> h(0, g(X, Y))
3.64/1.75	   g(X, s(Y)) -> g(X, Y)
3.64/1.75	
3.64/1.75	The set Q consists of the following terms:
3.64/1.75	
3.64/1.75	   h(x0, x1)
3.64/1.75	   f(x0, x1, g(x0, x1))
3.64/1.75	   g(0, x0)
3.64/1.75	   g(x0, s(x1))
3.64/1.75	
3.64/1.75	We have to consider all minimal (P,Q,R)-chains.
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(7) UsableRulesProof (EQUIVALENT)
3.64/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.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(8)
3.64/1.75	Obligation:
3.64/1.75	Q DP problem:
3.64/1.75	The TRS P consists of the following rules:
3.64/1.75	
3.64/1.75	   G(X, s(Y)) -> G(X, Y)
3.64/1.75	
3.64/1.75	R is empty.
3.64/1.75	The set Q consists of the following terms:
3.64/1.75	
3.64/1.75	   h(x0, x1)
3.64/1.75	   f(x0, x1, g(x0, x1))
3.64/1.75	   g(0, x0)
3.64/1.75	   g(x0, s(x1))
3.64/1.75	
3.64/1.75	We have to consider all minimal (P,Q,R)-chains.
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(9) QReductionProof (EQUIVALENT)
3.64/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.64/1.75	
3.64/1.75	   h(x0, x1)
3.64/1.75	   f(x0, x1, g(x0, x1))
3.64/1.75	   g(0, x0)
3.64/1.75	   g(x0, s(x1))
3.64/1.75	
3.64/1.75	
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(10)
3.64/1.75	Obligation:
3.64/1.75	Q DP problem:
3.64/1.75	The TRS P consists of the following rules:
3.64/1.75	
3.64/1.75	   G(X, s(Y)) -> G(X, Y)
3.64/1.75	
3.64/1.75	R is empty.
3.64/1.75	Q is empty.
3.64/1.75	We have to consider all minimal (P,Q,R)-chains.
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(11) QDPSizeChangeProof (EQUIVALENT)
3.64/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.64/1.75	
3.64/1.75	From the DPs we obtained the following set of size-change graphs:
3.64/1.75	*G(X, s(Y)) -> G(X, Y)
3.64/1.75	The graph contains the following edges 1 >= 1, 2 > 2
3.64/1.75	
3.64/1.75	
3.64/1.75	----------------------------------------
3.64/1.75	
3.64/1.75	(12)
3.64/1.75	YES
3.64/1.77	EOF