13.78/4.48	YES
14.26/4.62	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
14.26/4.62	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
14.26/4.62	
14.26/4.62	
14.26/4.62	Termination w.r.t. Q of the given QTRS could be proven:
14.26/4.62	
14.26/4.62	(0) QTRS
14.26/4.62	(1) DependencyPairsProof [EQUIVALENT, 1 ms]
14.26/4.62	(2) QDP
14.26/4.62	(3) MRRProof [EQUIVALENT, 48 ms]
14.26/4.62	(4) QDP
14.26/4.62	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
14.26/4.62	(6) TRUE
14.26/4.62	
14.26/4.62	
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(0)
14.26/4.62	Obligation:
14.26/4.62	Q restricted rewrite system:
14.26/4.62	The TRS R consists of the following rules:
14.26/4.62	
14.26/4.62	   a(a(x1)) -> b(x1)
14.26/4.62	   b(a(x1)) -> a(b(x1))
14.26/4.62	   b(b(c(x1))) -> c(a(x1))
14.26/4.62	   b(b(x1)) -> a(a(a(x1)))
14.26/4.62	   c(a(x1)) -> b(a(c(x1)))
14.26/4.62	
14.26/4.62	Q is empty.
14.26/4.62	
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(1) DependencyPairsProof (EQUIVALENT)
14.26/4.62	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(2)
14.26/4.62	Obligation:
14.26/4.62	Q DP problem:
14.26/4.62	The TRS P consists of the following rules:
14.26/4.62	
14.26/4.62	   A(a(x1)) -> B(x1)
14.26/4.62	   B(a(x1)) -> A(b(x1))
14.26/4.62	   B(a(x1)) -> B(x1)
14.26/4.62	   B(b(c(x1))) -> C(a(x1))
14.26/4.62	   B(b(c(x1))) -> A(x1)
14.26/4.62	   B(b(x1)) -> A(a(a(x1)))
14.26/4.62	   B(b(x1)) -> A(a(x1))
14.26/4.62	   B(b(x1)) -> A(x1)
14.26/4.62	   C(a(x1)) -> B(a(c(x1)))
14.26/4.62	   C(a(x1)) -> A(c(x1))
14.26/4.62	   C(a(x1)) -> C(x1)
14.26/4.62	
14.26/4.62	The TRS R consists of the following rules:
14.26/4.62	
14.26/4.62	   a(a(x1)) -> b(x1)
14.26/4.62	   b(a(x1)) -> a(b(x1))
14.26/4.62	   b(b(c(x1))) -> c(a(x1))
14.26/4.62	   b(b(x1)) -> a(a(a(x1)))
14.26/4.62	   c(a(x1)) -> b(a(c(x1)))
14.26/4.62	
14.26/4.62	Q is empty.
14.26/4.62	We have to consider all minimal (P,Q,R)-chains.
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(3) MRRProof (EQUIVALENT)
14.26/4.62	By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.
14.26/4.62	
14.26/4.62	Strictly oriented dependency pairs:
14.26/4.62	
14.26/4.62	   B(a(x1)) -> A(b(x1))
14.26/4.62	   B(a(x1)) -> B(x1)
14.26/4.62	   B(b(c(x1))) -> A(x1)
14.26/4.62	   B(b(x1)) -> A(a(a(x1)))
14.26/4.62	   B(b(x1)) -> A(a(x1))
14.26/4.62	   B(b(x1)) -> A(x1)
14.26/4.62	   C(a(x1)) -> B(a(c(x1)))
14.26/4.62	   C(a(x1)) -> A(c(x1))
14.26/4.62	   C(a(x1)) -> C(x1)
14.26/4.62	
14.26/4.62	Strictly oriented rules of the TRS R:
14.26/4.62	
14.26/4.62	   a(a(x1)) -> b(x1)
14.26/4.62	   c(a(x1)) -> b(a(c(x1)))
14.26/4.62	
14.26/4.62	Used ordering: Polynomial interpretation [POLO]:
14.26/4.62	
14.26/4.62	   POL(A(x_1)) = 1 + x_1
14.26/4.62	   POL(B(x_1)) = 3 + x_1
14.26/4.62	   POL(C(x_1)) = 2 + 3*x_1
14.26/4.62	   POL(a(x_1)) = 2 + x_1
14.26/4.62	   POL(b(x_1)) = 3 + x_1
14.26/4.62	   POL(c(x_1)) = 2 + 3*x_1
14.26/4.62	
14.26/4.62	
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(4)
14.26/4.62	Obligation:
14.26/4.62	Q DP problem:
14.26/4.62	The TRS P consists of the following rules:
14.26/4.62	
14.26/4.62	   A(a(x1)) -> B(x1)
14.26/4.62	   B(b(c(x1))) -> C(a(x1))
14.26/4.62	
14.26/4.62	The TRS R consists of the following rules:
14.26/4.62	
14.26/4.62	   b(a(x1)) -> a(b(x1))
14.26/4.62	   b(b(c(x1))) -> c(a(x1))
14.26/4.62	   b(b(x1)) -> a(a(a(x1)))
14.26/4.62	
14.26/4.62	Q is empty.
14.26/4.62	We have to consider all minimal (P,Q,R)-chains.
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(5) DependencyGraphProof (EQUIVALENT)
14.26/4.62	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 2 less nodes.
14.26/4.62	----------------------------------------
14.26/4.62	
14.26/4.62	(6)
14.26/4.62	TRUE
14.63/4.73	EOF