3.65/1.78	YES
3.65/1.79	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.65/1.79	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.65/1.79	
3.65/1.79	
3.65/1.79	Termination w.r.t. Q of the given QTRS could be proven:
3.65/1.79	
3.65/1.79	(0) QTRS
3.65/1.79	(1) QTRSRRRProof [EQUIVALENT, 69 ms]
3.65/1.79	(2) QTRS
3.65/1.79	(3) DependencyPairsProof [EQUIVALENT, 0 ms]
3.65/1.79	(4) QDP
3.65/1.79	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
3.65/1.79	(6) TRUE
3.65/1.79	
3.65/1.79	
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(0)
3.65/1.79	Obligation:
3.65/1.79	Q restricted rewrite system:
3.65/1.79	The TRS R consists of the following rules:
3.65/1.79	
3.65/1.79	   g(c, g(a(x), y)) -> g(f(a(b)), g(a(y), x))
3.65/1.79	   f(a(x)) -> c
3.65/1.79	   a(b) -> d
3.65/1.79	
3.65/1.79	The set Q consists of the following terms:
3.65/1.79	
3.65/1.79	   g(c, g(a(x0), x1))
3.65/1.79	   f(a(x0))
3.65/1.79	   a(b)
3.65/1.79	
3.65/1.79	
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(1) QTRSRRRProof (EQUIVALENT)
3.65/1.79	Used ordering:
3.65/1.79	Polynomial interpretation [POLO]:
3.65/1.79	
3.65/1.79	   POL(a(x_1)) = 1 + x_1
3.65/1.79	   POL(b) = 0
3.65/1.79	   POL(c) = 1
3.65/1.79	   POL(d) = 0
3.65/1.79	   POL(f(x_1)) = x_1
3.65/1.79	   POL(g(x_1, x_2)) = 2*x_1 + 2*x_2
3.65/1.79	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.65/1.79	
3.65/1.79	   a(b) -> d
3.65/1.79	
3.65/1.79	
3.65/1.79	
3.65/1.79	
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(2)
3.65/1.79	Obligation:
3.65/1.79	Q restricted rewrite system:
3.65/1.79	The TRS R consists of the following rules:
3.65/1.79	
3.65/1.79	   g(c, g(a(x), y)) -> g(f(a(b)), g(a(y), x))
3.65/1.79	   f(a(x)) -> c
3.65/1.79	
3.65/1.79	The set Q consists of the following terms:
3.65/1.79	
3.65/1.79	   g(c, g(a(x0), x1))
3.65/1.79	   f(a(x0))
3.65/1.79	   a(b)
3.65/1.79	
3.65/1.79	
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(3) DependencyPairsProof (EQUIVALENT)
3.65/1.79	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(4)
3.65/1.79	Obligation:
3.65/1.79	Q DP problem:
3.65/1.79	The TRS P consists of the following rules:
3.65/1.79	
3.65/1.79	   G(c, g(a(x), y)) -> G(f(a(b)), g(a(y), x))
3.65/1.79	   G(c, g(a(x), y)) -> F(a(b))
3.65/1.79	   G(c, g(a(x), y)) -> G(a(y), x)
3.65/1.79	
3.65/1.79	The TRS R consists of the following rules:
3.65/1.79	
3.65/1.79	   g(c, g(a(x), y)) -> g(f(a(b)), g(a(y), x))
3.65/1.79	   f(a(x)) -> c
3.65/1.79	
3.65/1.79	The set Q consists of the following terms:
3.65/1.79	
3.65/1.79	   g(c, g(a(x0), x1))
3.65/1.79	   f(a(x0))
3.65/1.79	   a(b)
3.65/1.79	
3.65/1.79	We have to consider all minimal (P,Q,R)-chains.
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(5) DependencyGraphProof (EQUIVALENT)
3.65/1.79	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 3 less nodes.
3.65/1.79	----------------------------------------
3.65/1.79	
3.65/1.79	(6)
3.65/1.79	TRUE
3.65/1.81	EOF