26.94/7.81	YES
27.38/7.90	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
27.38/7.90	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
27.38/7.90	
27.38/7.90	
27.38/7.90	Termination w.r.t. Q of the given QTRS could be proven:
27.38/7.90	
27.38/7.90	(0) QTRS
27.38/7.90	(1) QTRSRRRProof [EQUIVALENT, 82 ms]
27.38/7.90	(2) QTRS
27.38/7.90	(3) Overlay + Local Confluence [EQUIVALENT, 8 ms]
27.38/7.90	(4) QTRS
27.38/7.90	(5) DependencyPairsProof [EQUIVALENT, 51 ms]
27.38/7.90	(6) QDP
27.38/7.90	(7) MRRProof [EQUIVALENT, 41 ms]
27.38/7.90	(8) QDP
27.38/7.90	(9) PisEmptyProof [EQUIVALENT, 4 ms]
27.38/7.90	(10) YES
27.38/7.90	
27.38/7.90	
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(0)
27.38/7.90	Obligation:
27.38/7.90	Q restricted rewrite system:
27.38/7.90	The TRS R consists of the following rules:
27.38/7.90	
27.38/7.90	   a(b(x1)) -> C(x1)
27.38/7.90	   b(c(x1)) -> A(x1)
27.38/7.90	   c(a(x1)) -> B(x1)
27.38/7.90	   A(C(x1)) -> b(x1)
27.38/7.90	   C(B(x1)) -> a(x1)
27.38/7.90	   B(A(x1)) -> c(x1)
27.38/7.90	   a(a(a(a(a(x1))))) -> A(A(A(x1)))
27.38/7.90	   A(A(A(A(x1)))) -> a(a(a(a(x1))))
27.38/7.90	   b(b(b(b(b(x1))))) -> B(B(B(x1)))
27.38/7.90	   B(B(B(B(x1)))) -> b(b(b(b(x1))))
27.38/7.90	   c(c(c(c(c(x1))))) -> C(C(C(x1)))
27.38/7.90	   C(C(C(C(x1)))) -> c(c(c(c(x1))))
27.38/7.90	   B(a(a(a(a(x1))))) -> c(A(A(A(x1))))
27.38/7.90	   A(A(A(b(x1)))) -> a(a(a(a(C(x1)))))
27.38/7.90	   C(b(b(b(b(x1))))) -> a(B(B(B(x1))))
27.38/7.90	   B(B(B(c(x1)))) -> b(b(b(b(A(x1)))))
27.38/7.90	   A(c(c(c(c(x1))))) -> b(C(C(C(x1))))
27.38/7.90	   C(C(C(a(x1)))) -> c(c(c(c(B(x1)))))
27.38/7.90	   a(A(x1)) -> x1
27.38/7.90	   A(a(x1)) -> x1
27.38/7.90	   b(B(x1)) -> x1
27.38/7.90	   B(b(x1)) -> x1
27.38/7.90	   c(C(x1)) -> x1
27.38/7.90	   C(c(x1)) -> x1
27.38/7.90	
27.38/7.90	Q is empty.
27.38/7.90	
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(1) QTRSRRRProof (EQUIVALENT)
27.38/7.90	Used ordering:
27.38/7.90	Polynomial interpretation [POLO]:
27.38/7.90	
27.38/7.90	   POL(A(x_1)) = 3 + x_1
27.38/7.90	   POL(B(x_1)) = 3 + x_1
27.38/7.90	   POL(C(x_1)) = 3 + x_1
27.38/7.90	   POL(a(x_1)) = 2 + x_1
27.38/7.90	   POL(b(x_1)) = 2 + x_1
27.38/7.90	   POL(c(x_1)) = 2 + x_1
27.38/7.90	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
27.38/7.90	
27.38/7.90	   a(b(x1)) -> C(x1)
27.38/7.90	   b(c(x1)) -> A(x1)
27.38/7.90	   c(a(x1)) -> B(x1)
27.38/7.90	   A(C(x1)) -> b(x1)
27.38/7.90	   C(B(x1)) -> a(x1)
27.38/7.90	   B(A(x1)) -> c(x1)
27.38/7.90	   a(a(a(a(a(x1))))) -> A(A(A(x1)))
27.38/7.90	   A(A(A(A(x1)))) -> a(a(a(a(x1))))
27.38/7.90	   b(b(b(b(b(x1))))) -> B(B(B(x1)))
27.38/7.90	   B(B(B(B(x1)))) -> b(b(b(b(x1))))
27.38/7.90	   c(c(c(c(c(x1))))) -> C(C(C(x1)))
27.38/7.90	   C(C(C(C(x1)))) -> c(c(c(c(x1))))
27.38/7.90	   a(A(x1)) -> x1
27.38/7.90	   A(a(x1)) -> x1
27.38/7.90	   b(B(x1)) -> x1
27.38/7.90	   B(b(x1)) -> x1
27.38/7.90	   c(C(x1)) -> x1
27.38/7.90	   C(c(x1)) -> x1
27.38/7.90	
27.38/7.90	
27.38/7.90	
27.38/7.90	
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(2)
27.38/7.90	Obligation:
27.38/7.90	Q restricted rewrite system:
27.38/7.90	The TRS R consists of the following rules:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x1))))) -> c(A(A(A(x1))))
27.38/7.90	   A(A(A(b(x1)))) -> a(a(a(a(C(x1)))))
27.38/7.90	   C(b(b(b(b(x1))))) -> a(B(B(B(x1))))
27.38/7.90	   B(B(B(c(x1)))) -> b(b(b(b(A(x1)))))
27.38/7.90	   A(c(c(c(c(x1))))) -> b(C(C(C(x1))))
27.38/7.90	   C(C(C(a(x1)))) -> c(c(c(c(B(x1)))))
27.38/7.90	
27.38/7.90	Q is empty.
27.38/7.90	
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(3) Overlay + Local Confluence (EQUIVALENT)
27.38/7.90	The TRS is overlay and locally confluent. By [NOC] we can switch to innermost.
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(4)
27.38/7.90	Obligation:
27.38/7.90	Q restricted rewrite system:
27.38/7.90	The TRS R consists of the following rules:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x1))))) -> c(A(A(A(x1))))
27.38/7.90	   A(A(A(b(x1)))) -> a(a(a(a(C(x1)))))
27.38/7.90	   C(b(b(b(b(x1))))) -> a(B(B(B(x1))))
27.38/7.90	   B(B(B(c(x1)))) -> b(b(b(b(A(x1)))))
27.38/7.90	   A(c(c(c(c(x1))))) -> b(C(C(C(x1))))
27.38/7.90	   C(C(C(a(x1)))) -> c(c(c(c(B(x1)))))
27.38/7.90	
27.38/7.90	The set Q consists of the following terms:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x0)))))
27.38/7.90	   A(A(A(b(x0))))
27.38/7.90	   C(b(b(b(b(x0)))))
27.38/7.90	   B(B(B(c(x0))))
27.38/7.90	   A(c(c(c(c(x0)))))
27.38/7.90	   C(C(C(a(x0))))
27.38/7.90	
27.38/7.90	
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(5) DependencyPairsProof (EQUIVALENT)
27.38/7.90	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(6)
27.38/7.90	Obligation:
27.38/7.90	Q DP problem:
27.38/7.90	The TRS P consists of the following rules:
27.38/7.90	
27.38/7.90	   B^1(a(a(a(a(x1))))) -> A^1(A(A(x1)))
27.38/7.90	   B^1(a(a(a(a(x1))))) -> A^1(A(x1))
27.38/7.90	   B^1(a(a(a(a(x1))))) -> A^1(x1)
27.38/7.90	   A^1(A(A(b(x1)))) -> C^1(x1)
27.38/7.90	   C^1(b(b(b(b(x1))))) -> B^1(B(B(x1)))
27.38/7.90	   C^1(b(b(b(b(x1))))) -> B^1(B(x1))
27.38/7.90	   C^1(b(b(b(b(x1))))) -> B^1(x1)
27.38/7.90	   B^1(B(B(c(x1)))) -> A^1(x1)
27.38/7.90	   A^1(c(c(c(c(x1))))) -> C^1(C(C(x1)))
27.38/7.90	   A^1(c(c(c(c(x1))))) -> C^1(C(x1))
27.38/7.90	   A^1(c(c(c(c(x1))))) -> C^1(x1)
27.38/7.90	   C^1(C(C(a(x1)))) -> B^1(x1)
27.38/7.90	
27.38/7.90	The TRS R consists of the following rules:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x1))))) -> c(A(A(A(x1))))
27.38/7.90	   A(A(A(b(x1)))) -> a(a(a(a(C(x1)))))
27.38/7.90	   C(b(b(b(b(x1))))) -> a(B(B(B(x1))))
27.38/7.90	   B(B(B(c(x1)))) -> b(b(b(b(A(x1)))))
27.38/7.90	   A(c(c(c(c(x1))))) -> b(C(C(C(x1))))
27.38/7.90	   C(C(C(a(x1)))) -> c(c(c(c(B(x1)))))
27.38/7.90	
27.38/7.90	The set Q consists of the following terms:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x0)))))
27.38/7.90	   A(A(A(b(x0))))
27.38/7.90	   C(b(b(b(b(x0)))))
27.38/7.90	   B(B(B(c(x0))))
27.38/7.90	   A(c(c(c(c(x0)))))
27.38/7.90	   C(C(C(a(x0))))
27.38/7.90	
27.38/7.90	We have to consider all minimal (P,Q,R)-chains.
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(7) MRRProof (EQUIVALENT)
27.38/7.90	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.
27.38/7.90	
27.38/7.90	Strictly oriented dependency pairs:
27.38/7.90	
27.38/7.90	   B^1(a(a(a(a(x1))))) -> A^1(A(A(x1)))
27.38/7.90	   B^1(a(a(a(a(x1))))) -> A^1(A(x1))
27.38/7.90	   B^1(a(a(a(a(x1))))) -> A^1(x1)
27.38/7.90	   A^1(A(A(b(x1)))) -> C^1(x1)
27.38/7.90	   C^1(b(b(b(b(x1))))) -> B^1(B(B(x1)))
27.38/7.90	   C^1(b(b(b(b(x1))))) -> B^1(B(x1))
27.38/7.90	   C^1(b(b(b(b(x1))))) -> B^1(x1)
27.38/7.90	   B^1(B(B(c(x1)))) -> A^1(x1)
27.38/7.90	   A^1(c(c(c(c(x1))))) -> C^1(C(C(x1)))
27.38/7.90	   A^1(c(c(c(c(x1))))) -> C^1(C(x1))
27.38/7.90	   A^1(c(c(c(c(x1))))) -> C^1(x1)
27.38/7.90	   C^1(C(C(a(x1)))) -> B^1(x1)
27.38/7.90	
27.38/7.90	
27.38/7.90	Used ordering: Polynomial interpretation [POLO]:
27.38/7.90	
27.38/7.90	   POL(A(x_1)) = 3 + x_1
27.38/7.90	   POL(A^1(x_1)) = 2 + x_1
27.38/7.90	   POL(B(x_1)) = 3 + x_1
27.38/7.90	   POL(B^1(x_1)) = 1 + x_1
27.38/7.90	   POL(C(x_1)) = 3 + x_1
27.38/7.90	   POL(C^1(x_1)) = x_1
27.38/7.90	   POL(a(x_1)) = 2 + x_1
27.38/7.90	   POL(b(x_1)) = 2 + x_1
27.38/7.90	   POL(c(x_1)) = 2 + x_1
27.38/7.90	
27.38/7.90	
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(8)
27.38/7.90	Obligation:
27.38/7.90	Q DP problem:
27.38/7.90	P is empty.
27.38/7.90	The TRS R consists of the following rules:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x1))))) -> c(A(A(A(x1))))
27.38/7.90	   A(A(A(b(x1)))) -> a(a(a(a(C(x1)))))
27.38/7.90	   C(b(b(b(b(x1))))) -> a(B(B(B(x1))))
27.38/7.90	   B(B(B(c(x1)))) -> b(b(b(b(A(x1)))))
27.38/7.90	   A(c(c(c(c(x1))))) -> b(C(C(C(x1))))
27.38/7.90	   C(C(C(a(x1)))) -> c(c(c(c(B(x1)))))
27.38/7.90	
27.38/7.90	The set Q consists of the following terms:
27.38/7.90	
27.38/7.90	   B(a(a(a(a(x0)))))
27.38/7.90	   A(A(A(b(x0))))
27.38/7.90	   C(b(b(b(b(x0)))))
27.38/7.90	   B(B(B(c(x0))))
27.38/7.90	   A(c(c(c(c(x0)))))
27.38/7.90	   C(C(C(a(x0))))
27.38/7.90	
27.38/7.90	We have to consider all minimal (P,Q,R)-chains.
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(9) PisEmptyProof (EQUIVALENT)
27.38/7.90	The TRS P is empty. Hence, there is no (P,Q,R) chain.
27.38/7.90	----------------------------------------
27.38/7.90	
27.38/7.90	(10)
27.38/7.90	YES
27.64/7.98	EOF