176.29/45.68	YES
176.69/45.77	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
176.69/45.77	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
176.69/45.77	
176.69/45.77	
176.69/45.77	Termination w.r.t. Q of the given QTRS could be proven:
176.69/45.77	
176.69/45.77	(0) QTRS
176.69/45.77	(1) QTRS Reverse [EQUIVALENT, 0 ms]
176.69/45.77	(2) QTRS
176.69/45.77	(3) DependencyPairsProof [EQUIVALENT, 1 ms]
176.69/45.77	(4) QDP
176.69/45.77	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
176.69/45.77	(6) QDP
176.69/45.77	(7) SemLabProof [SOUND, 63 ms]
176.69/45.77	(8) QDP
176.69/45.77	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
176.69/45.77	(10) AND
176.69/45.77	    (11) QDP
176.69/45.77	        (12) UsableRulesReductionPairsProof [EQUIVALENT, 6 ms]
176.69/45.77	        (13) QDP
176.69/45.77	        (14) PisEmptyProof [EQUIVALENT, 0 ms]
176.69/45.77	        (15) YES
176.69/45.77	    (16) QDP
176.69/45.77	        (17) UsableRulesReductionPairsProof [EQUIVALENT, 9 ms]
176.69/45.77	        (18) QDP
176.69/45.77	        (19) PisEmptyProof [EQUIVALENT, 0 ms]
176.69/45.77	        (20) YES
176.69/45.77	
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(0)
176.69/45.77	Obligation:
176.69/45.77	Q restricted rewrite system:
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a(x1) -> x1
176.69/45.77	   a(b(x1)) -> b(b(c(a(c(x1)))))
176.69/45.77	   b(x1) -> x1
176.69/45.77	   c(c(x1)) -> a(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(1) QTRS Reverse (EQUIVALENT)
176.69/45.77	We applied the QTRS Reverse Processor [REVERSE].
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(2)
176.69/45.77	Obligation:
176.69/45.77	Q restricted rewrite system:
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a(x1) -> x1
176.69/45.77	   b(a(x1)) -> c(a(c(b(b(x1)))))
176.69/45.77	   b(x1) -> x1
176.69/45.77	   c(c(x1)) -> a(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(3) DependencyPairsProof (EQUIVALENT)
176.69/45.77	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(4)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	The TRS P consists of the following rules:
176.69/45.77	
176.69/45.77	   B(a(x1)) -> C(a(c(b(b(x1)))))
176.69/45.77	   B(a(x1)) -> A(c(b(b(x1))))
176.69/45.77	   B(a(x1)) -> C(b(b(x1)))
176.69/45.77	   B(a(x1)) -> B(b(x1))
176.69/45.77	   B(a(x1)) -> B(x1)
176.69/45.77	   C(c(x1)) -> A(x1)
176.69/45.77	
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a(x1) -> x1
176.69/45.77	   b(a(x1)) -> c(a(c(b(b(x1)))))
176.69/45.77	   b(x1) -> x1
176.69/45.77	   c(c(x1)) -> a(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(5) DependencyGraphProof (EQUIVALENT)
176.69/45.77	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 4 less nodes.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(6)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	The TRS P consists of the following rules:
176.69/45.77	
176.69/45.77	   B(a(x1)) -> B(x1)
176.69/45.77	   B(a(x1)) -> B(b(x1))
176.69/45.77	
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a(x1) -> x1
176.69/45.77	   b(a(x1)) -> c(a(c(b(b(x1)))))
176.69/45.77	   b(x1) -> x1
176.69/45.77	   c(c(x1)) -> a(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(7) SemLabProof (SOUND)
176.69/45.77	We found the following model for the rules of the TRSs R and P.
176.69/45.77	Interpretation over the domain with elements from 0 to 1.
176.69/45.77	a: x<sub>0</sub>
176.69/45.77	b: x<sub>0</sub>
176.69/45.77	c: 1 + x<sub>0</sub>
176.69/45.77	B: 0
176.69/45.77	By semantic labelling [SEMLAB] we obtain the following labelled QDP problem.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(8)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	The TRS P consists of the following rules:
176.69/45.77	
176.69/45.77	   B.0(a.0(x1)) -> B.0(x1)
176.69/45.77	   B.0(a.0(x1)) -> B.0(b.0(x1))
176.69/45.77	   B.1(a.1(x1)) -> B.1(b.1(x1))
176.69/45.77	   B.1(a.1(x1)) -> B.1(x1)
176.69/45.77	
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a.0(x1) -> x1
176.69/45.77	   a.1(x1) -> x1
176.69/45.77	   b.0(a.0(x1)) -> c.1(a.1(c.0(b.0(b.0(x1)))))
176.69/45.77	   b.1(a.1(x1)) -> c.0(a.0(c.1(b.1(b.1(x1)))))
176.69/45.77	   b.0(x1) -> x1
176.69/45.77	   b.1(x1) -> x1
176.69/45.77	   c.1(c.0(x1)) -> a.0(x1)
176.69/45.77	   c.0(c.1(x1)) -> a.1(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(9) DependencyGraphProof (EQUIVALENT)
176.69/45.77	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(10)
176.69/45.77	Complex Obligation (AND)
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(11)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	The TRS P consists of the following rules:
176.69/45.77	
176.69/45.77	   B.1(a.1(x1)) -> B.1(x1)
176.69/45.77	   B.1(a.1(x1)) -> B.1(b.1(x1))
176.69/45.77	
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a.0(x1) -> x1
176.69/45.77	   a.1(x1) -> x1
176.69/45.77	   b.0(a.0(x1)) -> c.1(a.1(c.0(b.0(b.0(x1)))))
176.69/45.77	   b.1(a.1(x1)) -> c.0(a.0(c.1(b.1(b.1(x1)))))
176.69/45.77	   b.0(x1) -> x1
176.69/45.77	   b.1(x1) -> x1
176.69/45.77	   c.1(c.0(x1)) -> a.0(x1)
176.69/45.77	   c.0(c.1(x1)) -> a.1(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(12) UsableRulesReductionPairsProof (EQUIVALENT)
176.69/45.77	By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
176.69/45.77	
176.69/45.77	The following dependency pairs can be deleted:
176.69/45.77	
176.69/45.77	   B.1(a.1(x1)) -> B.1(x1)
176.69/45.77	   B.1(a.1(x1)) -> B.1(b.1(x1))
176.69/45.77	The following rules are removed from R:
176.69/45.77	
176.69/45.77	   a.1(x1) -> x1
176.69/45.77	   b.0(a.0(x1)) -> c.1(a.1(c.0(b.0(b.0(x1)))))
176.69/45.77	   b.0(x1) -> x1
176.69/45.77	   c.1(c.0(x1)) -> a.0(x1)
176.69/45.77	Used ordering: POLO with Polynomial interpretation [POLO]:
176.69/45.77	
176.69/45.77	   POL(B.1(x_1)) = x_1
176.69/45.77	   POL(a.0(x_1)) = x_1
176.69/45.77	   POL(a.1(x_1)) = 1 + x_1
176.69/45.77	   POL(b.1(x_1)) = x_1
176.69/45.77	   POL(c.0(x_1)) = 1 + x_1
176.69/45.77	   POL(c.1(x_1)) = x_1
176.69/45.77	
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(13)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	P is empty.
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   b.1(a.1(x1)) -> c.0(a.0(c.1(b.1(b.1(x1)))))
176.69/45.77	   b.1(x1) -> x1
176.69/45.77	   a.0(x1) -> x1
176.69/45.77	   c.0(c.1(x1)) -> a.1(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(14) PisEmptyProof (EQUIVALENT)
176.69/45.77	The TRS P is empty. Hence, there is no (P,Q,R) chain.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(15)
176.69/45.77	YES
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(16)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	The TRS P consists of the following rules:
176.69/45.77	
176.69/45.77	   B.0(a.0(x1)) -> B.0(b.0(x1))
176.69/45.77	   B.0(a.0(x1)) -> B.0(x1)
176.69/45.77	
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   a.0(x1) -> x1
176.69/45.77	   a.1(x1) -> x1
176.69/45.77	   b.0(a.0(x1)) -> c.1(a.1(c.0(b.0(b.0(x1)))))
176.69/45.77	   b.1(a.1(x1)) -> c.0(a.0(c.1(b.1(b.1(x1)))))
176.69/45.77	   b.0(x1) -> x1
176.69/45.77	   b.1(x1) -> x1
176.69/45.77	   c.1(c.0(x1)) -> a.0(x1)
176.69/45.77	   c.0(c.1(x1)) -> a.1(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(17) UsableRulesReductionPairsProof (EQUIVALENT)
176.69/45.77	By using the usable rules with reduction pair processor [LPAR04] with a polynomial ordering [POLO], all dependency pairs and the corresponding usable rules [FROCOS05] can be oriented non-strictly. All non-usable rules are removed, and those dependency pairs and usable rules that have been oriented strictly or contain non-usable symbols in their left-hand side are removed as well.
176.69/45.77	
176.69/45.77	The following dependency pairs can be deleted:
176.69/45.77	
176.69/45.77	   B.0(a.0(x1)) -> B.0(b.0(x1))
176.69/45.77	   B.0(a.0(x1)) -> B.0(x1)
176.69/45.77	The following rules are removed from R:
176.69/45.77	
176.69/45.77	   a.0(x1) -> x1
176.69/45.77	   b.1(a.1(x1)) -> c.0(a.0(c.1(b.1(b.1(x1)))))
176.69/45.77	   b.1(x1) -> x1
176.69/45.77	   c.0(c.1(x1)) -> a.1(x1)
176.69/45.77	Used ordering: POLO with Polynomial interpretation [POLO]:
176.69/45.77	
176.69/45.77	   POL(B.0(x_1)) = x_1
176.69/45.77	   POL(a.0(x_1)) = 1 + x_1
176.69/45.77	   POL(a.1(x_1)) = x_1
176.69/45.77	   POL(b.0(x_1)) = x_1
176.69/45.77	   POL(c.0(x_1)) = x_1
176.69/45.77	   POL(c.1(x_1)) = 1 + x_1
176.69/45.77	
176.69/45.77	
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(18)
176.69/45.77	Obligation:
176.69/45.77	Q DP problem:
176.69/45.77	P is empty.
176.69/45.77	The TRS R consists of the following rules:
176.69/45.77	
176.69/45.77	   b.0(a.0(x1)) -> c.1(a.1(c.0(b.0(b.0(x1)))))
176.69/45.77	   b.0(x1) -> x1
176.69/45.77	   a.1(x1) -> x1
176.69/45.77	   c.1(c.0(x1)) -> a.0(x1)
176.69/45.77	
176.69/45.77	Q is empty.
176.69/45.77	We have to consider all minimal (P,Q,R)-chains.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(19) PisEmptyProof (EQUIVALENT)
176.69/45.77	The TRS P is empty. Hence, there is no (P,Q,R) chain.
176.69/45.77	----------------------------------------
176.69/45.77	
176.69/45.77	(20)
176.69/45.77	YES
177.02/45.88	EOF