15.41/4.99	YES
15.85/5.01	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
15.85/5.01	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
15.85/5.01	
15.85/5.01	
15.85/5.01	Termination w.r.t. Q of the given QTRS could be proven:
15.85/5.01	
15.85/5.01	(0) QTRS
15.85/5.01	(1) QTRSRRRProof [EQUIVALENT, 69 ms]
15.85/5.01	(2) QTRS
15.85/5.01	(3) DependencyPairsProof [EQUIVALENT, 9 ms]
15.85/5.01	(4) QDP
15.85/5.01	(5) DependencyGraphProof [EQUIVALENT, 0 ms]
15.85/5.01	(6) QDP
15.85/5.01	(7) MRRProof [EQUIVALENT, 39 ms]
15.85/5.01	(8) QDP
15.85/5.01	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
15.85/5.01	(10) TRUE
15.85/5.01	
15.85/5.01	
15.85/5.01	----------------------------------------
15.85/5.01	
15.85/5.01	(0)
15.85/5.01	Obligation:
15.85/5.01	Q restricted rewrite system:
15.85/5.01	The TRS R consists of the following rules:
15.85/5.01	
15.85/5.01	   a(a(x1)) -> b(c(c(c(x1))))
15.85/5.01	   b(c(x1)) -> d(d(d(d(x1))))
15.85/5.01	   a(x1) -> d(c(d(x1)))
15.85/5.01	   b(b(x1)) -> c(c(c(x1)))
15.85/5.01	   c(c(x1)) -> d(d(d(x1)))
15.85/5.01	   c(d(d(x1))) -> a(x1)
15.85/5.01	
15.85/5.01	Q is empty.
15.85/5.01	
15.85/5.01	----------------------------------------
15.85/5.01	
15.85/5.01	(1) QTRSRRRProof (EQUIVALENT)
15.85/5.01	Used ordering:
15.85/5.01	Polynomial interpretation [POLO]:
15.85/5.01	
15.85/5.01	   POL(a(x_1)) = 25 + x_1
15.85/5.01	   POL(b(x_1)) = 17 + x_1
15.85/5.01	   POL(c(x_1)) = 11 + x_1
15.85/5.01	   POL(d(x_1)) = 7 + x_1
15.85/5.01	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
15.85/5.03	
15.85/5.03	   b(b(x1)) -> c(c(c(x1)))
15.85/5.03	   c(c(x1)) -> d(d(d(x1)))
15.85/5.03	
15.85/5.03	
15.85/5.03	
15.85/5.03	
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(2)
15.85/5.03	Obligation:
15.85/5.03	Q restricted rewrite system:
15.85/5.03	The TRS R consists of the following rules:
15.85/5.03	
15.85/5.03	   a(a(x1)) -> b(c(c(c(x1))))
15.85/5.03	   b(c(x1)) -> d(d(d(d(x1))))
15.85/5.03	   a(x1) -> d(c(d(x1)))
15.85/5.03	   c(d(d(x1))) -> a(x1)
15.85/5.03	
15.85/5.03	Q is empty.
15.85/5.03	
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(3) DependencyPairsProof (EQUIVALENT)
15.85/5.03	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(4)
15.85/5.03	Obligation:
15.85/5.03	Q DP problem:
15.85/5.03	The TRS P consists of the following rules:
15.85/5.03	
15.85/5.03	   A(a(x1)) -> B(c(c(c(x1))))
15.85/5.03	   A(a(x1)) -> C(c(c(x1)))
15.85/5.03	   A(a(x1)) -> C(c(x1))
15.85/5.03	   A(a(x1)) -> C(x1)
15.85/5.03	   A(x1) -> C(d(x1))
15.85/5.03	   C(d(d(x1))) -> A(x1)
15.85/5.03	
15.85/5.03	The TRS R consists of the following rules:
15.85/5.03	
15.85/5.03	   a(a(x1)) -> b(c(c(c(x1))))
15.85/5.03	   b(c(x1)) -> d(d(d(d(x1))))
15.85/5.03	   a(x1) -> d(c(d(x1)))
15.85/5.03	   c(d(d(x1))) -> a(x1)
15.85/5.03	
15.85/5.03	Q is empty.
15.85/5.03	We have to consider all minimal (P,Q,R)-chains.
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(5) DependencyGraphProof (EQUIVALENT)
15.85/5.03	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 1 less node.
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(6)
15.85/5.03	Obligation:
15.85/5.03	Q DP problem:
15.85/5.03	The TRS P consists of the following rules:
15.85/5.03	
15.85/5.03	   A(a(x1)) -> C(c(c(x1)))
15.85/5.03	   C(d(d(x1))) -> A(x1)
15.85/5.03	   A(a(x1)) -> C(c(x1))
15.85/5.03	   A(a(x1)) -> C(x1)
15.85/5.03	   A(x1) -> C(d(x1))
15.85/5.03	
15.85/5.03	The TRS R consists of the following rules:
15.85/5.03	
15.85/5.03	   a(a(x1)) -> b(c(c(c(x1))))
15.85/5.03	   b(c(x1)) -> d(d(d(d(x1))))
15.85/5.03	   a(x1) -> d(c(d(x1)))
15.85/5.03	   c(d(d(x1))) -> a(x1)
15.85/5.03	
15.85/5.03	Q is empty.
15.85/5.03	We have to consider all minimal (P,Q,R)-chains.
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(7) MRRProof (EQUIVALENT)
15.85/5.03	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.
15.85/5.03	
15.85/5.03	Strictly oriented dependency pairs:
15.85/5.03	
15.85/5.03	   A(a(x1)) -> C(c(c(x1)))
15.85/5.03	   C(d(d(x1))) -> A(x1)
15.85/5.03	   A(a(x1)) -> C(c(x1))
15.85/5.03	   A(a(x1)) -> C(x1)
15.85/5.03	
15.85/5.03	
15.85/5.03	Used ordering: Polynomial interpretation [POLO]:
15.85/5.03	
15.85/5.03	   POL(A(x_1)) = 1 + x_1
15.85/5.03	   POL(C(x_1)) = x_1
15.85/5.03	   POL(a(x_1)) = 3 + x_1
15.85/5.03	   POL(b(x_1)) = 3 + x_1
15.85/5.03	   POL(c(x_1)) = 1 + x_1
15.85/5.03	   POL(d(x_1)) = 1 + x_1
15.85/5.03	
15.85/5.03	
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(8)
15.85/5.03	Obligation:
15.85/5.03	Q DP problem:
15.85/5.03	The TRS P consists of the following rules:
15.85/5.03	
15.85/5.03	   A(x1) -> C(d(x1))
15.85/5.03	
15.85/5.03	The TRS R consists of the following rules:
15.85/5.03	
15.85/5.03	   a(a(x1)) -> b(c(c(c(x1))))
15.85/5.03	   b(c(x1)) -> d(d(d(d(x1))))
15.85/5.03	   a(x1) -> d(c(d(x1)))
15.85/5.03	   c(d(d(x1))) -> a(x1)
15.85/5.03	
15.85/5.03	Q is empty.
15.85/5.03	We have to consider all minimal (P,Q,R)-chains.
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(9) DependencyGraphProof (EQUIVALENT)
15.85/5.03	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
15.85/5.03	----------------------------------------
15.85/5.03	
15.85/5.03	(10)
15.85/5.03	TRUE
15.85/5.08	EOF