10.93/3.72	YES
10.93/3.76	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
10.93/3.76	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
10.93/3.76	
10.93/3.76	
10.93/3.76	Termination w.r.t. Q of the given QTRS could be proven:
10.93/3.76	
10.93/3.76	(0) QTRS
10.93/3.76	(1) DependencyPairsProof [EQUIVALENT, 17 ms]
10.93/3.76	(2) QDP
10.93/3.76	(3) DependencyGraphProof [EQUIVALENT, 0 ms]
10.93/3.76	(4) QDP
10.93/3.76	(5) MRRProof [EQUIVALENT, 56 ms]
10.93/3.76	(6) QDP
10.93/3.76	(7) PisEmptyProof [EQUIVALENT, 0 ms]
10.93/3.76	(8) YES
10.93/3.76	
10.93/3.76	
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(0)
10.93/3.76	Obligation:
10.93/3.76	Q restricted rewrite system:
10.93/3.76	The TRS R consists of the following rules:
10.93/3.76	
10.93/3.76	   b(a(b(a(x1)))) -> b(b(a(b(x1))))
10.93/3.76	   a(a(b(b(x1)))) -> b(b(b(a(x1))))
10.93/3.76	   b(a(b(b(x1)))) -> b(b(a(a(x1))))
10.93/3.76	
10.93/3.76	Q is empty.
10.93/3.76	
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(1) DependencyPairsProof (EQUIVALENT)
10.93/3.76	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(2)
10.93/3.76	Obligation:
10.93/3.76	Q DP problem:
10.93/3.76	The TRS P consists of the following rules:
10.93/3.76	
10.93/3.76	   B(a(b(a(x1)))) -> B(b(a(b(x1))))
10.93/3.76	   B(a(b(a(x1)))) -> B(a(b(x1)))
10.93/3.76	   B(a(b(a(x1)))) -> A(b(x1))
10.93/3.76	   B(a(b(a(x1)))) -> B(x1)
10.93/3.76	   A(a(b(b(x1)))) -> B(b(b(a(x1))))
10.93/3.76	   A(a(b(b(x1)))) -> B(b(a(x1)))
10.93/3.76	   A(a(b(b(x1)))) -> B(a(x1))
10.93/3.76	   A(a(b(b(x1)))) -> A(x1)
10.93/3.76	   B(a(b(b(x1)))) -> B(b(a(a(x1))))
10.93/3.76	   B(a(b(b(x1)))) -> B(a(a(x1)))
10.93/3.76	   B(a(b(b(x1)))) -> A(a(x1))
10.93/3.76	   B(a(b(b(x1)))) -> A(x1)
10.93/3.76	
10.93/3.76	The TRS R consists of the following rules:
10.93/3.76	
10.93/3.76	   b(a(b(a(x1)))) -> b(b(a(b(x1))))
10.93/3.76	   a(a(b(b(x1)))) -> b(b(b(a(x1))))
10.93/3.76	   b(a(b(b(x1)))) -> b(b(a(a(x1))))
10.93/3.76	
10.93/3.76	Q is empty.
10.93/3.76	We have to consider all minimal (P,Q,R)-chains.
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(3) DependencyGraphProof (EQUIVALENT)
10.93/3.76	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 5 less nodes.
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(4)
10.93/3.76	Obligation:
10.93/3.76	Q DP problem:
10.93/3.76	The TRS P consists of the following rules:
10.93/3.76	
10.93/3.76	   B(a(b(a(x1)))) -> B(x1)
10.93/3.76	   B(a(b(a(x1)))) -> B(a(b(x1)))
10.93/3.76	   B(a(b(b(x1)))) -> B(a(a(x1)))
10.93/3.76	   B(a(b(b(x1)))) -> A(a(x1))
10.93/3.76	   A(a(b(b(x1)))) -> B(a(x1))
10.93/3.76	   B(a(b(b(x1)))) -> A(x1)
10.93/3.76	   A(a(b(b(x1)))) -> A(x1)
10.93/3.76	
10.93/3.76	The TRS R consists of the following rules:
10.93/3.76	
10.93/3.76	   b(a(b(a(x1)))) -> b(b(a(b(x1))))
10.93/3.76	   a(a(b(b(x1)))) -> b(b(b(a(x1))))
10.93/3.76	   b(a(b(b(x1)))) -> b(b(a(a(x1))))
10.93/3.76	
10.93/3.76	Q is empty.
10.93/3.76	We have to consider all minimal (P,Q,R)-chains.
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(5) MRRProof (EQUIVALENT)
10.93/3.76	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.
10.93/3.76	
10.93/3.76	Strictly oriented dependency pairs:
10.93/3.76	
10.93/3.76	   B(a(b(a(x1)))) -> B(x1)
10.93/3.76	   B(a(b(a(x1)))) -> B(a(b(x1)))
10.93/3.76	   B(a(b(b(x1)))) -> B(a(a(x1)))
10.93/3.76	   B(a(b(b(x1)))) -> A(a(x1))
10.93/3.76	   A(a(b(b(x1)))) -> B(a(x1))
10.93/3.76	   B(a(b(b(x1)))) -> A(x1)
10.93/3.76	   A(a(b(b(x1)))) -> A(x1)
10.93/3.76	
10.93/3.76	
10.93/3.76	Used ordering: Polynomial interpretation [POLO]:
10.93/3.76	
10.93/3.76	   POL(A(x_1)) = 2 + 2*x_1
10.93/3.76	   POL(B(x_1)) = 1 + 2*x_1
10.93/3.76	   POL(a(x_1)) = 2 + x_1
10.93/3.76	   POL(b(x_1)) = 2 + x_1
10.93/3.76	
10.93/3.76	
10.93/3.76	----------------------------------------
10.93/3.76	
10.93/3.76	(6)
10.93/3.76	Obligation:
10.93/3.76	Q DP problem:
10.93/3.76	P is empty.
10.93/3.76	The TRS R consists of the following rules:
10.93/3.76	
10.93/3.76	   b(a(b(a(x1)))) -> b(b(a(b(x1))))
10.93/3.77	   a(a(b(b(x1)))) -> b(b(b(a(x1))))
10.93/3.77	   b(a(b(b(x1)))) -> b(b(a(a(x1))))
10.93/3.77	
10.93/3.77	Q is empty.
10.93/3.77	We have to consider all minimal (P,Q,R)-chains.
10.93/3.77	----------------------------------------
10.93/3.77	
10.93/3.77	(7) PisEmptyProof (EQUIVALENT)
10.93/3.77	The TRS P is empty. Hence, there is no (P,Q,R) chain.
10.93/3.77	----------------------------------------
10.93/3.77	
10.93/3.77	(8)
10.93/3.77	YES
11.21/3.83	EOF