4.14/1.88	YES
4.14/1.89	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.14/1.89	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.14/1.89	
4.14/1.89	
4.14/1.89	Termination w.r.t. Q of the given QTRS could be proven:
4.14/1.89	
4.14/1.89	(0) QTRS
4.14/1.89	(1) QTRSRRRProof [EQUIVALENT, 100 ms]
4.14/1.89	(2) QTRS
4.14/1.89	(3) QTRSRRRProof [EQUIVALENT, 0 ms]
4.14/1.89	(4) QTRS
4.14/1.89	(5) RisEmptyProof [EQUIVALENT, 0 ms]
4.14/1.89	(6) YES
4.14/1.89	
4.14/1.89	
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(0)
4.14/1.89	Obligation:
4.14/1.89	Q restricted rewrite system:
4.14/1.89	The TRS R consists of the following rules:
4.14/1.89	
4.14/1.89	   active(2nd(cons1(X, cons(Y, Z)))) -> mark(Y)
4.14/1.89	   active(2nd(cons(X, X1))) -> mark(2nd(cons1(X, X1)))
4.14/1.89	   active(from(X)) -> mark(cons(X, from(s(X))))
4.14/1.89	   active(2nd(X)) -> 2nd(active(X))
4.14/1.89	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.14/1.89	   active(from(X)) -> from(active(X))
4.14/1.89	   active(s(X)) -> s(active(X))
4.14/1.89	   active(cons1(X1, X2)) -> cons1(active(X1), X2)
4.14/1.89	   active(cons1(X1, X2)) -> cons1(X1, active(X2))
4.14/1.89	   2nd(mark(X)) -> mark(2nd(X))
4.14/1.89	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.14/1.89	   from(mark(X)) -> mark(from(X))
4.14/1.89	   s(mark(X)) -> mark(s(X))
4.14/1.89	   cons1(mark(X1), X2) -> mark(cons1(X1, X2))
4.14/1.89	   cons1(X1, mark(X2)) -> mark(cons1(X1, X2))
4.14/1.89	   proper(2nd(X)) -> 2nd(proper(X))
4.14/1.89	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.14/1.89	   proper(from(X)) -> from(proper(X))
4.14/1.89	   proper(s(X)) -> s(proper(X))
4.14/1.89	   proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2))
4.14/1.89	   2nd(ok(X)) -> ok(2nd(X))
4.14/1.89	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
4.14/1.89	   from(ok(X)) -> ok(from(X))
4.14/1.89	   s(ok(X)) -> ok(s(X))
4.14/1.89	   cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2))
4.14/1.89	   top(mark(X)) -> top(proper(X))
4.14/1.89	   top(ok(X)) -> top(active(X))
4.14/1.89	
4.14/1.89	The set Q consists of the following terms:
4.14/1.89	
4.14/1.89	   active(from(x0))
4.14/1.89	   active(2nd(x0))
4.14/1.89	   active(cons(x0, x1))
4.14/1.89	   active(s(x0))
4.14/1.89	   active(cons1(x0, x1))
4.14/1.89	   2nd(mark(x0))
4.14/1.89	   cons(mark(x0), x1)
4.14/1.89	   from(mark(x0))
4.14/1.89	   s(mark(x0))
4.14/1.89	   cons1(mark(x0), x1)
4.14/1.89	   cons1(x0, mark(x1))
4.14/1.89	   proper(2nd(x0))
4.14/1.89	   proper(cons(x0, x1))
4.14/1.89	   proper(from(x0))
4.14/1.89	   proper(s(x0))
4.14/1.89	   proper(cons1(x0, x1))
4.14/1.89	   2nd(ok(x0))
4.14/1.89	   cons(ok(x0), ok(x1))
4.14/1.89	   from(ok(x0))
4.14/1.89	   s(ok(x0))
4.14/1.89	   cons1(ok(x0), ok(x1))
4.14/1.89	   top(mark(x0))
4.14/1.89	   top(ok(x0))
4.14/1.89	
4.14/1.89	
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(1) QTRSRRRProof (EQUIVALENT)
4.14/1.89	Used ordering:
4.14/1.89	Polynomial interpretation [POLO]:
4.14/1.89	
4.14/1.89	   POL(2nd(x_1)) = 1 + 2*x_1
4.14/1.89	   POL(active(x_1)) = 1 + 2*x_1
4.14/1.89	   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
4.14/1.89	   POL(cons1(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
4.14/1.89	   POL(from(x_1)) = 2 + 2*x_1
4.14/1.89	   POL(mark(x_1)) = 1 + x_1
4.14/1.89	   POL(ok(x_1)) = 2 + 2*x_1
4.14/1.89	   POL(proper(x_1)) = x_1
4.14/1.89	   POL(s(x_1)) = x_1
4.14/1.89	   POL(top(x_1)) = x_1
4.14/1.89	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.14/1.89	
4.14/1.89	   active(2nd(cons1(X, cons(Y, Z)))) -> mark(Y)
4.14/1.89	   active(2nd(cons(X, X1))) -> mark(2nd(cons1(X, X1)))
4.14/1.89	   active(from(X)) -> mark(cons(X, from(s(X))))
4.14/1.89	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.14/1.89	   active(from(X)) -> from(active(X))
4.14/1.89	   2nd(mark(X)) -> mark(2nd(X))
4.14/1.89	   from(mark(X)) -> mark(from(X))
4.14/1.89	   cons1(mark(X1), X2) -> mark(cons1(X1, X2))
4.14/1.89	   cons1(X1, mark(X2)) -> mark(cons1(X1, X2))
4.14/1.89	   2nd(ok(X)) -> ok(2nd(X))
4.14/1.89	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
4.14/1.89	   cons1(ok(X1), ok(X2)) -> ok(cons1(X1, X2))
4.14/1.89	   top(mark(X)) -> top(proper(X))
4.14/1.89	   top(ok(X)) -> top(active(X))
4.14/1.89	
4.14/1.89	
4.14/1.89	
4.14/1.89	
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(2)
4.14/1.89	Obligation:
4.14/1.89	Q restricted rewrite system:
4.14/1.89	The TRS R consists of the following rules:
4.14/1.89	
4.14/1.89	   active(2nd(X)) -> 2nd(active(X))
4.14/1.89	   active(s(X)) -> s(active(X))
4.14/1.89	   active(cons1(X1, X2)) -> cons1(active(X1), X2)
4.14/1.89	   active(cons1(X1, X2)) -> cons1(X1, active(X2))
4.14/1.89	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.14/1.89	   s(mark(X)) -> mark(s(X))
4.14/1.89	   proper(2nd(X)) -> 2nd(proper(X))
4.14/1.89	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.14/1.89	   proper(from(X)) -> from(proper(X))
4.14/1.89	   proper(s(X)) -> s(proper(X))
4.14/1.89	   proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2))
4.14/1.89	   from(ok(X)) -> ok(from(X))
4.14/1.89	   s(ok(X)) -> ok(s(X))
4.14/1.89	
4.14/1.89	The set Q consists of the following terms:
4.14/1.89	
4.14/1.89	   active(from(x0))
4.14/1.89	   active(2nd(x0))
4.14/1.89	   active(cons(x0, x1))
4.14/1.89	   active(s(x0))
4.14/1.89	   active(cons1(x0, x1))
4.14/1.89	   2nd(mark(x0))
4.14/1.89	   cons(mark(x0), x1)
4.14/1.89	   from(mark(x0))
4.14/1.89	   s(mark(x0))
4.14/1.89	   cons1(mark(x0), x1)
4.14/1.89	   cons1(x0, mark(x1))
4.14/1.89	   proper(2nd(x0))
4.14/1.89	   proper(cons(x0, x1))
4.14/1.89	   proper(from(x0))
4.14/1.89	   proper(s(x0))
4.14/1.89	   proper(cons1(x0, x1))
4.14/1.89	   2nd(ok(x0))
4.14/1.89	   cons(ok(x0), ok(x1))
4.14/1.89	   from(ok(x0))
4.14/1.89	   s(ok(x0))
4.14/1.89	   cons1(ok(x0), ok(x1))
4.14/1.89	   top(mark(x0))
4.14/1.89	   top(ok(x0))
4.14/1.89	
4.14/1.89	
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(3) QTRSRRRProof (EQUIVALENT)
4.14/1.89	Used ordering:
4.14/1.89	Knuth-Bendix order [KBO] with precedence:proper_1 > from_1 > active_1 > s_1 > ok_1 > cons_2 > mark_1 > cons1_2 > 2nd_1
4.14/1.89	
4.14/1.89	and weight map:
4.14/1.89	
4.14/1.89	   active_1=3
4.14/1.89	   2nd_1=1
4.14/1.89	   s_1=2
4.14/1.89	   mark_1=1
4.14/1.89	   proper_1=0
4.14/1.89	   from_1=2
4.14/1.89	   ok_1=1
4.14/1.89	   cons1_2=0
4.14/1.89	   cons_2=0
4.14/1.89	
4.14/1.89	The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.14/1.89	
4.14/1.89	   active(2nd(X)) -> 2nd(active(X))
4.14/1.89	   active(s(X)) -> s(active(X))
4.14/1.89	   active(cons1(X1, X2)) -> cons1(active(X1), X2)
4.14/1.89	   active(cons1(X1, X2)) -> cons1(X1, active(X2))
4.14/1.89	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.14/1.89	   s(mark(X)) -> mark(s(X))
4.14/1.89	   proper(2nd(X)) -> 2nd(proper(X))
4.14/1.89	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.14/1.89	   proper(from(X)) -> from(proper(X))
4.14/1.89	   proper(s(X)) -> s(proper(X))
4.14/1.89	   proper(cons1(X1, X2)) -> cons1(proper(X1), proper(X2))
4.14/1.89	   from(ok(X)) -> ok(from(X))
4.14/1.89	   s(ok(X)) -> ok(s(X))
4.14/1.89	
4.14/1.89	
4.14/1.89	
4.14/1.89	
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(4)
4.14/1.89	Obligation:
4.14/1.89	Q restricted rewrite system:
4.14/1.89	R is empty.
4.14/1.89	The set Q consists of the following terms:
4.14/1.89	
4.14/1.89	   active(from(x0))
4.14/1.89	   active(2nd(x0))
4.14/1.89	   active(cons(x0, x1))
4.14/1.89	   active(s(x0))
4.14/1.89	   active(cons1(x0, x1))
4.14/1.89	   2nd(mark(x0))
4.14/1.89	   cons(mark(x0), x1)
4.14/1.89	   from(mark(x0))
4.14/1.89	   s(mark(x0))
4.14/1.89	   cons1(mark(x0), x1)
4.14/1.89	   cons1(x0, mark(x1))
4.14/1.89	   proper(2nd(x0))
4.14/1.89	   proper(cons(x0, x1))
4.14/1.89	   proper(from(x0))
4.14/1.89	   proper(s(x0))
4.14/1.89	   proper(cons1(x0, x1))
4.14/1.89	   2nd(ok(x0))
4.14/1.89	   cons(ok(x0), ok(x1))
4.14/1.89	   from(ok(x0))
4.14/1.89	   s(ok(x0))
4.14/1.89	   cons1(ok(x0), ok(x1))
4.14/1.89	   top(mark(x0))
4.14/1.89	   top(ok(x0))
4.14/1.89	
4.14/1.89	
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(5) RisEmptyProof (EQUIVALENT)
4.14/1.89	The TRS R is empty. Hence, termination is trivially proven.
4.14/1.89	----------------------------------------
4.14/1.89	
4.14/1.89	(6)
4.14/1.89	YES
4.33/1.96	EOF