6.72/2.52	YES
6.72/2.54	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.72/2.54	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.72/2.54	
6.72/2.54	
6.72/2.54	Termination w.r.t. Q of the given QTRS could be proven:
6.72/2.54	
6.72/2.54	(0) QTRS
6.72/2.54	(1) QTRSRRRProof [EQUIVALENT, 393 ms]
6.72/2.54	(2) QTRS
6.72/2.54	(3) QTRSRRRProof [EQUIVALENT, 52 ms]
6.72/2.54	(4) QTRS
6.72/2.54	(5) QTRSRRRProof [EQUIVALENT, 52 ms]
6.72/2.54	(6) QTRS
6.72/2.54	(7) QTRSRRRProof [EQUIVALENT, 33 ms]
6.72/2.54	(8) QTRS
6.72/2.54	(9) QTRSRRRProof [EQUIVALENT, 0 ms]
6.72/2.54	(10) QTRS
6.72/2.54	(11) RisEmptyProof [EQUIVALENT, 0 ms]
6.72/2.54	(12) YES
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(0)
6.72/2.54	Obligation:
6.72/2.54	Q restricted rewrite system:
6.72/2.54	The TRS R consists of the following rules:
6.72/2.54	
6.72/2.54	   active(U11(tt, N)) -> mark(N)
6.72/2.54	   active(U21(tt, M, N)) -> mark(s(plus(N, M)))
6.72/2.54	   active(U31(tt)) -> mark(0)
6.72/2.54	   active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
6.72/2.54	   active(and(tt, X)) -> mark(X)
6.72/2.54	   active(isNat(0)) -> mark(tt)
6.72/2.54	   active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.72/2.54	   active(isNat(s(V1))) -> mark(isNat(V1))
6.72/2.54	   active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.72/2.54	   active(plus(N, 0)) -> mark(U11(isNat(N), N))
6.72/2.54	   active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
6.72/2.54	   active(x(N, 0)) -> mark(U31(isNat(N)))
6.72/2.54	   active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
6.72/2.54	   mark(U11(X1, X2)) -> active(U11(mark(X1), X2))
6.72/2.54	   mark(tt) -> active(tt)
6.72/2.54	   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
6.72/2.54	   mark(s(X)) -> active(s(mark(X)))
6.72/2.54	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.72/2.54	   mark(U31(X)) -> active(U31(mark(X)))
6.72/2.54	   mark(0) -> active(0)
6.72/2.54	   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
6.72/2.54	   mark(x(X1, X2)) -> active(x(mark(X1), mark(X2)))
6.72/2.54	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.72/2.54	   mark(isNat(X)) -> active(isNat(X))
6.72/2.54	   U11(mark(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, mark(X2)) -> U11(X1, X2)
6.72/2.54	   U11(active(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, active(X2)) -> U11(X1, X2)
6.72/2.54	   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
6.72/2.54	   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(mark(X)) -> s(X)
6.72/2.54	   s(active(X)) -> s(X)
6.72/2.54	   plus(mark(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, mark(X2)) -> plus(X1, X2)
6.72/2.54	   plus(active(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, active(X2)) -> plus(X1, X2)
6.72/2.54	   U31(mark(X)) -> U31(X)
6.72/2.54	   U31(active(X)) -> U31(X)
6.72/2.54	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.72/2.54	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(mark(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, mark(X2)) -> x(X1, X2)
6.72/2.54	   x(active(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, active(X2)) -> x(X1, X2)
6.72/2.54	   and(mark(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, mark(X2)) -> and(X1, X2)
6.72/2.54	   and(active(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, active(X2)) -> and(X1, X2)
6.72/2.54	   isNat(mark(X)) -> isNat(X)
6.72/2.54	   isNat(active(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	The set Q consists of the following terms:
6.72/2.54	
6.72/2.54	   active(U11(tt, x0))
6.72/2.54	   active(U21(tt, x0, x1))
6.72/2.54	   active(U31(tt))
6.72/2.54	   active(U41(tt, x0, x1))
6.72/2.54	   active(and(tt, x0))
6.72/2.54	   active(isNat(0))
6.72/2.54	   active(isNat(plus(x0, x1)))
6.72/2.54	   active(isNat(s(x0)))
6.72/2.54	   active(isNat(x(x0, x1)))
6.72/2.54	   active(plus(x0, 0))
6.72/2.54	   active(plus(x0, s(x1)))
6.72/2.54	   active(x(x0, 0))
6.72/2.54	   active(x(x0, s(x1)))
6.72/2.54	   mark(U11(x0, x1))
6.72/2.54	   mark(tt)
6.72/2.54	   mark(U21(x0, x1, x2))
6.72/2.54	   mark(s(x0))
6.72/2.54	   mark(plus(x0, x1))
6.72/2.54	   mark(U31(x0))
6.72/2.54	   mark(0)
6.72/2.54	   mark(U41(x0, x1, x2))
6.72/2.54	   mark(x(x0, x1))
6.72/2.54	   mark(and(x0, x1))
6.72/2.54	   mark(isNat(x0))
6.72/2.54	   U11(mark(x0), x1)
6.72/2.54	   U11(x0, mark(x1))
6.72/2.54	   U11(active(x0), x1)
6.72/2.54	   U11(x0, active(x1))
6.72/2.54	   U21(mark(x0), x1, x2)
6.72/2.54	   U21(x0, mark(x1), x2)
6.72/2.54	   U21(x0, x1, mark(x2))
6.72/2.54	   U21(active(x0), x1, x2)
6.72/2.54	   U21(x0, active(x1), x2)
6.72/2.54	   U21(x0, x1, active(x2))
6.72/2.54	   s(mark(x0))
6.72/2.54	   s(active(x0))
6.72/2.54	   plus(mark(x0), x1)
6.72/2.54	   plus(x0, mark(x1))
6.72/2.54	   plus(active(x0), x1)
6.72/2.54	   plus(x0, active(x1))
6.72/2.54	   U31(mark(x0))
6.72/2.54	   U31(active(x0))
6.72/2.54	   U41(mark(x0), x1, x2)
6.72/2.54	   U41(x0, mark(x1), x2)
6.72/2.54	   U41(x0, x1, mark(x2))
6.72/2.54	   U41(active(x0), x1, x2)
6.72/2.54	   U41(x0, active(x1), x2)
6.72/2.54	   U41(x0, x1, active(x2))
6.72/2.54	   x(mark(x0), x1)
6.72/2.54	   x(x0, mark(x1))
6.72/2.54	   x(active(x0), x1)
6.72/2.54	   x(x0, active(x1))
6.72/2.54	   and(mark(x0), x1)
6.72/2.54	   and(x0, mark(x1))
6.72/2.54	   and(active(x0), x1)
6.72/2.54	   and(x0, active(x1))
6.72/2.54	   isNat(mark(x0))
6.72/2.54	   isNat(active(x0))
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(1) QTRSRRRProof (EQUIVALENT)
6.72/2.54	Used ordering:
6.72/2.54	active/1)YES(
6.72/2.54	U11/2(YES,YES)
6.72/2.54	tt/0)
6.72/2.54	mark/1)YES(
6.72/2.54	U21/3(YES,YES,YES)
6.72/2.54	s/1(YES)
6.72/2.54	plus/2(YES,YES)
6.72/2.54	U31/1(YES)
6.72/2.54	0/0)
6.72/2.54	U41/3(YES,YES,YES)
6.72/2.54	x/2(YES,YES)
6.72/2.54	and/2(YES,YES)
6.72/2.54	isNat/1)YES(
6.72/2.54	
6.72/2.54	Quasi precedence:
6.72/2.54	[U41_3, x_2] > [U21_3, plus_2] > U11_2
6.72/2.54	[U41_3, x_2] > [U21_3, plus_2] > s_1 > and_2
6.72/2.54	[U41_3, x_2] > U31_1 > 0 > U11_2
6.72/2.54	[U41_3, x_2] > U31_1 > 0 > tt
6.72/2.54	
6.72/2.54	
6.72/2.54	Status:
6.72/2.54	U11_2: multiset status
6.72/2.54	tt: multiset status
6.72/2.54	U21_3: [3,2,1]
6.72/2.54	s_1: multiset status
6.72/2.54	plus_2: [1,2]
6.72/2.54	U31_1: multiset status
6.72/2.54	0: multiset status
6.72/2.54	U41_3: [2,3,1]
6.72/2.54	x_2: [2,1]
6.72/2.54	and_2: multiset status
6.72/2.54	
6.72/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.72/2.54	
6.72/2.54	   active(U11(tt, N)) -> mark(N)
6.72/2.54	   active(U21(tt, M, N)) -> mark(s(plus(N, M)))
6.72/2.54	   active(U31(tt)) -> mark(0)
6.72/2.54	   active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
6.72/2.54	   active(and(tt, X)) -> mark(X)
6.72/2.54	   active(isNat(0)) -> mark(tt)
6.72/2.54	   active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.72/2.54	   active(isNat(s(V1))) -> mark(isNat(V1))
6.72/2.54	   active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.72/2.54	   active(plus(N, 0)) -> mark(U11(isNat(N), N))
6.72/2.54	   active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
6.72/2.54	   active(x(N, 0)) -> mark(U31(isNat(N)))
6.72/2.54	   active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(2)
6.72/2.54	Obligation:
6.72/2.54	Q restricted rewrite system:
6.72/2.54	The TRS R consists of the following rules:
6.72/2.54	
6.72/2.54	   mark(U11(X1, X2)) -> active(U11(mark(X1), X2))
6.72/2.54	   mark(tt) -> active(tt)
6.72/2.54	   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
6.72/2.54	   mark(s(X)) -> active(s(mark(X)))
6.72/2.54	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.72/2.54	   mark(U31(X)) -> active(U31(mark(X)))
6.72/2.54	   mark(0) -> active(0)
6.72/2.54	   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
6.72/2.54	   mark(x(X1, X2)) -> active(x(mark(X1), mark(X2)))
6.72/2.54	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.72/2.54	   mark(isNat(X)) -> active(isNat(X))
6.72/2.54	   U11(mark(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, mark(X2)) -> U11(X1, X2)
6.72/2.54	   U11(active(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, active(X2)) -> U11(X1, X2)
6.72/2.54	   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
6.72/2.54	   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(mark(X)) -> s(X)
6.72/2.54	   s(active(X)) -> s(X)
6.72/2.54	   plus(mark(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, mark(X2)) -> plus(X1, X2)
6.72/2.54	   plus(active(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, active(X2)) -> plus(X1, X2)
6.72/2.54	   U31(mark(X)) -> U31(X)
6.72/2.54	   U31(active(X)) -> U31(X)
6.72/2.54	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.72/2.54	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(mark(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, mark(X2)) -> x(X1, X2)
6.72/2.54	   x(active(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, active(X2)) -> x(X1, X2)
6.72/2.54	   and(mark(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, mark(X2)) -> and(X1, X2)
6.72/2.54	   and(active(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, active(X2)) -> and(X1, X2)
6.72/2.54	   isNat(mark(X)) -> isNat(X)
6.72/2.54	   isNat(active(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	The set Q consists of the following terms:
6.72/2.54	
6.72/2.54	   active(U11(tt, x0))
6.72/2.54	   active(U21(tt, x0, x1))
6.72/2.54	   active(U31(tt))
6.72/2.54	   active(U41(tt, x0, x1))
6.72/2.54	   active(and(tt, x0))
6.72/2.54	   active(isNat(0))
6.72/2.54	   active(isNat(plus(x0, x1)))
6.72/2.54	   active(isNat(s(x0)))
6.72/2.54	   active(isNat(x(x0, x1)))
6.72/2.54	   active(plus(x0, 0))
6.72/2.54	   active(plus(x0, s(x1)))
6.72/2.54	   active(x(x0, 0))
6.72/2.54	   active(x(x0, s(x1)))
6.72/2.54	   mark(U11(x0, x1))
6.72/2.54	   mark(tt)
6.72/2.54	   mark(U21(x0, x1, x2))
6.72/2.54	   mark(s(x0))
6.72/2.54	   mark(plus(x0, x1))
6.72/2.54	   mark(U31(x0))
6.72/2.54	   mark(0)
6.72/2.54	   mark(U41(x0, x1, x2))
6.72/2.54	   mark(x(x0, x1))
6.72/2.54	   mark(and(x0, x1))
6.72/2.54	   mark(isNat(x0))
6.72/2.54	   U11(mark(x0), x1)
6.72/2.54	   U11(x0, mark(x1))
6.72/2.54	   U11(active(x0), x1)
6.72/2.54	   U11(x0, active(x1))
6.72/2.54	   U21(mark(x0), x1, x2)
6.72/2.54	   U21(x0, mark(x1), x2)
6.72/2.54	   U21(x0, x1, mark(x2))
6.72/2.54	   U21(active(x0), x1, x2)
6.72/2.54	   U21(x0, active(x1), x2)
6.72/2.54	   U21(x0, x1, active(x2))
6.72/2.54	   s(mark(x0))
6.72/2.54	   s(active(x0))
6.72/2.54	   plus(mark(x0), x1)
6.72/2.54	   plus(x0, mark(x1))
6.72/2.54	   plus(active(x0), x1)
6.72/2.54	   plus(x0, active(x1))
6.72/2.54	   U31(mark(x0))
6.72/2.54	   U31(active(x0))
6.72/2.54	   U41(mark(x0), x1, x2)
6.72/2.54	   U41(x0, mark(x1), x2)
6.72/2.54	   U41(x0, x1, mark(x2))
6.72/2.54	   U41(active(x0), x1, x2)
6.72/2.54	   U41(x0, active(x1), x2)
6.72/2.54	   U41(x0, x1, active(x2))
6.72/2.54	   x(mark(x0), x1)
6.72/2.54	   x(x0, mark(x1))
6.72/2.54	   x(active(x0), x1)
6.72/2.54	   x(x0, active(x1))
6.72/2.54	   and(mark(x0), x1)
6.72/2.54	   and(x0, mark(x1))
6.72/2.54	   and(active(x0), x1)
6.72/2.54	   and(x0, active(x1))
6.72/2.54	   isNat(mark(x0))
6.72/2.54	   isNat(active(x0))
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(3) QTRSRRRProof (EQUIVALENT)
6.72/2.54	Used ordering:
6.72/2.54	Polynomial interpretation [POLO]:
6.72/2.54	
6.72/2.54	   POL(0) = 1
6.72/2.54	   POL(U11(x_1, x_2)) = 1 + x_1 + x_2
6.72/2.54	   POL(U21(x_1, x_2, x_3)) = x_1 + x_2 + 2*x_3
6.72/2.54	   POL(U31(x_1)) = x_1
6.72/2.54	   POL(U41(x_1, x_2, x_3)) = 1 + x_1 + x_2 + 2*x_3
6.72/2.54	   POL(active(x_1)) = x_1
6.72/2.54	   POL(and(x_1, x_2)) = x_1 + x_2
6.72/2.54	   POL(isNat(x_1)) = 2 + x_1
6.72/2.54	   POL(mark(x_1)) = 1 + 2*x_1
6.72/2.54	   POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_2
6.72/2.54	   POL(s(x_1)) = x_1
6.72/2.54	   POL(tt) = 2
6.72/2.54	   POL(x(x_1, x_2)) = 2 + 2*x_1 + x_2
6.72/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.72/2.54	
6.72/2.54	   mark(U11(X1, X2)) -> active(U11(mark(X1), X2))
6.72/2.54	   mark(tt) -> active(tt)
6.72/2.54	   mark(0) -> active(0)
6.72/2.54	   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
6.72/2.54	   mark(isNat(X)) -> active(isNat(X))
6.72/2.54	   U11(mark(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, mark(X2)) -> U11(X1, X2)
6.72/2.54	   U21(mark(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, mark(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, mark(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(mark(X)) -> s(X)
6.72/2.54	   plus(mark(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, mark(X2)) -> plus(X1, X2)
6.72/2.54	   U31(mark(X)) -> U31(X)
6.72/2.54	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(mark(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, mark(X2)) -> x(X1, X2)
6.72/2.54	   and(mark(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, mark(X2)) -> and(X1, X2)
6.72/2.54	   isNat(mark(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(4)
6.72/2.54	Obligation:
6.72/2.54	Q restricted rewrite system:
6.72/2.54	The TRS R consists of the following rules:
6.72/2.54	
6.72/2.54	   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
6.72/2.54	   mark(s(X)) -> active(s(mark(X)))
6.72/2.54	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.72/2.54	   mark(U31(X)) -> active(U31(mark(X)))
6.72/2.54	   mark(x(X1, X2)) -> active(x(mark(X1), mark(X2)))
6.72/2.54	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.72/2.54	   U11(active(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, active(X2)) -> U11(X1, X2)
6.72/2.54	   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(active(X)) -> s(X)
6.72/2.54	   plus(active(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, active(X2)) -> plus(X1, X2)
6.72/2.54	   U31(active(X)) -> U31(X)
6.72/2.54	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(active(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, active(X2)) -> x(X1, X2)
6.72/2.54	   and(active(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, active(X2)) -> and(X1, X2)
6.72/2.54	   isNat(active(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	The set Q consists of the following terms:
6.72/2.54	
6.72/2.54	   active(U11(tt, x0))
6.72/2.54	   active(U21(tt, x0, x1))
6.72/2.54	   active(U31(tt))
6.72/2.54	   active(U41(tt, x0, x1))
6.72/2.54	   active(and(tt, x0))
6.72/2.54	   active(isNat(0))
6.72/2.54	   active(isNat(plus(x0, x1)))
6.72/2.54	   active(isNat(s(x0)))
6.72/2.54	   active(isNat(x(x0, x1)))
6.72/2.54	   active(plus(x0, 0))
6.72/2.54	   active(plus(x0, s(x1)))
6.72/2.54	   active(x(x0, 0))
6.72/2.54	   active(x(x0, s(x1)))
6.72/2.54	   mark(U11(x0, x1))
6.72/2.54	   mark(tt)
6.72/2.54	   mark(U21(x0, x1, x2))
6.72/2.54	   mark(s(x0))
6.72/2.54	   mark(plus(x0, x1))
6.72/2.54	   mark(U31(x0))
6.72/2.54	   mark(0)
6.72/2.54	   mark(U41(x0, x1, x2))
6.72/2.54	   mark(x(x0, x1))
6.72/2.54	   mark(and(x0, x1))
6.72/2.54	   mark(isNat(x0))
6.72/2.54	   U11(mark(x0), x1)
6.72/2.54	   U11(x0, mark(x1))
6.72/2.54	   U11(active(x0), x1)
6.72/2.54	   U11(x0, active(x1))
6.72/2.54	   U21(mark(x0), x1, x2)
6.72/2.54	   U21(x0, mark(x1), x2)
6.72/2.54	   U21(x0, x1, mark(x2))
6.72/2.54	   U21(active(x0), x1, x2)
6.72/2.54	   U21(x0, active(x1), x2)
6.72/2.54	   U21(x0, x1, active(x2))
6.72/2.54	   s(mark(x0))
6.72/2.54	   s(active(x0))
6.72/2.54	   plus(mark(x0), x1)
6.72/2.54	   plus(x0, mark(x1))
6.72/2.54	   plus(active(x0), x1)
6.72/2.54	   plus(x0, active(x1))
6.72/2.54	   U31(mark(x0))
6.72/2.54	   U31(active(x0))
6.72/2.54	   U41(mark(x0), x1, x2)
6.72/2.54	   U41(x0, mark(x1), x2)
6.72/2.54	   U41(x0, x1, mark(x2))
6.72/2.54	   U41(active(x0), x1, x2)
6.72/2.54	   U41(x0, active(x1), x2)
6.72/2.54	   U41(x0, x1, active(x2))
6.72/2.54	   x(mark(x0), x1)
6.72/2.54	   x(x0, mark(x1))
6.72/2.54	   x(active(x0), x1)
6.72/2.54	   x(x0, active(x1))
6.72/2.54	   and(mark(x0), x1)
6.72/2.54	   and(x0, mark(x1))
6.72/2.54	   and(active(x0), x1)
6.72/2.54	   and(x0, active(x1))
6.72/2.54	   isNat(mark(x0))
6.72/2.54	   isNat(active(x0))
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(5) QTRSRRRProof (EQUIVALENT)
6.72/2.54	Used ordering:
6.72/2.54	Polynomial interpretation [POLO]:
6.72/2.54	
6.72/2.54	   POL(U11(x_1, x_2)) = 2*x_1 + 2*x_2
6.72/2.54	   POL(U21(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + x_3
6.72/2.54	   POL(U31(x_1)) = x_1
6.72/2.54	   POL(U41(x_1, x_2, x_3)) = x_1 + 2*x_2 + 2*x_3
6.72/2.54	   POL(active(x_1)) = x_1
6.72/2.54	   POL(and(x_1, x_2)) = 1 + x_1 + x_2
6.72/2.54	   POL(isNat(x_1)) = 2*x_1
6.72/2.54	   POL(mark(x_1)) = 2 + 2*x_1
6.72/2.54	   POL(plus(x_1, x_2)) = 2 + x_1 + x_2
6.72/2.54	   POL(s(x_1)) = 2 + x_1
6.72/2.54	   POL(x(x_1, x_2)) = 2 + x_1 + x_2
6.72/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.72/2.54	
6.72/2.54	   mark(s(X)) -> active(s(mark(X)))
6.72/2.54	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(6)
6.72/2.54	Obligation:
6.72/2.54	Q restricted rewrite system:
6.72/2.54	The TRS R consists of the following rules:
6.72/2.54	
6.72/2.54	   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
6.72/2.54	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.72/2.54	   mark(U31(X)) -> active(U31(mark(X)))
6.72/2.54	   mark(x(X1, X2)) -> active(x(mark(X1), mark(X2)))
6.72/2.54	   U11(active(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, active(X2)) -> U11(X1, X2)
6.72/2.54	   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(active(X)) -> s(X)
6.72/2.54	   plus(active(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, active(X2)) -> plus(X1, X2)
6.72/2.54	   U31(active(X)) -> U31(X)
6.72/2.54	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(active(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, active(X2)) -> x(X1, X2)
6.72/2.54	   and(active(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, active(X2)) -> and(X1, X2)
6.72/2.54	   isNat(active(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	The set Q consists of the following terms:
6.72/2.54	
6.72/2.54	   active(U11(tt, x0))
6.72/2.54	   active(U21(tt, x0, x1))
6.72/2.54	   active(U31(tt))
6.72/2.54	   active(U41(tt, x0, x1))
6.72/2.54	   active(and(tt, x0))
6.72/2.54	   active(isNat(0))
6.72/2.54	   active(isNat(plus(x0, x1)))
6.72/2.54	   active(isNat(s(x0)))
6.72/2.54	   active(isNat(x(x0, x1)))
6.72/2.54	   active(plus(x0, 0))
6.72/2.54	   active(plus(x0, s(x1)))
6.72/2.54	   active(x(x0, 0))
6.72/2.54	   active(x(x0, s(x1)))
6.72/2.54	   mark(U11(x0, x1))
6.72/2.54	   mark(tt)
6.72/2.54	   mark(U21(x0, x1, x2))
6.72/2.54	   mark(s(x0))
6.72/2.54	   mark(plus(x0, x1))
6.72/2.54	   mark(U31(x0))
6.72/2.54	   mark(0)
6.72/2.54	   mark(U41(x0, x1, x2))
6.72/2.54	   mark(x(x0, x1))
6.72/2.54	   mark(and(x0, x1))
6.72/2.54	   mark(isNat(x0))
6.72/2.54	   U11(mark(x0), x1)
6.72/2.54	   U11(x0, mark(x1))
6.72/2.54	   U11(active(x0), x1)
6.72/2.54	   U11(x0, active(x1))
6.72/2.54	   U21(mark(x0), x1, x2)
6.72/2.54	   U21(x0, mark(x1), x2)
6.72/2.54	   U21(x0, x1, mark(x2))
6.72/2.54	   U21(active(x0), x1, x2)
6.72/2.54	   U21(x0, active(x1), x2)
6.72/2.54	   U21(x0, x1, active(x2))
6.72/2.54	   s(mark(x0))
6.72/2.54	   s(active(x0))
6.72/2.54	   plus(mark(x0), x1)
6.72/2.54	   plus(x0, mark(x1))
6.72/2.54	   plus(active(x0), x1)
6.72/2.54	   plus(x0, active(x1))
6.72/2.54	   U31(mark(x0))
6.72/2.54	   U31(active(x0))
6.72/2.54	   U41(mark(x0), x1, x2)
6.72/2.54	   U41(x0, mark(x1), x2)
6.72/2.54	   U41(x0, x1, mark(x2))
6.72/2.54	   U41(active(x0), x1, x2)
6.72/2.54	   U41(x0, active(x1), x2)
6.72/2.54	   U41(x0, x1, active(x2))
6.72/2.54	   x(mark(x0), x1)
6.72/2.54	   x(x0, mark(x1))
6.72/2.54	   x(active(x0), x1)
6.72/2.54	   x(x0, active(x1))
6.72/2.54	   and(mark(x0), x1)
6.72/2.54	   and(x0, mark(x1))
6.72/2.54	   and(active(x0), x1)
6.72/2.54	   and(x0, active(x1))
6.72/2.54	   isNat(mark(x0))
6.72/2.54	   isNat(active(x0))
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(7) QTRSRRRProof (EQUIVALENT)
6.72/2.54	Used ordering:
6.72/2.54	Polynomial interpretation [POLO]:
6.72/2.54	
6.72/2.54	   POL(U11(x_1, x_2)) = x_1 + x_2
6.72/2.54	   POL(U21(x_1, x_2, x_3)) = 1 + x_1 + x_2 + x_3
6.72/2.54	   POL(U31(x_1)) = 1 + x_1
6.72/2.54	   POL(U41(x_1, x_2, x_3)) = 2*x_1 + 2*x_2 + 2*x_3
6.72/2.54	   POL(active(x_1)) = x_1
6.72/2.54	   POL(and(x_1, x_2)) = x_1 + x_2
6.72/2.54	   POL(isNat(x_1)) = 2*x_1
6.72/2.54	   POL(mark(x_1)) = 1 + 2*x_1
6.72/2.54	   POL(plus(x_1, x_2)) = 2 + x_1 + x_2
6.72/2.54	   POL(s(x_1)) = 2*x_1
6.72/2.54	   POL(x(x_1, x_2)) = 2 + x_1 + x_2
6.72/2.54	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.72/2.54	
6.72/2.54	   mark(U21(X1, X2, X3)) -> active(U21(mark(X1), X2, X3))
6.72/2.54	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.72/2.54	   mark(U31(X)) -> active(U31(mark(X)))
6.72/2.54	   mark(x(X1, X2)) -> active(x(mark(X1), mark(X2)))
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(8)
6.72/2.54	Obligation:
6.72/2.54	Q restricted rewrite system:
6.72/2.54	The TRS R consists of the following rules:
6.72/2.54	
6.72/2.54	   U11(active(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, active(X2)) -> U11(X1, X2)
6.72/2.54	   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(active(X)) -> s(X)
6.72/2.54	   plus(active(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, active(X2)) -> plus(X1, X2)
6.72/2.54	   U31(active(X)) -> U31(X)
6.72/2.54	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(active(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, active(X2)) -> x(X1, X2)
6.72/2.54	   and(active(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, active(X2)) -> and(X1, X2)
6.72/2.54	   isNat(active(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	The set Q consists of the following terms:
6.72/2.54	
6.72/2.54	   active(U11(tt, x0))
6.72/2.54	   active(U21(tt, x0, x1))
6.72/2.54	   active(U31(tt))
6.72/2.54	   active(U41(tt, x0, x1))
6.72/2.54	   active(and(tt, x0))
6.72/2.54	   active(isNat(0))
6.72/2.54	   active(isNat(plus(x0, x1)))
6.72/2.54	   active(isNat(s(x0)))
6.72/2.54	   active(isNat(x(x0, x1)))
6.72/2.54	   active(plus(x0, 0))
6.72/2.54	   active(plus(x0, s(x1)))
6.72/2.54	   active(x(x0, 0))
6.72/2.54	   active(x(x0, s(x1)))
6.72/2.54	   mark(U11(x0, x1))
6.72/2.54	   mark(tt)
6.72/2.54	   mark(U21(x0, x1, x2))
6.72/2.54	   mark(s(x0))
6.72/2.54	   mark(plus(x0, x1))
6.72/2.54	   mark(U31(x0))
6.72/2.54	   mark(0)
6.72/2.54	   mark(U41(x0, x1, x2))
6.72/2.54	   mark(x(x0, x1))
6.72/2.54	   mark(and(x0, x1))
6.72/2.54	   mark(isNat(x0))
6.72/2.54	   U11(mark(x0), x1)
6.72/2.54	   U11(x0, mark(x1))
6.72/2.54	   U11(active(x0), x1)
6.72/2.54	   U11(x0, active(x1))
6.72/2.54	   U21(mark(x0), x1, x2)
6.72/2.54	   U21(x0, mark(x1), x2)
6.72/2.54	   U21(x0, x1, mark(x2))
6.72/2.54	   U21(active(x0), x1, x2)
6.72/2.54	   U21(x0, active(x1), x2)
6.72/2.54	   U21(x0, x1, active(x2))
6.72/2.54	   s(mark(x0))
6.72/2.54	   s(active(x0))
6.72/2.54	   plus(mark(x0), x1)
6.72/2.54	   plus(x0, mark(x1))
6.72/2.54	   plus(active(x0), x1)
6.72/2.54	   plus(x0, active(x1))
6.72/2.54	   U31(mark(x0))
6.72/2.54	   U31(active(x0))
6.72/2.54	   U41(mark(x0), x1, x2)
6.72/2.54	   U41(x0, mark(x1), x2)
6.72/2.54	   U41(x0, x1, mark(x2))
6.72/2.54	   U41(active(x0), x1, x2)
6.72/2.54	   U41(x0, active(x1), x2)
6.72/2.54	   U41(x0, x1, active(x2))
6.72/2.54	   x(mark(x0), x1)
6.72/2.54	   x(x0, mark(x1))
6.72/2.54	   x(active(x0), x1)
6.72/2.54	   x(x0, active(x1))
6.72/2.54	   and(mark(x0), x1)
6.72/2.54	   and(x0, mark(x1))
6.72/2.54	   and(active(x0), x1)
6.72/2.54	   and(x0, active(x1))
6.72/2.54	   isNat(mark(x0))
6.72/2.54	   isNat(active(x0))
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(9) QTRSRRRProof (EQUIVALENT)
6.72/2.54	Used ordering:
6.72/2.54	Knuth-Bendix order [KBO] with precedence:active_1 > isNat_1 > and_2 > x_2 > U41_3 > U31_1 > plus_2 > s_1 > U21_3 > U11_2
6.72/2.54	
6.72/2.54	and weight map:
6.72/2.54	
6.72/2.54	   active_1=0
6.72/2.54	   s_1=1
6.72/2.54	   U31_1=1
6.72/2.54	   isNat_1=1
6.72/2.54	   U11_2=0
6.72/2.54	   U21_3=0
6.72/2.54	   plus_2=0
6.72/2.54	   U41_3=0
6.72/2.54	   x_2=0
6.72/2.54	   and_2=0
6.72/2.54	
6.72/2.54	The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.72/2.54	
6.72/2.54	   U11(active(X1), X2) -> U11(X1, X2)
6.72/2.54	   U11(X1, active(X2)) -> U11(X1, X2)
6.72/2.54	   U21(active(X1), X2, X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, active(X2), X3) -> U21(X1, X2, X3)
6.72/2.54	   U21(X1, X2, active(X3)) -> U21(X1, X2, X3)
6.72/2.54	   s(active(X)) -> s(X)
6.72/2.54	   plus(active(X1), X2) -> plus(X1, X2)
6.72/2.54	   plus(X1, active(X2)) -> plus(X1, X2)
6.72/2.54	   U31(active(X)) -> U31(X)
6.72/2.54	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.72/2.54	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.72/2.54	   x(active(X1), X2) -> x(X1, X2)
6.72/2.54	   x(X1, active(X2)) -> x(X1, X2)
6.72/2.54	   and(active(X1), X2) -> and(X1, X2)
6.72/2.54	   and(X1, active(X2)) -> and(X1, X2)
6.72/2.54	   isNat(active(X)) -> isNat(X)
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(10)
6.72/2.54	Obligation:
6.72/2.54	Q restricted rewrite system:
6.72/2.54	R is empty.
6.72/2.54	The set Q consists of the following terms:
6.72/2.54	
6.72/2.54	   active(U11(tt, x0))
6.72/2.54	   active(U21(tt, x0, x1))
6.72/2.54	   active(U31(tt))
6.72/2.54	   active(U41(tt, x0, x1))
6.72/2.54	   active(and(tt, x0))
6.72/2.54	   active(isNat(0))
6.72/2.54	   active(isNat(plus(x0, x1)))
6.72/2.54	   active(isNat(s(x0)))
6.72/2.54	   active(isNat(x(x0, x1)))
6.72/2.54	   active(plus(x0, 0))
6.72/2.54	   active(plus(x0, s(x1)))
6.72/2.54	   active(x(x0, 0))
6.72/2.54	   active(x(x0, s(x1)))
6.72/2.54	   mark(U11(x0, x1))
6.72/2.54	   mark(tt)
6.72/2.54	   mark(U21(x0, x1, x2))
6.72/2.54	   mark(s(x0))
6.72/2.54	   mark(plus(x0, x1))
6.72/2.54	   mark(U31(x0))
6.72/2.54	   mark(0)
6.72/2.54	   mark(U41(x0, x1, x2))
6.72/2.54	   mark(x(x0, x1))
6.72/2.54	   mark(and(x0, x1))
6.72/2.54	   mark(isNat(x0))
6.72/2.54	   U11(mark(x0), x1)
6.72/2.54	   U11(x0, mark(x1))
6.72/2.54	   U11(active(x0), x1)
6.72/2.54	   U11(x0, active(x1))
6.72/2.54	   U21(mark(x0), x1, x2)
6.72/2.54	   U21(x0, mark(x1), x2)
6.72/2.54	   U21(x0, x1, mark(x2))
6.72/2.54	   U21(active(x0), x1, x2)
6.72/2.54	   U21(x0, active(x1), x2)
6.72/2.54	   U21(x0, x1, active(x2))
6.72/2.54	   s(mark(x0))
6.72/2.54	   s(active(x0))
6.72/2.54	   plus(mark(x0), x1)
6.72/2.54	   plus(x0, mark(x1))
6.72/2.54	   plus(active(x0), x1)
6.72/2.54	   plus(x0, active(x1))
6.72/2.54	   U31(mark(x0))
6.72/2.54	   U31(active(x0))
6.72/2.54	   U41(mark(x0), x1, x2)
6.72/2.54	   U41(x0, mark(x1), x2)
6.72/2.54	   U41(x0, x1, mark(x2))
6.72/2.54	   U41(active(x0), x1, x2)
6.72/2.54	   U41(x0, active(x1), x2)
6.72/2.54	   U41(x0, x1, active(x2))
6.72/2.54	   x(mark(x0), x1)
6.72/2.54	   x(x0, mark(x1))
6.72/2.54	   x(active(x0), x1)
6.72/2.54	   x(x0, active(x1))
6.72/2.54	   and(mark(x0), x1)
6.72/2.54	   and(x0, mark(x1))
6.72/2.54	   and(active(x0), x1)
6.72/2.54	   and(x0, active(x1))
6.72/2.54	   isNat(mark(x0))
6.72/2.54	   isNat(active(x0))
6.72/2.54	
6.72/2.54	
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(11) RisEmptyProof (EQUIVALENT)
6.72/2.54	The TRS R is empty. Hence, termination is trivially proven.
6.72/2.54	----------------------------------------
6.72/2.54	
6.72/2.54	(12)
6.72/2.54	YES
6.91/2.62	EOF