4.81/2.09	YES
4.81/2.10	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
4.81/2.10	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.81/2.10	
4.81/2.10	
4.81/2.10	Termination w.r.t. Q of the given QTRS could be proven:
4.81/2.10	
4.81/2.10	(0) QTRS
4.81/2.10	(1) QTRSRRRProof [EQUIVALENT, 91 ms]
4.81/2.10	(2) QTRS
4.81/2.10	(3) QTRSRRRProof [EQUIVALENT, 26 ms]
4.81/2.10	(4) QTRS
4.81/2.10	(5) QTRSRRRProof [EQUIVALENT, 14 ms]
4.81/2.10	(6) QTRS
4.81/2.10	(7) QTRSRRRProof [EQUIVALENT, 0 ms]
4.81/2.10	(8) QTRS
4.81/2.10	(9) QTRSRRRProof [EQUIVALENT, 10 ms]
4.81/2.10	(10) QTRS
4.81/2.10	(11) QTRSRRRProof [EQUIVALENT, 0 ms]
4.81/2.10	(12) QTRS
4.81/2.10	(13) RisEmptyProof [EQUIVALENT, 0 ms]
4.81/2.10	(14) YES
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(0)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	The TRS R consists of the following rules:
4.81/2.10	
4.81/2.10	   active(2nd(cons(X, cons(Y, Z)))) -> mark(Y)
4.81/2.10	   active(from(X)) -> mark(cons(X, from(s(X))))
4.81/2.10	   active(2nd(X)) -> 2nd(active(X))
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(from(X)) -> from(active(X))
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   2nd(mark(X)) -> mark(2nd(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(2nd(X)) -> 2nd(proper(X))
4.81/2.10	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	   2nd(ok(X)) -> ok(2nd(X))
4.81/2.10	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
4.81/2.10	   from(ok(X)) -> ok(from(X))
4.81/2.10	   s(ok(X)) -> ok(s(X))
4.81/2.10	   top(mark(X)) -> top(proper(X))
4.81/2.10	   top(ok(X)) -> top(active(X))
4.81/2.10	
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(1) QTRSRRRProof (EQUIVALENT)
4.81/2.10	Used ordering:
4.81/2.10	Polynomial interpretation [POLO]:
4.81/2.10	
4.81/2.10	   POL(2nd(x_1)) = 2*x_1
4.81/2.10	   POL(active(x_1)) = 2*x_1
4.81/2.10	   POL(cons(x_1, x_2)) = x_1 + x_2
4.81/2.10	   POL(from(x_1)) = x_1
4.81/2.10	   POL(mark(x_1)) = x_1
4.81/2.10	   POL(ok(x_1)) = 1 + 2*x_1
4.81/2.10	   POL(proper(x_1)) = x_1
4.81/2.10	   POL(s(x_1)) = x_1
4.81/2.10	   POL(top(x_1)) = 2*x_1
4.81/2.10	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.81/2.10	
4.81/2.10	   2nd(ok(X)) -> ok(2nd(X))
4.81/2.10	   cons(ok(X1), ok(X2)) -> ok(cons(X1, X2))
4.81/2.10	   top(ok(X)) -> top(active(X))
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(2)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	The TRS R consists of the following rules:
4.81/2.10	
4.81/2.10	   active(2nd(cons(X, cons(Y, Z)))) -> mark(Y)
4.81/2.10	   active(from(X)) -> mark(cons(X, from(s(X))))
4.81/2.10	   active(2nd(X)) -> 2nd(active(X))
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(from(X)) -> from(active(X))
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   2nd(mark(X)) -> mark(2nd(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(2nd(X)) -> 2nd(proper(X))
4.81/2.10	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	   from(ok(X)) -> ok(from(X))
4.81/2.10	   s(ok(X)) -> ok(s(X))
4.81/2.10	   top(mark(X)) -> top(proper(X))
4.81/2.10	
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(3) QTRSRRRProof (EQUIVALENT)
4.81/2.10	Used ordering:
4.81/2.10	Polynomial interpretation [POLO]:
4.81/2.10	
4.81/2.10	   POL(2nd(x_1)) = 1 + 2*x_1
4.81/2.10	   POL(active(x_1)) = 2*x_1
4.81/2.10	   POL(cons(x_1, x_2)) = 2*x_1 + x_2
4.81/2.10	   POL(from(x_1)) = 2*x_1
4.81/2.10	   POL(mark(x_1)) = x_1
4.81/2.10	   POL(ok(x_1)) = 2*x_1
4.81/2.10	   POL(proper(x_1)) = x_1
4.81/2.10	   POL(s(x_1)) = x_1
4.81/2.10	   POL(top(x_1)) = 2*x_1
4.81/2.10	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.81/2.10	
4.81/2.10	   active(2nd(cons(X, cons(Y, Z)))) -> mark(Y)
4.81/2.10	   active(2nd(X)) -> 2nd(active(X))
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(4)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	The TRS R consists of the following rules:
4.81/2.10	
4.81/2.10	   active(from(X)) -> mark(cons(X, from(s(X))))
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(from(X)) -> from(active(X))
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   2nd(mark(X)) -> mark(2nd(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(2nd(X)) -> 2nd(proper(X))
4.81/2.10	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	   from(ok(X)) -> ok(from(X))
4.81/2.10	   s(ok(X)) -> ok(s(X))
4.81/2.10	   top(mark(X)) -> top(proper(X))
4.81/2.10	
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(5) QTRSRRRProof (EQUIVALENT)
4.81/2.10	Used ordering:
4.81/2.10	Polynomial interpretation [POLO]:
4.81/2.10	
4.81/2.10	   POL(2nd(x_1)) = x_1
4.81/2.10	   POL(active(x_1)) = 2*x_1
4.81/2.10	   POL(cons(x_1, x_2)) = x_1 + x_2
4.81/2.10	   POL(from(x_1)) = 2*x_1
4.81/2.10	   POL(mark(x_1)) = x_1
4.81/2.10	   POL(ok(x_1)) = 2 + 2*x_1
4.81/2.10	   POL(proper(x_1)) = x_1
4.81/2.10	   POL(s(x_1)) = x_1
4.81/2.10	   POL(top(x_1)) = x_1
4.81/2.10	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.81/2.10	
4.81/2.10	   from(ok(X)) -> ok(from(X))
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(6)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	The TRS R consists of the following rules:
4.81/2.10	
4.81/2.10	   active(from(X)) -> mark(cons(X, from(s(X))))
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(from(X)) -> from(active(X))
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   2nd(mark(X)) -> mark(2nd(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(2nd(X)) -> 2nd(proper(X))
4.81/2.10	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	   s(ok(X)) -> ok(s(X))
4.81/2.10	   top(mark(X)) -> top(proper(X))
4.81/2.10	
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(7) QTRSRRRProof (EQUIVALENT)
4.81/2.10	Used ordering:
4.81/2.10	Polynomial interpretation [POLO]:
4.81/2.10	
4.81/2.10	   POL(2nd(x_1)) = 2*x_1
4.81/2.10	   POL(active(x_1)) = 2*x_1
4.81/2.10	   POL(cons(x_1, x_2)) = x_1 + x_2
4.81/2.10	   POL(from(x_1)) = 2 + x_1
4.81/2.10	   POL(mark(x_1)) = 1 + x_1
4.81/2.10	   POL(ok(x_1)) = 2*x_1
4.81/2.10	   POL(proper(x_1)) = x_1
4.81/2.10	   POL(s(x_1)) = x_1
4.81/2.10	   POL(top(x_1)) = x_1
4.81/2.10	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.81/2.10	
4.81/2.10	   active(from(X)) -> mark(cons(X, from(s(X))))
4.81/2.10	   active(from(X)) -> from(active(X))
4.81/2.10	   2nd(mark(X)) -> mark(2nd(X))
4.81/2.10	   top(mark(X)) -> top(proper(X))
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(8)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	The TRS R consists of the following rules:
4.81/2.10	
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(2nd(X)) -> 2nd(proper(X))
4.81/2.10	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	   s(ok(X)) -> ok(s(X))
4.81/2.10	
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(9) QTRSRRRProof (EQUIVALENT)
4.81/2.10	Used ordering:
4.81/2.10	Polynomial interpretation [POLO]:
4.81/2.10	
4.81/2.10	   POL(2nd(x_1)) = 1 + x_1
4.81/2.10	   POL(active(x_1)) = x_1
4.81/2.10	   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
4.81/2.10	   POL(from(x_1)) = x_1
4.81/2.10	   POL(mark(x_1)) = x_1
4.81/2.10	   POL(ok(x_1)) = 2 + 2*x_1
4.81/2.10	   POL(proper(x_1)) = 2*x_1
4.81/2.10	   POL(s(x_1)) = 2*x_1
4.81/2.10	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.81/2.10	
4.81/2.10	   proper(2nd(X)) -> 2nd(proper(X))
4.81/2.10	   proper(cons(X1, X2)) -> cons(proper(X1), proper(X2))
4.81/2.10	   s(ok(X)) -> ok(s(X))
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(10)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	The TRS R consists of the following rules:
4.81/2.10	
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(11) QTRSRRRProof (EQUIVALENT)
4.81/2.10	Used ordering:
4.81/2.10	Knuth-Bendix order [KBO] with precedence:proper_1 > from_1 > active_1 > s_1 > cons_2 > mark_1
4.81/2.10	
4.81/2.10	and weight map:
4.81/2.10	
4.81/2.10	   active_1=3
4.81/2.10	   s_1=2
4.81/2.10	   mark_1=1
4.81/2.10	   from_1=2
4.81/2.10	   proper_1=3
4.81/2.10	   cons_2=0
4.81/2.10	
4.81/2.10	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.81/2.10	
4.81/2.10	   active(cons(X1, X2)) -> cons(active(X1), X2)
4.81/2.10	   active(s(X)) -> s(active(X))
4.81/2.10	   cons(mark(X1), X2) -> mark(cons(X1, X2))
4.81/2.10	   from(mark(X)) -> mark(from(X))
4.81/2.10	   s(mark(X)) -> mark(s(X))
4.81/2.10	   proper(from(X)) -> from(proper(X))
4.81/2.10	   proper(s(X)) -> s(proper(X))
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(12)
4.81/2.10	Obligation:
4.81/2.10	Q restricted rewrite system:
4.81/2.10	R is empty.
4.81/2.10	The set Q consists of the following terms:
4.81/2.10	
4.81/2.10	   active(from(x0))
4.81/2.10	   active(2nd(x0))
4.81/2.10	   active(cons(x0, x1))
4.81/2.10	   active(s(x0))
4.81/2.10	   2nd(mark(x0))
4.81/2.10	   cons(mark(x0), x1)
4.81/2.10	   from(mark(x0))
4.81/2.10	   s(mark(x0))
4.81/2.10	   proper(2nd(x0))
4.81/2.10	   proper(cons(x0, x1))
4.81/2.10	   proper(from(x0))
4.81/2.10	   proper(s(x0))
4.81/2.10	   2nd(ok(x0))
4.81/2.10	   cons(ok(x0), ok(x1))
4.81/2.10	   from(ok(x0))
4.81/2.10	   s(ok(x0))
4.81/2.10	   top(mark(x0))
4.81/2.10	   top(ok(x0))
4.81/2.10	
4.81/2.10	
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(13) RisEmptyProof (EQUIVALENT)
4.81/2.10	The TRS R is empty. Hence, termination is trivially proven.
4.81/2.10	----------------------------------------
4.81/2.10	
4.81/2.10	(14)
4.81/2.10	YES
5.03/2.13	EOF