4.25/1.84	YES
4.25/1.85	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.25/1.85	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.25/1.85	
4.25/1.85	
4.25/1.85	Termination w.r.t. Q of the given QTRS could be proven:
4.25/1.85	
4.25/1.85	(0) QTRS
4.25/1.85	(1) QTRSRRRProof [EQUIVALENT, 107 ms]
4.25/1.85	(2) QTRS
4.25/1.85	(3) QTRSRRRProof [EQUIVALENT, 19 ms]
4.25/1.85	(4) QTRS
4.25/1.85	(5) QTRSRRRProof [EQUIVALENT, 0 ms]
4.25/1.85	(6) QTRS
4.25/1.85	(7) RisEmptyProof [EQUIVALENT, 0 ms]
4.25/1.85	(8) YES
4.25/1.85	
4.25/1.85	
4.25/1.85	----------------------------------------
4.25/1.85	
4.25/1.85	(0)
4.25/1.85	Obligation:
4.25/1.85	Q restricted rewrite system:
4.25/1.85	The TRS R consists of the following rules:
4.25/1.85	
4.25/1.85	   a__and(true, X) -> mark(X)
4.25/1.85	   a__and(false, Y) -> false
4.25/1.85	   a__if(true, X, Y) -> mark(X)
4.25/1.85	   a__if(false, X, Y) -> mark(Y)
4.25/1.85	   a__add(0, X) -> mark(X)
4.25/1.85	   a__add(s(X), Y) -> s(add(X, Y))
4.25/1.85	   a__first(0, X) -> nil
4.25/1.85	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
4.25/1.85	   a__from(X) -> cons(X, from(s(X)))
4.25/1.85	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
4.25/1.85	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
4.25/1.85	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
4.25/1.85	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
4.25/1.85	   mark(from(X)) -> a__from(X)
4.25/1.85	   mark(true) -> true
4.25/1.85	   mark(false) -> false
4.25/1.85	   mark(0) -> 0
4.25/1.85	   mark(s(X)) -> s(X)
4.25/1.85	   mark(nil) -> nil
4.25/1.85	   mark(cons(X1, X2)) -> cons(X1, X2)
4.25/1.85	   a__and(X1, X2) -> and(X1, X2)
4.25/1.85	   a__if(X1, X2, X3) -> if(X1, X2, X3)
4.25/1.85	   a__add(X1, X2) -> add(X1, X2)
4.25/1.85	   a__first(X1, X2) -> first(X1, X2)
4.25/1.85	   a__from(X) -> from(X)
4.25/1.85	
4.25/1.85	The set Q consists of the following terms:
4.25/1.85	
4.25/1.85	   a__from(x0)
4.25/1.85	   mark(and(x0, x1))
4.25/1.85	   mark(if(x0, x1, x2))
4.25/1.85	   mark(add(x0, x1))
4.25/1.85	   mark(first(x0, x1))
4.25/1.85	   mark(from(x0))
4.25/1.85	   mark(true)
4.25/1.85	   mark(false)
4.25/1.85	   mark(0)
4.25/1.85	   mark(s(x0))
4.25/1.85	   mark(nil)
4.25/1.85	   mark(cons(x0, x1))
4.25/1.85	   a__and(x0, x1)
4.25/1.85	   a__if(x0, x1, x2)
4.25/1.85	   a__add(x0, x1)
4.25/1.85	   a__first(x0, x1)
4.25/1.85	
4.25/1.85	
4.25/1.85	----------------------------------------
4.25/1.85	
4.25/1.85	(1) QTRSRRRProof (EQUIVALENT)
4.25/1.85	Used ordering:
4.25/1.85	Polynomial interpretation [POLO]:
4.25/1.85	
4.25/1.85	   POL(0) = 1
4.25/1.85	   POL(a__add(x_1, x_2)) = 2 + x_1 + 2*x_2
4.25/1.85	   POL(a__and(x_1, x_2)) = 2 + x_1 + 2*x_2
4.25/1.85	   POL(a__first(x_1, x_2)) = 2 + x_1 + 2*x_2
4.25/1.85	   POL(a__from(x_1)) = 2 + 2*x_1
4.25/1.85	   POL(a__if(x_1, x_2, x_3)) = 2 + 2*x_1 + 2*x_2 + 2*x_3
4.25/1.86	   POL(add(x_1, x_2)) = 1 + x_1 + 2*x_2
4.25/1.86	   POL(and(x_1, x_2)) = 1 + x_1 + 2*x_2
4.25/1.86	   POL(cons(x_1, x_2)) = 1 + x_1 + x_2
4.25/1.86	   POL(false) = 1
4.25/1.86	   POL(first(x_1, x_2)) = 1 + x_1 + 2*x_2
4.25/1.86	   POL(from(x_1)) = 1 + x_1
4.25/1.86	   POL(if(x_1, x_2, x_3)) = 1 + 2*x_1 + 2*x_2 + 2*x_3
4.25/1.86	   POL(mark(x_1)) = 2*x_1
4.25/1.86	   POL(nil) = 1
4.25/1.86	   POL(s(x_1)) = x_1
4.25/1.86	   POL(true) = 1
4.25/1.86	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.25/1.86	
4.25/1.86	   a__and(true, X) -> mark(X)
4.25/1.86	   a__and(false, Y) -> false
4.25/1.86	   a__if(true, X, Y) -> mark(X)
4.25/1.86	   a__if(false, X, Y) -> mark(Y)
4.25/1.86	   a__add(0, X) -> mark(X)
4.25/1.86	   a__add(s(X), Y) -> s(add(X, Y))
4.25/1.86	   a__first(0, X) -> nil
4.25/1.86	   a__first(s(X), cons(Y, Z)) -> cons(Y, first(X, Z))
4.25/1.86	   mark(true) -> true
4.25/1.86	   mark(false) -> false
4.25/1.86	   mark(0) -> 0
4.25/1.86	   mark(nil) -> nil
4.25/1.86	   mark(cons(X1, X2)) -> cons(X1, X2)
4.25/1.86	   a__and(X1, X2) -> and(X1, X2)
4.25/1.86	   a__if(X1, X2, X3) -> if(X1, X2, X3)
4.25/1.86	   a__add(X1, X2) -> add(X1, X2)
4.25/1.86	   a__first(X1, X2) -> first(X1, X2)
4.25/1.86	   a__from(X) -> from(X)
4.25/1.86	
4.25/1.86	
4.25/1.86	
4.25/1.86	
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(2)
4.25/1.86	Obligation:
4.25/1.86	Q restricted rewrite system:
4.25/1.86	The TRS R consists of the following rules:
4.25/1.86	
4.25/1.86	   a__from(X) -> cons(X, from(s(X)))
4.25/1.86	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
4.25/1.86	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
4.25/1.86	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
4.25/1.86	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
4.25/1.86	   mark(from(X)) -> a__from(X)
4.25/1.86	   mark(s(X)) -> s(X)
4.25/1.86	
4.25/1.86	The set Q consists of the following terms:
4.25/1.86	
4.25/1.86	   a__from(x0)
4.25/1.86	   mark(and(x0, x1))
4.25/1.86	   mark(if(x0, x1, x2))
4.25/1.86	   mark(add(x0, x1))
4.25/1.86	   mark(first(x0, x1))
4.25/1.86	   mark(from(x0))
4.25/1.86	   mark(true)
4.25/1.86	   mark(false)
4.25/1.86	   mark(0)
4.25/1.86	   mark(s(x0))
4.25/1.86	   mark(nil)
4.25/1.86	   mark(cons(x0, x1))
4.25/1.86	   a__and(x0, x1)
4.25/1.86	   a__if(x0, x1, x2)
4.25/1.86	   a__add(x0, x1)
4.25/1.86	   a__first(x0, x1)
4.25/1.86	
4.25/1.86	
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(3) QTRSRRRProof (EQUIVALENT)
4.25/1.86	Used ordering:
4.25/1.86	Polynomial interpretation [POLO]:
4.25/1.86	
4.25/1.86	   POL(a__add(x_1, x_2)) = 1 + 2*x_1 + 2*x_2
4.25/1.86	   POL(a__and(x_1, x_2)) = x_1 + 2*x_2
4.25/1.86	   POL(a__first(x_1, x_2)) = x_1 + x_2
4.25/1.86	   POL(a__from(x_1)) = 2 + 2*x_1
4.25/1.86	   POL(a__if(x_1, x_2, x_3)) = 1 + x_1 + 2*x_2 + 2*x_3
4.25/1.86	   POL(add(x_1, x_2)) = 2 + 2*x_1 + x_2
4.25/1.86	   POL(and(x_1, x_2)) = 1 + 2*x_1 + x_2
4.25/1.86	   POL(cons(x_1, x_2)) = x_1 + x_2
4.25/1.86	   POL(first(x_1, x_2)) = 2 + 2*x_1 + 2*x_2
4.25/1.86	   POL(from(x_1)) = x_1
4.25/1.86	   POL(if(x_1, x_2, x_3)) = 1 + 2*x_1 + x_2 + x_3
4.25/1.86	   POL(mark(x_1)) = 2 + 2*x_1
4.25/1.86	   POL(s(x_1)) = 1 + x_1
4.25/1.86	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.25/1.86	
4.25/1.86	   a__from(X) -> cons(X, from(s(X)))
4.25/1.86	   mark(and(X1, X2)) -> a__and(mark(X1), X2)
4.25/1.86	   mark(if(X1, X2, X3)) -> a__if(mark(X1), X2, X3)
4.25/1.86	   mark(add(X1, X2)) -> a__add(mark(X1), X2)
4.25/1.86	   mark(first(X1, X2)) -> a__first(mark(X1), mark(X2))
4.25/1.86	   mark(s(X)) -> s(X)
4.25/1.86	
4.25/1.86	
4.25/1.86	
4.25/1.86	
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(4)
4.25/1.86	Obligation:
4.25/1.86	Q restricted rewrite system:
4.25/1.86	The TRS R consists of the following rules:
4.25/1.86	
4.25/1.86	   mark(from(X)) -> a__from(X)
4.25/1.86	
4.25/1.86	The set Q consists of the following terms:
4.25/1.86	
4.25/1.86	   a__from(x0)
4.25/1.86	   mark(and(x0, x1))
4.25/1.86	   mark(if(x0, x1, x2))
4.25/1.86	   mark(add(x0, x1))
4.25/1.86	   mark(first(x0, x1))
4.25/1.86	   mark(from(x0))
4.25/1.86	   mark(true)
4.25/1.86	   mark(false)
4.25/1.86	   mark(0)
4.25/1.86	   mark(s(x0))
4.25/1.86	   mark(nil)
4.25/1.86	   mark(cons(x0, x1))
4.25/1.86	   a__and(x0, x1)
4.25/1.86	   a__if(x0, x1, x2)
4.25/1.86	   a__add(x0, x1)
4.25/1.86	   a__first(x0, x1)
4.25/1.86	
4.25/1.86	
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(5) QTRSRRRProof (EQUIVALENT)
4.25/1.86	Used ordering:
4.25/1.86	Polynomial interpretation [POLO]:
4.25/1.86	
4.25/1.86	   POL(a__from(x_1)) = 2 + 2*x_1
4.25/1.86	   POL(from(x_1)) = 1 + x_1
4.25/1.86	   POL(mark(x_1)) = 2 + 2*x_1
4.25/1.86	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.25/1.86	
4.25/1.86	   mark(from(X)) -> a__from(X)
4.25/1.86	
4.25/1.86	
4.25/1.86	
4.25/1.86	
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(6)
4.25/1.86	Obligation:
4.25/1.86	Q restricted rewrite system:
4.25/1.86	R is empty.
4.25/1.86	The set Q consists of the following terms:
4.25/1.86	
4.25/1.86	   a__from(x0)
4.25/1.86	   mark(and(x0, x1))
4.25/1.86	   mark(if(x0, x1, x2))
4.25/1.86	   mark(add(x0, x1))
4.25/1.86	   mark(first(x0, x1))
4.25/1.86	   mark(from(x0))
4.25/1.86	   mark(true)
4.25/1.86	   mark(false)
4.25/1.86	   mark(0)
4.25/1.86	   mark(s(x0))
4.25/1.86	   mark(nil)
4.25/1.86	   mark(cons(x0, x1))
4.25/1.86	   a__and(x0, x1)
4.25/1.86	   a__if(x0, x1, x2)
4.25/1.86	   a__add(x0, x1)
4.25/1.86	   a__first(x0, x1)
4.25/1.86	
4.25/1.86	
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(7) RisEmptyProof (EQUIVALENT)
4.25/1.86	The TRS R is empty. Hence, termination is trivially proven.
4.25/1.86	----------------------------------------
4.25/1.86	
4.25/1.86	(8)
4.25/1.86	YES
4.25/1.89	EOF