4.61/1.92	YES
4.61/1.93	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
4.61/1.93	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
4.61/1.93	
4.61/1.93	
4.61/1.93	Termination w.r.t. Q of the given QTRS could be proven:
4.61/1.93	
4.61/1.93	(0) QTRS
4.61/1.93	(1) QTRSRRRProof [EQUIVALENT, 64 ms]
4.61/1.93	(2) QTRS
4.61/1.93	(3) QTRSRRRProof [EQUIVALENT, 4 ms]
4.61/1.93	(4) QTRS
4.61/1.93	(5) QTRSRRRProof [EQUIVALENT, 11 ms]
4.61/1.93	(6) QTRS
4.61/1.93	(7) QTRSRRRProof [EQUIVALENT, 14 ms]
4.61/1.93	(8) QTRS
4.61/1.93	(9) QTRSRRRProof [EQUIVALENT, 0 ms]
4.61/1.93	(10) QTRS
4.61/1.93	(11) RisEmptyProof [EQUIVALENT, 0 ms]
4.61/1.93	(12) YES
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(0)
4.61/1.93	Obligation:
4.61/1.93	Q restricted rewrite system:
4.61/1.93	The TRS R consists of the following rules:
4.61/1.93	
4.61/1.93	   active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z)))
4.61/1.93	   active(__(X, nil)) -> mark(X)
4.61/1.93	   active(__(nil, X)) -> mark(X)
4.61/1.93	   active(and(tt, X)) -> mark(X)
4.61/1.93	   active(isNePal(__(I, __(P, I)))) -> mark(tt)
4.61/1.93	   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
4.61/1.93	   mark(nil) -> active(nil)
4.61/1.93	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
4.61/1.93	   mark(tt) -> active(tt)
4.61/1.93	   mark(isNePal(X)) -> active(isNePal(mark(X)))
4.61/1.93	   __(mark(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, mark(X2)) -> __(X1, X2)
4.61/1.93	   __(active(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, active(X2)) -> __(X1, X2)
4.61/1.93	   and(mark(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, mark(X2)) -> and(X1, X2)
4.61/1.93	   and(active(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, active(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(mark(X)) -> isNePal(X)
4.61/1.93	   isNePal(active(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	The set Q consists of the following terms:
4.61/1.93	
4.61/1.93	   active(__(__(x0, x1), x2))
4.61/1.93	   active(__(x0, nil))
4.61/1.93	   active(__(nil, x0))
4.61/1.93	   active(and(tt, x0))
4.61/1.93	   active(isNePal(__(x0, __(x1, x0))))
4.61/1.93	   mark(__(x0, x1))
4.61/1.93	   mark(nil)
4.61/1.93	   mark(and(x0, x1))
4.61/1.93	   mark(tt)
4.61/1.93	   mark(isNePal(x0))
4.61/1.93	   __(mark(x0), x1)
4.61/1.93	   __(x0, mark(x1))
4.61/1.93	   __(active(x0), x1)
4.61/1.93	   __(x0, active(x1))
4.61/1.93	   and(mark(x0), x1)
4.61/1.93	   and(x0, mark(x1))
4.61/1.93	   and(active(x0), x1)
4.61/1.93	   and(x0, active(x1))
4.61/1.93	   isNePal(mark(x0))
4.61/1.93	   isNePal(active(x0))
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(1) QTRSRRRProof (EQUIVALENT)
4.61/1.93	Used ordering:
4.61/1.93	Polynomial interpretation [POLO]:
4.61/1.93	
4.61/1.93	   POL(__(x_1, x_2)) = x_1 + x_2
4.61/1.93	   POL(active(x_1)) = x_1
4.61/1.93	   POL(and(x_1, x_2)) = 1 + x_1 + 2*x_2
4.61/1.93	   POL(isNePal(x_1)) = x_1
4.61/1.93	   POL(mark(x_1)) = x_1
4.61/1.93	   POL(nil) = 0
4.61/1.93	   POL(tt) = 0
4.61/1.93	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.61/1.93	
4.61/1.93	   active(and(tt, X)) -> mark(X)
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(2)
4.61/1.93	Obligation:
4.61/1.93	Q restricted rewrite system:
4.61/1.93	The TRS R consists of the following rules:
4.61/1.93	
4.61/1.93	   active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z)))
4.61/1.93	   active(__(X, nil)) -> mark(X)
4.61/1.93	   active(__(nil, X)) -> mark(X)
4.61/1.93	   active(isNePal(__(I, __(P, I)))) -> mark(tt)
4.61/1.93	   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
4.61/1.93	   mark(nil) -> active(nil)
4.61/1.93	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
4.61/1.93	   mark(tt) -> active(tt)
4.61/1.93	   mark(isNePal(X)) -> active(isNePal(mark(X)))
4.61/1.93	   __(mark(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, mark(X2)) -> __(X1, X2)
4.61/1.93	   __(active(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, active(X2)) -> __(X1, X2)
4.61/1.93	   and(mark(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, mark(X2)) -> and(X1, X2)
4.61/1.93	   and(active(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, active(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(mark(X)) -> isNePal(X)
4.61/1.93	   isNePal(active(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	The set Q consists of the following terms:
4.61/1.93	
4.61/1.93	   active(__(__(x0, x1), x2))
4.61/1.93	   active(__(x0, nil))
4.61/1.93	   active(__(nil, x0))
4.61/1.93	   active(and(tt, x0))
4.61/1.93	   active(isNePal(__(x0, __(x1, x0))))
4.61/1.93	   mark(__(x0, x1))
4.61/1.93	   mark(nil)
4.61/1.93	   mark(and(x0, x1))
4.61/1.93	   mark(tt)
4.61/1.93	   mark(isNePal(x0))
4.61/1.93	   __(mark(x0), x1)
4.61/1.93	   __(x0, mark(x1))
4.61/1.93	   __(active(x0), x1)
4.61/1.93	   __(x0, active(x1))
4.61/1.93	   and(mark(x0), x1)
4.61/1.93	   and(x0, mark(x1))
4.61/1.93	   and(active(x0), x1)
4.61/1.93	   and(x0, active(x1))
4.61/1.93	   isNePal(mark(x0))
4.61/1.93	   isNePal(active(x0))
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(3) QTRSRRRProof (EQUIVALENT)
4.61/1.93	Used ordering:
4.61/1.93	Polynomial interpretation [POLO]:
4.61/1.93	
4.61/1.93	   POL(__(x_1, x_2)) = 2 + x_1 + x_2
4.61/1.93	   POL(active(x_1)) = x_1
4.61/1.93	   POL(and(x_1, x_2)) = 2*x_1 + 2*x_2
4.61/1.93	   POL(isNePal(x_1)) = x_1
4.61/1.93	   POL(mark(x_1)) = x_1
4.61/1.93	   POL(nil) = 0
4.61/1.93	   POL(tt) = 0
4.61/1.93	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.61/1.93	
4.61/1.93	   active(__(X, nil)) -> mark(X)
4.61/1.93	   active(__(nil, X)) -> mark(X)
4.61/1.93	   active(isNePal(__(I, __(P, I)))) -> mark(tt)
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(4)
4.61/1.93	Obligation:
4.61/1.93	Q restricted rewrite system:
4.61/1.93	The TRS R consists of the following rules:
4.61/1.93	
4.61/1.93	   active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z)))
4.61/1.93	   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
4.61/1.93	   mark(nil) -> active(nil)
4.61/1.93	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
4.61/1.93	   mark(tt) -> active(tt)
4.61/1.93	   mark(isNePal(X)) -> active(isNePal(mark(X)))
4.61/1.93	   __(mark(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, mark(X2)) -> __(X1, X2)
4.61/1.93	   __(active(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, active(X2)) -> __(X1, X2)
4.61/1.93	   and(mark(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, mark(X2)) -> and(X1, X2)
4.61/1.93	   and(active(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, active(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(mark(X)) -> isNePal(X)
4.61/1.93	   isNePal(active(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	The set Q consists of the following terms:
4.61/1.93	
4.61/1.93	   active(__(__(x0, x1), x2))
4.61/1.93	   active(__(x0, nil))
4.61/1.93	   active(__(nil, x0))
4.61/1.93	   active(and(tt, x0))
4.61/1.93	   active(isNePal(__(x0, __(x1, x0))))
4.61/1.93	   mark(__(x0, x1))
4.61/1.93	   mark(nil)
4.61/1.93	   mark(and(x0, x1))
4.61/1.93	   mark(tt)
4.61/1.93	   mark(isNePal(x0))
4.61/1.93	   __(mark(x0), x1)
4.61/1.93	   __(x0, mark(x1))
4.61/1.93	   __(active(x0), x1)
4.61/1.93	   __(x0, active(x1))
4.61/1.93	   and(mark(x0), x1)
4.61/1.93	   and(x0, mark(x1))
4.61/1.93	   and(active(x0), x1)
4.61/1.93	   and(x0, active(x1))
4.61/1.93	   isNePal(mark(x0))
4.61/1.93	   isNePal(active(x0))
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(5) QTRSRRRProof (EQUIVALENT)
4.61/1.93	Used ordering:
4.61/1.93	Polynomial interpretation [POLO]:
4.61/1.93	
4.61/1.93	   POL(__(x_1, x_2)) = 2 + 2*x_1 + x_2
4.61/1.93	   POL(active(x_1)) = x_1
4.61/1.93	   POL(and(x_1, x_2)) = 2*x_1 + x_2
4.61/1.93	   POL(isNePal(x_1)) = x_1
4.61/1.93	   POL(mark(x_1)) = x_1
4.61/1.93	   POL(nil) = 0
4.61/1.93	   POL(tt) = 0
4.61/1.93	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.61/1.93	
4.61/1.93	   active(__(__(X, Y), Z)) -> mark(__(X, __(Y, Z)))
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(6)
4.61/1.93	Obligation:
4.61/1.93	Q restricted rewrite system:
4.61/1.93	The TRS R consists of the following rules:
4.61/1.93	
4.61/1.93	   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
4.61/1.93	   mark(nil) -> active(nil)
4.61/1.93	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
4.61/1.93	   mark(tt) -> active(tt)
4.61/1.93	   mark(isNePal(X)) -> active(isNePal(mark(X)))
4.61/1.93	   __(mark(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, mark(X2)) -> __(X1, X2)
4.61/1.93	   __(active(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, active(X2)) -> __(X1, X2)
4.61/1.93	   and(mark(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, mark(X2)) -> and(X1, X2)
4.61/1.93	   and(active(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, active(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(mark(X)) -> isNePal(X)
4.61/1.93	   isNePal(active(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	The set Q consists of the following terms:
4.61/1.93	
4.61/1.93	   active(__(__(x0, x1), x2))
4.61/1.93	   active(__(x0, nil))
4.61/1.93	   active(__(nil, x0))
4.61/1.93	   active(and(tt, x0))
4.61/1.93	   active(isNePal(__(x0, __(x1, x0))))
4.61/1.93	   mark(__(x0, x1))
4.61/1.93	   mark(nil)
4.61/1.93	   mark(and(x0, x1))
4.61/1.93	   mark(tt)
4.61/1.93	   mark(isNePal(x0))
4.61/1.93	   __(mark(x0), x1)
4.61/1.93	   __(x0, mark(x1))
4.61/1.93	   __(active(x0), x1)
4.61/1.93	   __(x0, active(x1))
4.61/1.93	   and(mark(x0), x1)
4.61/1.93	   and(x0, mark(x1))
4.61/1.93	   and(active(x0), x1)
4.61/1.93	   and(x0, active(x1))
4.61/1.93	   isNePal(mark(x0))
4.61/1.93	   isNePal(active(x0))
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(7) QTRSRRRProof (EQUIVALENT)
4.61/1.93	Used ordering:
4.61/1.93	Polynomial interpretation [POLO]:
4.61/1.93	
4.61/1.93	   POL(__(x_1, x_2)) = 2 + x_1 + 2*x_2
4.61/1.93	   POL(active(x_1)) = 2 + x_1
4.61/1.93	   POL(and(x_1, x_2)) = 2 + 2*x_1 + x_2
4.61/1.93	   POL(isNePal(x_1)) = 2 + 2*x_1
4.61/1.93	   POL(mark(x_1)) = 2*x_1
4.61/1.93	   POL(nil) = 2
4.61/1.93	   POL(tt) = 2
4.61/1.93	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.61/1.93	
4.61/1.93	   __(active(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, active(X2)) -> __(X1, X2)
4.61/1.93	   and(active(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, active(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(active(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(8)
4.61/1.93	Obligation:
4.61/1.93	Q restricted rewrite system:
4.61/1.93	The TRS R consists of the following rules:
4.61/1.93	
4.61/1.93	   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
4.61/1.93	   mark(nil) -> active(nil)
4.61/1.93	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
4.61/1.93	   mark(tt) -> active(tt)
4.61/1.93	   mark(isNePal(X)) -> active(isNePal(mark(X)))
4.61/1.93	   __(mark(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, mark(X2)) -> __(X1, X2)
4.61/1.93	   and(mark(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, mark(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(mark(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	The set Q consists of the following terms:
4.61/1.93	
4.61/1.93	   active(__(__(x0, x1), x2))
4.61/1.93	   active(__(x0, nil))
4.61/1.93	   active(__(nil, x0))
4.61/1.93	   active(and(tt, x0))
4.61/1.93	   active(isNePal(__(x0, __(x1, x0))))
4.61/1.93	   mark(__(x0, x1))
4.61/1.93	   mark(nil)
4.61/1.93	   mark(and(x0, x1))
4.61/1.93	   mark(tt)
4.61/1.93	   mark(isNePal(x0))
4.61/1.93	   __(mark(x0), x1)
4.61/1.93	   __(x0, mark(x1))
4.61/1.93	   __(active(x0), x1)
4.61/1.93	   __(x0, active(x1))
4.61/1.93	   and(mark(x0), x1)
4.61/1.93	   and(x0, mark(x1))
4.61/1.93	   and(active(x0), x1)
4.61/1.93	   and(x0, active(x1))
4.61/1.93	   isNePal(mark(x0))
4.61/1.93	   isNePal(active(x0))
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(9) QTRSRRRProof (EQUIVALENT)
4.61/1.93	Used ordering:
4.61/1.93	Polynomial interpretation [POLO]:
4.61/1.93	
4.61/1.93	   POL(__(x_1, x_2)) = 2 + x_1 + x_2
4.61/1.93	   POL(active(x_1)) = x_1
4.61/1.93	   POL(and(x_1, x_2)) = 1 + x_1 + x_2
4.61/1.93	   POL(isNePal(x_1)) = 1 + x_1
4.61/1.93	   POL(mark(x_1)) = 1 + 2*x_1
4.61/1.93	   POL(nil) = 2
4.61/1.93	   POL(tt) = 2
4.61/1.93	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
4.61/1.93	
4.61/1.93	   mark(__(X1, X2)) -> active(__(mark(X1), mark(X2)))
4.61/1.93	   mark(nil) -> active(nil)
4.61/1.93	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
4.61/1.93	   mark(tt) -> active(tt)
4.61/1.93	   mark(isNePal(X)) -> active(isNePal(mark(X)))
4.61/1.93	   __(mark(X1), X2) -> __(X1, X2)
4.61/1.93	   __(X1, mark(X2)) -> __(X1, X2)
4.61/1.93	   and(mark(X1), X2) -> and(X1, X2)
4.61/1.93	   and(X1, mark(X2)) -> and(X1, X2)
4.61/1.93	   isNePal(mark(X)) -> isNePal(X)
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(10)
4.61/1.93	Obligation:
4.61/1.93	Q restricted rewrite system:
4.61/1.93	R is empty.
4.61/1.93	The set Q consists of the following terms:
4.61/1.93	
4.61/1.93	   active(__(__(x0, x1), x2))
4.61/1.93	   active(__(x0, nil))
4.61/1.93	   active(__(nil, x0))
4.61/1.93	   active(and(tt, x0))
4.61/1.93	   active(isNePal(__(x0, __(x1, x0))))
4.61/1.93	   mark(__(x0, x1))
4.61/1.93	   mark(nil)
4.61/1.93	   mark(and(x0, x1))
4.61/1.93	   mark(tt)
4.61/1.93	   mark(isNePal(x0))
4.61/1.93	   __(mark(x0), x1)
4.61/1.93	   __(x0, mark(x1))
4.61/1.93	   __(active(x0), x1)
4.61/1.93	   __(x0, active(x1))
4.61/1.93	   and(mark(x0), x1)
4.61/1.93	   and(x0, mark(x1))
4.61/1.93	   and(active(x0), x1)
4.61/1.93	   and(x0, active(x1))
4.61/1.93	   isNePal(mark(x0))
4.61/1.93	   isNePal(active(x0))
4.61/1.93	
4.61/1.93	
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(11) RisEmptyProof (EQUIVALENT)
4.61/1.93	The TRS R is empty. Hence, termination is trivially proven.
4.61/1.93	----------------------------------------
4.61/1.93	
4.61/1.93	(12)
4.61/1.93	YES
4.61/1.96	EOF