3.87/1.91	YES
3.87/1.92	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.87/1.92	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.87/1.92	
3.87/1.92	
3.87/1.92	Termination w.r.t. Q of the given QTRS could be proven:
3.87/1.92	
3.87/1.92	(0) QTRS
3.87/1.92	(1) QTRSRRRProof [EQUIVALENT, 64 ms]
3.87/1.92	(2) QTRS
3.87/1.92	(3) QTRSRRRProof [EQUIVALENT, 0 ms]
3.87/1.92	(4) QTRS
3.87/1.92	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
3.87/1.92	(6) QTRS
3.87/1.92	(7) QTRSRRRProof [EQUIVALENT, 3 ms]
3.87/1.92	(8) QTRS
3.87/1.92	(9) QTRSRRRProof [EQUIVALENT, 0 ms]
3.87/1.92	(10) QTRS
3.87/1.92	(11) RisEmptyProof [EQUIVALENT, 0 ms]
3.87/1.92	(12) YES
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(0)
3.87/1.92	Obligation:
3.87/1.92	Q restricted rewrite system:
3.87/1.92	The TRS R consists of the following rules:
3.87/1.92	
3.87/1.92	   a__f(a, X, X) -> a__f(X, a__b, b)
3.87/1.92	   a__b -> a
3.87/1.92	   mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3)
3.87/1.92	   mark(b) -> a__b
3.87/1.92	   mark(a) -> a
3.87/1.92	   a__f(X1, X2, X3) -> f(X1, X2, X3)
3.87/1.92	   a__b -> b
3.87/1.92	
3.87/1.92	The set Q consists of the following terms:
3.87/1.92	
3.87/1.92	   a__b
3.87/1.92	   mark(f(x0, x1, x2))
3.87/1.92	   mark(b)
3.87/1.92	   mark(a)
3.87/1.92	   a__f(x0, x1, x2)
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(1) QTRSRRRProof (EQUIVALENT)
3.87/1.92	Used ordering:
3.87/1.92	Polynomial interpretation [POLO]:
3.87/1.92	
3.87/1.92	   POL(a) = 1
3.87/1.92	   POL(a__b) = 1
3.87/1.92	   POL(a__f(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3
3.87/1.92	   POL(b) = 0
3.87/1.92	   POL(f(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3
3.87/1.92	   POL(mark(x_1)) = 1 + 2*x_1
3.87/1.92	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.87/1.92	
3.87/1.92	   mark(f(X1, X2, X3)) -> a__f(X1, mark(X2), X3)
3.87/1.92	   mark(a) -> a
3.87/1.92	   a__b -> b
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(2)
3.87/1.92	Obligation:
3.87/1.92	Q restricted rewrite system:
3.87/1.92	The TRS R consists of the following rules:
3.87/1.92	
3.87/1.92	   a__f(a, X, X) -> a__f(X, a__b, b)
3.87/1.92	   a__b -> a
3.87/1.92	   mark(b) -> a__b
3.87/1.92	   a__f(X1, X2, X3) -> f(X1, X2, X3)
3.87/1.92	
3.87/1.92	The set Q consists of the following terms:
3.87/1.92	
3.87/1.92	   a__b
3.87/1.92	   mark(f(x0, x1, x2))
3.87/1.92	   mark(b)
3.87/1.92	   mark(a)
3.87/1.92	   a__f(x0, x1, x2)
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(3) QTRSRRRProof (EQUIVALENT)
3.87/1.92	Used ordering:
3.87/1.92	Polynomial interpretation [POLO]:
3.87/1.92	
3.87/1.92	   POL(a) = 0
3.87/1.92	   POL(a__b) = 0
3.87/1.92	   POL(a__f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3
3.87/1.92	   POL(b) = 0
3.87/1.92	   POL(f(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + x_3
3.87/1.92	   POL(mark(x_1)) = 2 + 2*x_1
3.87/1.92	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.87/1.92	
3.87/1.92	   mark(b) -> a__b
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(4)
3.87/1.92	Obligation:
3.87/1.92	Q restricted rewrite system:
3.87/1.92	The TRS R consists of the following rules:
3.87/1.92	
3.87/1.92	   a__f(a, X, X) -> a__f(X, a__b, b)
3.87/1.92	   a__b -> a
3.87/1.92	   a__f(X1, X2, X3) -> f(X1, X2, X3)
3.87/1.92	
3.87/1.92	The set Q consists of the following terms:
3.87/1.92	
3.87/1.92	   a__b
3.87/1.92	   mark(f(x0, x1, x2))
3.87/1.92	   mark(b)
3.87/1.92	   mark(a)
3.87/1.92	   a__f(x0, x1, x2)
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(5) QTRSRRRProof (EQUIVALENT)
3.87/1.92	Used ordering:
3.87/1.92	Polynomial interpretation [POLO]:
3.87/1.92	
3.87/1.92	   POL(a) = 0
3.87/1.92	   POL(a__b) = 0
3.87/1.92	   POL(a__f(x_1, x_2, x_3)) = 2 + x_1 + 2*x_2 + 2*x_3
3.87/1.92	   POL(b) = 0
3.87/1.92	   POL(f(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3
3.87/1.92	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.87/1.92	
3.87/1.92	   a__f(X1, X2, X3) -> f(X1, X2, X3)
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(6)
3.87/1.92	Obligation:
3.87/1.92	Q restricted rewrite system:
3.87/1.92	The TRS R consists of the following rules:
3.87/1.92	
3.87/1.92	   a__f(a, X, X) -> a__f(X, a__b, b)
3.87/1.92	   a__b -> a
3.87/1.92	
3.87/1.92	The set Q consists of the following terms:
3.87/1.92	
3.87/1.92	   a__b
3.87/1.92	   mark(f(x0, x1, x2))
3.87/1.92	   mark(b)
3.87/1.92	   mark(a)
3.87/1.92	   a__f(x0, x1, x2)
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(7) QTRSRRRProof (EQUIVALENT)
3.87/1.92	Used ordering:
3.87/1.92	Polynomial interpretation [POLO]:
3.87/1.92	
3.87/1.92	   POL(a) = 1
3.87/1.92	   POL(a__b) = 1
3.87/1.92	   POL(a__f(x_1, x_2, x_3)) = 2*x_1 + x_2 + 2*x_3
3.87/1.92	   POL(b) = 0
3.87/1.92	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.87/1.92	
3.87/1.92	   a__f(a, X, X) -> a__f(X, a__b, b)
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(8)
3.87/1.92	Obligation:
3.87/1.92	Q restricted rewrite system:
3.87/1.92	The TRS R consists of the following rules:
3.87/1.92	
3.87/1.92	   a__b -> a
3.87/1.92	
3.87/1.92	The set Q consists of the following terms:
3.87/1.92	
3.87/1.92	   a__b
3.87/1.92	   mark(f(x0, x1, x2))
3.87/1.92	   mark(b)
3.87/1.92	   mark(a)
3.87/1.92	   a__f(x0, x1, x2)
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(9) QTRSRRRProof (EQUIVALENT)
3.87/1.92	Used ordering:
3.87/1.92	Knuth-Bendix order [KBO] with precedence:a__b > a
3.87/1.92	
3.87/1.92	and weight map:
3.87/1.92	
3.87/1.92	   a__b=1
3.87/1.92	   a=1
3.87/1.92	
3.87/1.92	The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
3.87/1.92	
3.87/1.92	   a__b -> a
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(10)
3.87/1.92	Obligation:
3.87/1.92	Q restricted rewrite system:
3.87/1.92	R is empty.
3.87/1.92	The set Q consists of the following terms:
3.87/1.92	
3.87/1.92	   a__b
3.87/1.92	   mark(f(x0, x1, x2))
3.87/1.92	   mark(b)
3.87/1.92	   mark(a)
3.87/1.92	   a__f(x0, x1, x2)
3.87/1.92	
3.87/1.92	
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(11) RisEmptyProof (EQUIVALENT)
3.87/1.92	The TRS R is empty. Hence, termination is trivially proven.
3.87/1.92	----------------------------------------
3.87/1.92	
3.87/1.92	(12)
3.87/1.92	YES
3.87/1.96	EOF