3.67/1.81	YES
3.67/1.82	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
3.67/1.82	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.67/1.82	
3.67/1.82	
3.67/1.82	Termination w.r.t. Q of the given QTRS could be proven:
3.67/1.82	
3.67/1.82	(0) QTRS
3.67/1.82	(1) DependencyPairsProof [EQUIVALENT, 13 ms]
3.67/1.82	(2) QDP
3.67/1.82	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
3.67/1.82	(4) QDP
3.67/1.82	(5) TransformationProof [EQUIVALENT, 0 ms]
3.67/1.82	(6) QDP
3.67/1.82	(7) DependencyGraphProof [EQUIVALENT, 0 ms]
3.67/1.82	(8) QDP
3.67/1.82	(9) UsableRulesProof [EQUIVALENT, 0 ms]
3.67/1.82	(10) QDP
3.67/1.82	(11) QReductionProof [EQUIVALENT, 0 ms]
3.67/1.82	(12) QDP
3.67/1.82	(13) TransformationProof [EQUIVALENT, 0 ms]
3.67/1.82	(14) QDP
3.67/1.82	(15) TransformationProof [EQUIVALENT, 0 ms]
3.67/1.82	(16) QDP
3.67/1.82	(17) DependencyGraphProof [EQUIVALENT, 0 ms]
3.67/1.82	(18) TRUE
3.67/1.82	
3.67/1.82	
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(0)
3.67/1.82	Obligation:
3.67/1.82	Q restricted rewrite system:
3.67/1.82	The TRS R consists of the following rules:
3.67/1.82	
3.67/1.82	   f(a(x), y, s(z), u) -> f(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	   g(x, y, z, u) -> h(x, y, z, u)
3.67/1.82	   h(b, y, z, u) -> f(y, y, z, u)
3.67/1.82	   a(b) -> c
3.67/1.82	
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(1) DependencyPairsProof (EQUIVALENT)
3.67/1.82	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(2)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   F(a(x), y, s(z), u) -> F(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	   F(a(x), y, s(z), u) -> A(b)
3.67/1.82	   F(a(x), y, s(z), u) -> G(x, y, s(z), u)
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	
3.67/1.82	The TRS R consists of the following rules:
3.67/1.82	
3.67/1.82	   f(a(x), y, s(z), u) -> f(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	   g(x, y, z, u) -> h(x, y, z, u)
3.67/1.82	   h(b, y, z, u) -> f(y, y, z, u)
3.67/1.82	   a(b) -> c
3.67/1.82	
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(3) DependencyGraphProof (EQUIVALENT)
3.67/1.82	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(4)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   F(a(x), y, s(z), u) -> G(x, y, s(z), u)
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x), y, s(z), u) -> F(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	
3.67/1.82	The TRS R consists of the following rules:
3.67/1.82	
3.67/1.82	   f(a(x), y, s(z), u) -> f(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	   g(x, y, z, u) -> h(x, y, z, u)
3.67/1.82	   h(b, y, z, u) -> f(y, y, z, u)
3.67/1.82	   a(b) -> c
3.67/1.82	
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(5) TransformationProof (EQUIVALENT)
3.67/1.82	By rewriting [LPAR04] the rule F(a(x), y, s(z), u) -> F(a(b), y, z, g(x, y, s(z), u)) at position [0] we obtained the following new rules [LPAR04]:
3.67/1.82	
3.67/1.82	   (F(a(x), y, s(z), u) -> F(c, y, z, g(x, y, s(z), u)),F(a(x), y, s(z), u) -> F(c, y, z, g(x, y, s(z), u)))
3.67/1.82	
3.67/1.82	
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(6)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   F(a(x), y, s(z), u) -> G(x, y, s(z), u)
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x), y, s(z), u) -> F(c, y, z, g(x, y, s(z), u))
3.67/1.82	
3.67/1.82	The TRS R consists of the following rules:
3.67/1.82	
3.67/1.82	   f(a(x), y, s(z), u) -> f(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	   g(x, y, z, u) -> h(x, y, z, u)
3.67/1.82	   h(b, y, z, u) -> f(y, y, z, u)
3.67/1.82	   a(b) -> c
3.67/1.82	
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(7) DependencyGraphProof (EQUIVALENT)
3.67/1.82	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(8)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x), y, s(z), u) -> G(x, y, s(z), u)
3.67/1.82	
3.67/1.82	The TRS R consists of the following rules:
3.67/1.82	
3.67/1.82	   f(a(x), y, s(z), u) -> f(a(b), y, z, g(x, y, s(z), u))
3.67/1.82	   g(x, y, z, u) -> h(x, y, z, u)
3.67/1.82	   h(b, y, z, u) -> f(y, y, z, u)
3.67/1.82	   a(b) -> c
3.67/1.82	
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(9) UsableRulesProof (EQUIVALENT)
3.67/1.82	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.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(10)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x), y, s(z), u) -> G(x, y, s(z), u)
3.67/1.82	
3.67/1.82	R is empty.
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(11) QReductionProof (EQUIVALENT)
3.67/1.82	We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].
3.67/1.82	
3.67/1.82	   f(a(x0), x1, s(x2), x3)
3.67/1.82	   g(x0, x1, x2, x3)
3.67/1.82	   h(b, x0, x1, x2)
3.67/1.82	
3.67/1.82	
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(12)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x), y, s(z), u) -> G(x, y, s(z), u)
3.67/1.82	
3.67/1.82	R is empty.
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(13) TransformationProof (EQUIVALENT)
3.67/1.82	By instantiating [LPAR04] the rule F(a(x), y, s(z), u) -> G(x, y, s(z), u) we obtained the following new rules [LPAR04]:
3.67/1.82	
3.67/1.82	   (F(a(x0), a(x0), s(x2), z2) -> G(x0, a(x0), s(x2), z2),F(a(x0), a(x0), s(x2), z2) -> G(x0, a(x0), s(x2), z2))
3.67/1.82	
3.67/1.82	
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(14)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   G(x, y, z, u) -> H(x, y, z, u)
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x0), a(x0), s(x2), z2) -> G(x0, a(x0), s(x2), z2)
3.67/1.82	
3.67/1.82	R is empty.
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(15) TransformationProof (EQUIVALENT)
3.67/1.82	By instantiating [LPAR04] the rule G(x, y, z, u) -> H(x, y, z, u) we obtained the following new rules [LPAR04]:
3.67/1.82	
3.67/1.82	   (G(z0, a(z0), s(z1), z2) -> H(z0, a(z0), s(z1), z2),G(z0, a(z0), s(z1), z2) -> H(z0, a(z0), s(z1), z2))
3.67/1.82	
3.67/1.82	
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(16)
3.67/1.82	Obligation:
3.67/1.82	Q DP problem:
3.67/1.82	The TRS P consists of the following rules:
3.67/1.82	
3.67/1.82	   H(b, y, z, u) -> F(y, y, z, u)
3.67/1.82	   F(a(x0), a(x0), s(x2), z2) -> G(x0, a(x0), s(x2), z2)
3.67/1.82	   G(z0, a(z0), s(z1), z2) -> H(z0, a(z0), s(z1), z2)
3.67/1.82	
3.67/1.82	R is empty.
3.67/1.82	The set Q consists of the following terms:
3.67/1.82	
3.67/1.82	   a(b)
3.67/1.82	
3.67/1.82	We have to consider all minimal (P,Q,R)-chains.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(17) DependencyGraphProof (EQUIVALENT)
3.67/1.82	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes.
3.67/1.82	----------------------------------------
3.67/1.82	
3.67/1.82	(18)
3.67/1.82	TRUE
3.67/1.84	EOF