3.60/1.77	YES
3.68/1.78	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.68/1.78	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.68/1.78	
3.68/1.78	
3.68/1.78	Termination w.r.t. Q of the given QTRS could be proven:
3.68/1.78	
3.68/1.78	(0) QTRS
3.68/1.78	(1) QTRSRRRProof [EQUIVALENT, 63 ms]
3.68/1.78	(2) QTRS
3.68/1.78	(3) QTRSRRRProof [EQUIVALENT, 0 ms]
3.68/1.78	(4) QTRS
3.68/1.78	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
3.68/1.78	(6) QTRS
3.68/1.78	(7) DependencyPairsProof [EQUIVALENT, 0 ms]
3.68/1.78	(8) QDP
3.68/1.78	(9) DependencyGraphProof [EQUIVALENT, 0 ms]
3.68/1.78	(10) TRUE
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(0)
3.68/1.78	Obligation:
3.68/1.78	Q restricted rewrite system:
3.68/1.78	The TRS R consists of the following rules:
3.68/1.78	
3.68/1.78	   a__f(X, X) -> a__f(a, b)
3.68/1.78	   a__b -> a
3.68/1.78	   mark(f(X1, X2)) -> a__f(mark(X1), X2)
3.68/1.78	   mark(b) -> a__b
3.68/1.78	   mark(a) -> a
3.68/1.78	   a__f(X1, X2) -> f(X1, X2)
3.68/1.78	   a__b -> b
3.68/1.78	
3.68/1.78	The set Q consists of the following terms:
3.68/1.78	
3.68/1.78	   a__b
3.68/1.78	   mark(f(x0, x1))
3.68/1.78	   mark(b)
3.68/1.78	   mark(a)
3.68/1.78	   a__f(x0, x1)
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(1) QTRSRRRProof (EQUIVALENT)
3.68/1.78	Used ordering:
3.68/1.78	Polynomial interpretation [POLO]:
3.68/1.78	
3.68/1.78	   POL(a) = 0
3.68/1.78	   POL(a__b) = 0
3.68/1.78	   POL(a__f(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
3.68/1.78	   POL(b) = 0
3.68/1.78	   POL(f(x_1, x_2)) = 1 + 2*x_1 + x_2
3.68/1.78	   POL(mark(x_1)) = 2*x_1
3.68/1.78	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.68/1.78	
3.68/1.78	   a__f(X1, X2) -> f(X1, X2)
3.68/1.78	
3.68/1.78	
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(2)
3.68/1.78	Obligation:
3.68/1.78	Q restricted rewrite system:
3.68/1.78	The TRS R consists of the following rules:
3.68/1.78	
3.68/1.78	   a__f(X, X) -> a__f(a, b)
3.68/1.78	   a__b -> a
3.68/1.78	   mark(f(X1, X2)) -> a__f(mark(X1), X2)
3.68/1.78	   mark(b) -> a__b
3.68/1.78	   mark(a) -> a
3.68/1.78	   a__b -> b
3.68/1.78	
3.68/1.78	The set Q consists of the following terms:
3.68/1.78	
3.68/1.78	   a__b
3.68/1.78	   mark(f(x0, x1))
3.68/1.78	   mark(b)
3.68/1.78	   mark(a)
3.68/1.78	   a__f(x0, x1)
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(3) QTRSRRRProof (EQUIVALENT)
3.68/1.78	Used ordering:
3.68/1.78	Polynomial interpretation [POLO]:
3.68/1.78	
3.68/1.78	   POL(a) = 0
3.68/1.78	   POL(a__b) = 0
3.68/1.78	   POL(a__f(x_1, x_2)) = x_1 + 2*x_2
3.68/1.78	   POL(b) = 0
3.68/1.78	   POL(f(x_1, x_2)) = 1 + 2*x_1 + x_2
3.68/1.78	   POL(mark(x_1)) = 2*x_1
3.68/1.78	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.68/1.78	
3.68/1.78	   mark(f(X1, X2)) -> a__f(mark(X1), X2)
3.68/1.78	
3.68/1.78	
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(4)
3.68/1.78	Obligation:
3.68/1.78	Q restricted rewrite system:
3.68/1.78	The TRS R consists of the following rules:
3.68/1.78	
3.68/1.78	   a__f(X, X) -> a__f(a, b)
3.68/1.78	   a__b -> a
3.68/1.78	   mark(b) -> a__b
3.68/1.78	   mark(a) -> a
3.68/1.78	   a__b -> b
3.68/1.78	
3.68/1.78	The set Q consists of the following terms:
3.68/1.78	
3.68/1.78	   a__b
3.68/1.78	   mark(f(x0, x1))
3.68/1.78	   mark(b)
3.68/1.78	   mark(a)
3.68/1.78	   a__f(x0, x1)
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(5) QTRSRRRProof (EQUIVALENT)
3.68/1.78	Used ordering:
3.68/1.78	Quasi precedence:
3.68/1.78	[a__b, mark_1] > [a__f_2, a, b]
3.68/1.78	
3.68/1.78	
3.68/1.78	Status:
3.68/1.78	a__f_2: [2,1]
3.68/1.78	a: multiset status
3.68/1.78	b: multiset status
3.68/1.78	a__b: multiset status
3.68/1.78	mark_1: [1]
3.68/1.78	
3.68/1.78	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.68/1.78	
3.68/1.78	   a__b -> a
3.68/1.78	   mark(b) -> a__b
3.68/1.78	   mark(a) -> a
3.68/1.78	   a__b -> b
3.68/1.78	
3.68/1.78	
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(6)
3.68/1.78	Obligation:
3.68/1.78	Q restricted rewrite system:
3.68/1.78	The TRS R consists of the following rules:
3.68/1.78	
3.68/1.78	   a__f(X, X) -> a__f(a, b)
3.68/1.78	
3.68/1.78	The set Q consists of the following terms:
3.68/1.78	
3.68/1.78	   a__b
3.68/1.78	   mark(f(x0, x1))
3.68/1.78	   mark(b)
3.68/1.78	   mark(a)
3.68/1.78	   a__f(x0, x1)
3.68/1.78	
3.68/1.78	
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(7) DependencyPairsProof (EQUIVALENT)
3.68/1.78	Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(8)
3.68/1.78	Obligation:
3.68/1.78	Q DP problem:
3.68/1.78	The TRS P consists of the following rules:
3.68/1.78	
3.68/1.78	   A__F(X, X) -> A__F(a, b)
3.68/1.78	
3.68/1.78	The TRS R consists of the following rules:
3.68/1.78	
3.68/1.78	   a__f(X, X) -> a__f(a, b)
3.68/1.78	
3.68/1.78	The set Q consists of the following terms:
3.68/1.78	
3.68/1.78	   a__b
3.68/1.78	   mark(f(x0, x1))
3.68/1.78	   mark(b)
3.68/1.78	   mark(a)
3.68/1.78	   a__f(x0, x1)
3.68/1.78	
3.68/1.78	We have to consider all minimal (P,Q,R)-chains.
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(9) DependencyGraphProof (EQUIVALENT)
3.68/1.78	The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 1 less node.
3.68/1.78	----------------------------------------
3.68/1.78	
3.68/1.78	(10)
3.68/1.78	TRUE
3.68/1.80	EOF