28.63/8.27	YES
32.61/9.20	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
32.61/9.20	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
32.61/9.20	
32.61/9.20	
32.61/9.20	Termination w.r.t. Q of the given QTRS could be proven:
32.61/9.20	
32.61/9.20	(0) QTRS
32.61/9.20	(1) DependencyPairsProof [EQUIVALENT, 16 ms]
32.61/9.20	(2) QDP
32.61/9.20	(3) MRRProof [EQUIVALENT, 69 ms]
32.61/9.20	(4) QDP
32.61/9.20	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
32.61/9.20	(6) QDP
32.61/9.20	(7) QDPOrderProof [EQUIVALENT, 0 ms]
32.61/9.20	(8) QDP
32.61/9.20	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
32.61/9.20	(10) QDP
32.61/9.20	(11) QDPOrderProof [EQUIVALENT, 13 ms]
32.61/9.20	(12) QDP
32.61/9.20	(13) PisEmptyProof [EQUIVALENT, 0 ms]
32.61/9.20	(14) YES
32.61/9.20	
32.61/9.20	
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(0)
32.61/9.20	Obligation:
32.61/9.20	Q restricted rewrite system:
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(1) DependencyPairsProof (EQUIVALENT)
32.61/9.20	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(2)
32.61/9.20	Obligation:
32.61/9.20	Q DP problem:
32.61/9.20	The TRS P consists of the following rules:
32.61/9.20	
32.61/9.20	   B(a(a(x1))) -> A(b(c(x1)))
32.61/9.20	   B(a(a(x1))) -> B(c(x1))
32.61/9.20	   B(a(a(x1))) -> C(x1)
32.61/9.20	   C(a(x1)) -> A(c(x1))
32.61/9.20	   C(a(x1)) -> C(x1)
32.61/9.20	   B(c(a(x1))) -> A(b(c(x1)))
32.61/9.20	   B(c(a(x1))) -> B(c(x1))
32.61/9.20	   B(c(a(x1))) -> C(x1)
32.61/9.20	   C(b(x1)) -> D(x1)
32.61/9.20	   D(x1) -> B(a(x1))
32.61/9.20	   D(x1) -> A(x1)
32.61/9.20	   A(d(x1)) -> D(a(x1))
32.61/9.20	   A(d(x1)) -> A(x1)
32.61/9.20	   A(a(x1)) -> A(b(a(x1)))
32.61/9.20	   A(a(x1)) -> B(a(x1))
32.61/9.20	
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	We have to consider all minimal (P,Q,R)-chains.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(3) MRRProof (EQUIVALENT)
32.61/9.20	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.
32.61/9.20	
32.61/9.20	Strictly oriented dependency pairs:
32.61/9.20	
32.61/9.20	   B(a(a(x1))) -> B(c(x1))
32.61/9.20	   B(a(a(x1))) -> C(x1)
32.61/9.20	   C(a(x1)) -> C(x1)
32.61/9.20	   B(c(a(x1))) -> B(c(x1))
32.61/9.20	   B(c(a(x1))) -> C(x1)
32.61/9.20	   A(d(x1)) -> A(x1)
32.61/9.20	   A(a(x1)) -> B(a(x1))
32.61/9.20	
32.61/9.20	
32.61/9.20	Used ordering: Polynomial interpretation [POLO]:
32.61/9.20	
32.61/9.20	   POL(A(x_1)) = 3 + x_1
32.61/9.20	   POL(B(x_1)) = 2 + x_1
32.61/9.20	   POL(C(x_1)) = 3 + x_1
32.61/9.20	   POL(D(x_1)) = 3 + x_1
32.61/9.20	   POL(a(x_1)) = 1 + x_1
32.61/9.20	   POL(b(x_1)) = x_1
32.61/9.20	   POL(c(x_1)) = 1 + x_1
32.61/9.20	   POL(d(x_1)) = 1 + x_1
32.61/9.20	
32.61/9.20	
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(4)
32.61/9.20	Obligation:
32.61/9.20	Q DP problem:
32.61/9.20	The TRS P consists of the following rules:
32.61/9.20	
32.61/9.20	   B(a(a(x1))) -> A(b(c(x1)))
32.61/9.20	   C(a(x1)) -> A(c(x1))
32.61/9.20	   B(c(a(x1))) -> A(b(c(x1)))
32.61/9.20	   C(b(x1)) -> D(x1)
32.61/9.20	   D(x1) -> B(a(x1))
32.61/9.20	   D(x1) -> A(x1)
32.61/9.20	   A(d(x1)) -> D(a(x1))
32.61/9.20	   A(a(x1)) -> A(b(a(x1)))
32.61/9.20	
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	We have to consider all minimal (P,Q,R)-chains.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(5) DependencyGraphProof (EQUIVALENT)
32.61/9.20	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(6)
32.61/9.20	Obligation:
32.61/9.20	Q DP problem:
32.61/9.20	The TRS P consists of the following rules:
32.61/9.20	
32.61/9.20	   A(d(x1)) -> D(a(x1))
32.61/9.20	   D(x1) -> B(a(x1))
32.61/9.20	   B(a(a(x1))) -> A(b(c(x1)))
32.61/9.20	   A(a(x1)) -> A(b(a(x1)))
32.61/9.20	   D(x1) -> A(x1)
32.61/9.20	
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	We have to consider all minimal (P,Q,R)-chains.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(7) QDPOrderProof (EQUIVALENT)
32.61/9.20	We use the reduction pair processor [LPAR04,JAR06].
32.61/9.20	
32.61/9.20	
32.61/9.20	The following pairs can be oriented strictly and are deleted.
32.61/9.20	
32.61/9.20	   A(d(x1)) -> D(a(x1))
32.61/9.20	   D(x1) -> B(a(x1))
32.61/9.20	   D(x1) -> A(x1)
32.61/9.20	The remaining pairs can at least be oriented weakly.
32.61/9.20	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
32.61/9.20	
32.61/9.20	POL( A_1(x_1) ) = 2x_1
32.61/9.20	POL( B_1(x_1) ) = 0
32.61/9.20	POL( D_1(x_1) ) = 2x_1 + 1
32.61/9.20	POL( a_1(x_1) ) = 2x_1
32.61/9.20	POL( d_1(x_1) ) = 2x_1 + 1
32.61/9.20	POL( b_1(x_1) ) = max{0, -2}
32.61/9.20	POL( c_1(x_1) ) = 0
32.61/9.20	
32.61/9.20	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
32.61/9.20	
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	
32.61/9.20	
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(8)
32.61/9.20	Obligation:
32.61/9.20	Q DP problem:
32.61/9.20	The TRS P consists of the following rules:
32.61/9.20	
32.61/9.20	   B(a(a(x1))) -> A(b(c(x1)))
32.61/9.20	   A(a(x1)) -> A(b(a(x1)))
32.61/9.20	
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	We have to consider all minimal (P,Q,R)-chains.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(9) DependencyGraphProof (EQUIVALENT)
32.61/9.20	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(10)
32.61/9.20	Obligation:
32.61/9.20	Q DP problem:
32.61/9.20	The TRS P consists of the following rules:
32.61/9.20	
32.61/9.20	   A(a(x1)) -> A(b(a(x1)))
32.61/9.20	
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	We have to consider all minimal (P,Q,R)-chains.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(11) QDPOrderProof (EQUIVALENT)
32.61/9.20	We use the reduction pair processor [LPAR04,JAR06].
32.61/9.20	
32.61/9.20	
32.61/9.20	The following pairs can be oriented strictly and are deleted.
32.61/9.20	
32.61/9.20	   A(a(x1)) -> A(b(a(x1)))
32.61/9.20	The remaining pairs can at least be oriented weakly.
32.61/9.20	Used ordering:  Polynomial Order [NEGPOLO,POLO] with Interpretation:
32.61/9.20	
32.61/9.20	POL( A_1(x_1) ) = max{0, 2x_1 - 2}
32.61/9.20	POL( a_1(x_1) ) = x_1 + 2
32.61/9.20	POL( d_1(x_1) ) = x_1
32.61/9.20	POL( b_1(x_1) ) = max{0, x_1 - 2}
32.61/9.20	POL( c_1(x_1) ) = x_1 + 2
32.61/9.20	
32.61/9.20	The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:
32.61/9.20	
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	
32.61/9.20	
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(12)
32.61/9.20	Obligation:
32.61/9.20	Q DP problem:
32.61/9.20	P is empty.
32.61/9.20	The TRS R consists of the following rules:
32.61/9.20	
32.61/9.20	   b(a(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(a(x1)) -> a(c(x1))
32.61/9.20	   b(c(a(x1))) -> a(b(c(x1)))
32.61/9.20	   c(b(x1)) -> d(x1)
32.61/9.20	   d(x1) -> b(a(x1))
32.61/9.20	   a(d(x1)) -> d(a(x1))
32.61/9.20	   a(a(x1)) -> a(b(a(x1)))
32.61/9.20	
32.61/9.20	Q is empty.
32.61/9.20	We have to consider all minimal (P,Q,R)-chains.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(13) PisEmptyProof (EQUIVALENT)
32.61/9.20	The TRS P is empty. Hence, there is no (P,Q,R) chain.
32.61/9.20	----------------------------------------
32.61/9.20	
32.61/9.20	(14)
32.61/9.20	YES
32.71/9.26	EOF