6.17/2.55	YES
6.17/2.55	proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
6.17/2.55	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.17/2.55	
6.17/2.55	
6.17/2.55	Termination w.r.t. Q of the given QTRS could be proven:
6.17/2.55	
6.17/2.55	(0) QTRS
6.17/2.55	(1) QTRSRRRProof [EQUIVALENT, 511 ms]
6.17/2.55	(2) QTRS
6.17/2.55	(3) QTRSRRRProof [EQUIVALENT, 54 ms]
6.17/2.55	(4) QTRS
6.17/2.55	(5) QTRSRRRProof [EQUIVALENT, 2 ms]
6.17/2.55	(6) QTRS
6.17/2.55	(7) RisEmptyProof [EQUIVALENT, 0 ms]
6.17/2.55	(8) YES
6.17/2.55	
6.17/2.55	
6.17/2.55	----------------------------------------
6.17/2.55	
6.17/2.55	(0)
6.17/2.55	Obligation:
6.17/2.55	Q restricted rewrite system:
6.17/2.55	The TRS R consists of the following rules:
6.17/2.55	
6.17/2.55	   active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2))
6.17/2.55	   active(U12(tt, V2)) -> mark(U13(isNat(V2)))
6.17/2.55	   active(U13(tt)) -> mark(tt)
6.17/2.55	   active(U21(tt, V1)) -> mark(U22(isNat(V1)))
6.17/2.55	   active(U22(tt)) -> mark(tt)
6.17/2.55	   active(U31(tt, N)) -> mark(N)
6.17/2.55	   active(U41(tt, M, N)) -> mark(s(plus(N, M)))
6.17/2.55	   active(and(tt, X)) -> mark(X)
6.17/2.55	   active(isNat(0)) -> mark(tt)
6.17/2.55	   active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2))
6.17/2.55	   active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1))
6.17/2.55	   active(isNatKind(0)) -> mark(tt)
6.17/2.55	   active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2)))
6.17/2.55	   active(isNatKind(s(V1))) -> mark(isNatKind(V1))
6.17/2.55	   active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N))
6.17/2.55	   active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N))
6.17/2.55	   mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3))
6.17/2.55	   mark(tt) -> active(tt)
6.17/2.55	   mark(U12(X1, X2)) -> active(U12(mark(X1), X2))
6.17/2.55	   mark(isNat(X)) -> active(isNat(X))
6.17/2.55	   mark(U13(X)) -> active(U13(mark(X)))
6.17/2.55	   mark(U21(X1, X2)) -> active(U21(mark(X1), X2))
6.17/2.55	   mark(U22(X)) -> active(U22(mark(X)))
6.17/2.55	   mark(U31(X1, X2)) -> active(U31(mark(X1), X2))
6.17/2.55	   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
6.17/2.55	   mark(s(X)) -> active(s(mark(X)))
6.17/2.55	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.17/2.55	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.17/2.55	   mark(0) -> active(0)
6.17/2.55	   mark(isNatKind(X)) -> active(isNatKind(X))
6.17/2.55	   U11(mark(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.55	   U11(X1, mark(X2), X3) -> U11(X1, X2, X3)
6.17/2.55	   U11(X1, X2, mark(X3)) -> U11(X1, X2, X3)
6.17/2.55	   U11(active(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.55	   U11(X1, active(X2), X3) -> U11(X1, X2, X3)
6.17/2.55	   U11(X1, X2, active(X3)) -> U11(X1, X2, X3)
6.17/2.55	   U12(mark(X1), X2) -> U12(X1, X2)
6.17/2.55	   U12(X1, mark(X2)) -> U12(X1, X2)
6.17/2.55	   U12(active(X1), X2) -> U12(X1, X2)
6.17/2.55	   U12(X1, active(X2)) -> U12(X1, X2)
6.17/2.55	   isNat(mark(X)) -> isNat(X)
6.17/2.55	   isNat(active(X)) -> isNat(X)
6.17/2.55	   U13(mark(X)) -> U13(X)
6.17/2.55	   U13(active(X)) -> U13(X)
6.17/2.55	   U21(mark(X1), X2) -> U21(X1, X2)
6.17/2.55	   U21(X1, mark(X2)) -> U21(X1, X2)
6.17/2.55	   U21(active(X1), X2) -> U21(X1, X2)
6.17/2.55	   U21(X1, active(X2)) -> U21(X1, X2)
6.17/2.55	   U22(mark(X)) -> U22(X)
6.17/2.55	   U22(active(X)) -> U22(X)
6.17/2.55	   U31(mark(X1), X2) -> U31(X1, X2)
6.17/2.55	   U31(X1, mark(X2)) -> U31(X1, X2)
6.17/2.55	   U31(active(X1), X2) -> U31(X1, X2)
6.17/2.55	   U31(X1, active(X2)) -> U31(X1, X2)
6.17/2.55	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.55	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.17/2.55	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.17/2.55	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.55	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.17/2.56	   s(mark(X)) -> s(X)
6.17/2.56	   s(active(X)) -> s(X)
6.17/2.56	   plus(mark(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, mark(X2)) -> plus(X1, X2)
6.17/2.56	   plus(active(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, active(X2)) -> plus(X1, X2)
6.17/2.56	   and(mark(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, mark(X2)) -> and(X1, X2)
6.17/2.56	   and(active(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, active(X2)) -> and(X1, X2)
6.17/2.56	   isNatKind(mark(X)) -> isNatKind(X)
6.17/2.56	   isNatKind(active(X)) -> isNatKind(X)
6.17/2.56	
6.17/2.56	The set Q consists of the following terms:
6.17/2.56	
6.17/2.56	   active(U11(tt, x0, x1))
6.17/2.56	   active(U12(tt, x0))
6.17/2.56	   active(U13(tt))
6.17/2.56	   active(U21(tt, x0))
6.17/2.56	   active(U22(tt))
6.17/2.56	   active(U31(tt, x0))
6.17/2.56	   active(U41(tt, x0, x1))
6.17/2.56	   active(and(tt, x0))
6.17/2.56	   active(isNat(0))
6.17/2.56	   active(isNat(plus(x0, x1)))
6.17/2.56	   active(isNat(s(x0)))
6.17/2.56	   active(isNatKind(0))
6.17/2.56	   active(isNatKind(plus(x0, x1)))
6.17/2.56	   active(isNatKind(s(x0)))
6.17/2.56	   active(plus(x0, 0))
6.17/2.56	   active(plus(x0, s(x1)))
6.17/2.56	   mark(U11(x0, x1, x2))
6.17/2.56	   mark(tt)
6.17/2.56	   mark(U12(x0, x1))
6.17/2.56	   mark(isNat(x0))
6.17/2.56	   mark(U13(x0))
6.17/2.56	   mark(U21(x0, x1))
6.17/2.56	   mark(U22(x0))
6.17/2.56	   mark(U31(x0, x1))
6.17/2.56	   mark(U41(x0, x1, x2))
6.17/2.56	   mark(s(x0))
6.17/2.56	   mark(plus(x0, x1))
6.17/2.56	   mark(and(x0, x1))
6.17/2.56	   mark(0)
6.17/2.56	   mark(isNatKind(x0))
6.17/2.56	   U11(mark(x0), x1, x2)
6.17/2.56	   U11(x0, mark(x1), x2)
6.17/2.56	   U11(x0, x1, mark(x2))
6.17/2.56	   U11(active(x0), x1, x2)
6.17/2.56	   U11(x0, active(x1), x2)
6.17/2.56	   U11(x0, x1, active(x2))
6.17/2.56	   U12(mark(x0), x1)
6.17/2.56	   U12(x0, mark(x1))
6.17/2.56	   U12(active(x0), x1)
6.17/2.56	   U12(x0, active(x1))
6.17/2.56	   isNat(mark(x0))
6.17/2.56	   isNat(active(x0))
6.17/2.56	   U13(mark(x0))
6.17/2.56	   U13(active(x0))
6.17/2.56	   U21(mark(x0), x1)
6.17/2.56	   U21(x0, mark(x1))
6.17/2.56	   U21(active(x0), x1)
6.17/2.56	   U21(x0, active(x1))
6.17/2.56	   U22(mark(x0))
6.17/2.56	   U22(active(x0))
6.17/2.56	   U31(mark(x0), x1)
6.17/2.56	   U31(x0, mark(x1))
6.17/2.56	   U31(active(x0), x1)
6.17/2.56	   U31(x0, active(x1))
6.17/2.56	   U41(mark(x0), x1, x2)
6.17/2.56	   U41(x0, mark(x1), x2)
6.17/2.56	   U41(x0, x1, mark(x2))
6.17/2.56	   U41(active(x0), x1, x2)
6.17/2.56	   U41(x0, active(x1), x2)
6.17/2.56	   U41(x0, x1, active(x2))
6.17/2.56	   s(mark(x0))
6.17/2.56	   s(active(x0))
6.17/2.56	   plus(mark(x0), x1)
6.17/2.56	   plus(x0, mark(x1))
6.17/2.56	   plus(active(x0), x1)
6.17/2.56	   plus(x0, active(x1))
6.17/2.56	   and(mark(x0), x1)
6.17/2.56	   and(x0, mark(x1))
6.17/2.56	   and(active(x0), x1)
6.17/2.56	   and(x0, active(x1))
6.17/2.56	   isNatKind(mark(x0))
6.17/2.56	   isNatKind(active(x0))
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(1) QTRSRRRProof (EQUIVALENT)
6.17/2.56	Used ordering:
6.17/2.56	active/1)YES(
6.17/2.56	U11/3(YES,YES,YES)
6.17/2.56	tt/0)
6.17/2.56	mark/1)YES(
6.17/2.56	U12/2(YES,YES)
6.17/2.56	isNat/1(YES)
6.17/2.56	U13/1)YES(
6.17/2.56	U21/2(YES,YES)
6.17/2.56	U22/1)YES(
6.17/2.56	U31/2(YES,YES)
6.17/2.56	U41/3(YES,YES,YES)
6.17/2.56	s/1(YES)
6.17/2.56	plus/2(YES,YES)
6.17/2.56	and/2(YES,YES)
6.17/2.56	0/0)
6.17/2.56	isNatKind/1(YES)
6.17/2.56	
6.17/2.56	Quasi precedence:
6.17/2.56	[U41_3, plus_2] > U11_3 > [U12_2, isNat_1, U21_2, s_1] > isNatKind_1 > [tt, 0]
6.17/2.56	[U41_3, plus_2] > U31_2
6.17/2.56	[U41_3, plus_2] > and_2
6.17/2.56	
6.17/2.56	
6.17/2.56	Status:
6.17/2.56	U11_3: multiset status
6.17/2.56	tt: multiset status
6.17/2.56	U12_2: multiset status
6.17/2.56	isNat_1: multiset status
6.17/2.56	U21_2: multiset status
6.17/2.56	U31_2: multiset status
6.17/2.56	U41_3: [3,2,1]
6.17/2.56	s_1: multiset status
6.17/2.56	plus_2: [1,2]
6.17/2.56	and_2: [2,1]
6.17/2.56	0: multiset status
6.17/2.56	isNatKind_1: multiset status
6.17/2.56	
6.17/2.56	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.17/2.56	
6.17/2.56	   active(U11(tt, V1, V2)) -> mark(U12(isNat(V1), V2))
6.17/2.56	   active(U12(tt, V2)) -> mark(U13(isNat(V2)))
6.17/2.56	   active(U21(tt, V1)) -> mark(U22(isNat(V1)))
6.17/2.56	   active(U31(tt, N)) -> mark(N)
6.17/2.56	   active(U41(tt, M, N)) -> mark(s(plus(N, M)))
6.17/2.56	   active(and(tt, X)) -> mark(X)
6.17/2.56	   active(isNat(0)) -> mark(tt)
6.17/2.56	   active(isNat(plus(V1, V2))) -> mark(U11(and(isNatKind(V1), isNatKind(V2)), V1, V2))
6.17/2.56	   active(isNat(s(V1))) -> mark(U21(isNatKind(V1), V1))
6.17/2.56	   active(isNatKind(0)) -> mark(tt)
6.17/2.56	   active(isNatKind(plus(V1, V2))) -> mark(and(isNatKind(V1), isNatKind(V2)))
6.17/2.56	   active(isNatKind(s(V1))) -> mark(isNatKind(V1))
6.17/2.56	   active(plus(N, 0)) -> mark(U31(and(isNat(N), isNatKind(N)), N))
6.17/2.56	   active(plus(N, s(M))) -> mark(U41(and(and(isNat(M), isNatKind(M)), and(isNat(N), isNatKind(N))), M, N))
6.17/2.56	
6.17/2.56	
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(2)
6.17/2.56	Obligation:
6.17/2.56	Q restricted rewrite system:
6.17/2.56	The TRS R consists of the following rules:
6.17/2.56	
6.17/2.56	   active(U13(tt)) -> mark(tt)
6.17/2.56	   active(U22(tt)) -> mark(tt)
6.17/2.56	   mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3))
6.17/2.56	   mark(tt) -> active(tt)
6.17/2.56	   mark(U12(X1, X2)) -> active(U12(mark(X1), X2))
6.17/2.56	   mark(isNat(X)) -> active(isNat(X))
6.17/2.56	   mark(U13(X)) -> active(U13(mark(X)))
6.17/2.56	   mark(U21(X1, X2)) -> active(U21(mark(X1), X2))
6.17/2.56	   mark(U22(X)) -> active(U22(mark(X)))
6.17/2.56	   mark(U31(X1, X2)) -> active(U31(mark(X1), X2))
6.17/2.56	   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
6.17/2.56	   mark(s(X)) -> active(s(mark(X)))
6.17/2.56	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.17/2.56	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.17/2.56	   mark(0) -> active(0)
6.17/2.56	   mark(isNatKind(X)) -> active(isNatKind(X))
6.17/2.56	   U11(mark(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, mark(X2), X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, X2, mark(X3)) -> U11(X1, X2, X3)
6.17/2.56	   U11(active(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, active(X2), X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, X2, active(X3)) -> U11(X1, X2, X3)
6.17/2.56	   U12(mark(X1), X2) -> U12(X1, X2)
6.17/2.56	   U12(X1, mark(X2)) -> U12(X1, X2)
6.17/2.56	   U12(active(X1), X2) -> U12(X1, X2)
6.17/2.56	   U12(X1, active(X2)) -> U12(X1, X2)
6.17/2.56	   isNat(mark(X)) -> isNat(X)
6.17/2.56	   isNat(active(X)) -> isNat(X)
6.17/2.56	   U13(mark(X)) -> U13(X)
6.17/2.56	   U13(active(X)) -> U13(X)
6.17/2.56	   U21(mark(X1), X2) -> U21(X1, X2)
6.17/2.56	   U21(X1, mark(X2)) -> U21(X1, X2)
6.17/2.56	   U21(active(X1), X2) -> U21(X1, X2)
6.17/2.56	   U21(X1, active(X2)) -> U21(X1, X2)
6.17/2.56	   U22(mark(X)) -> U22(X)
6.17/2.56	   U22(active(X)) -> U22(X)
6.17/2.56	   U31(mark(X1), X2) -> U31(X1, X2)
6.17/2.56	   U31(X1, mark(X2)) -> U31(X1, X2)
6.17/2.56	   U31(active(X1), X2) -> U31(X1, X2)
6.17/2.56	   U31(X1, active(X2)) -> U31(X1, X2)
6.17/2.56	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.17/2.56	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.17/2.56	   s(mark(X)) -> s(X)
6.17/2.56	   s(active(X)) -> s(X)
6.17/2.56	   plus(mark(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, mark(X2)) -> plus(X1, X2)
6.17/2.56	   plus(active(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, active(X2)) -> plus(X1, X2)
6.17/2.56	   and(mark(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, mark(X2)) -> and(X1, X2)
6.17/2.56	   and(active(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, active(X2)) -> and(X1, X2)
6.17/2.56	   isNatKind(mark(X)) -> isNatKind(X)
6.17/2.56	   isNatKind(active(X)) -> isNatKind(X)
6.17/2.56	
6.17/2.56	The set Q consists of the following terms:
6.17/2.56	
6.17/2.56	   active(U11(tt, x0, x1))
6.17/2.56	   active(U12(tt, x0))
6.17/2.56	   active(U13(tt))
6.17/2.56	   active(U21(tt, x0))
6.17/2.56	   active(U22(tt))
6.17/2.56	   active(U31(tt, x0))
6.17/2.56	   active(U41(tt, x0, x1))
6.17/2.56	   active(and(tt, x0))
6.17/2.56	   active(isNat(0))
6.17/2.56	   active(isNat(plus(x0, x1)))
6.17/2.56	   active(isNat(s(x0)))
6.17/2.56	   active(isNatKind(0))
6.17/2.56	   active(isNatKind(plus(x0, x1)))
6.17/2.56	   active(isNatKind(s(x0)))
6.17/2.56	   active(plus(x0, 0))
6.17/2.56	   active(plus(x0, s(x1)))
6.17/2.56	   mark(U11(x0, x1, x2))
6.17/2.56	   mark(tt)
6.17/2.56	   mark(U12(x0, x1))
6.17/2.56	   mark(isNat(x0))
6.17/2.56	   mark(U13(x0))
6.17/2.56	   mark(U21(x0, x1))
6.17/2.56	   mark(U22(x0))
6.17/2.56	   mark(U31(x0, x1))
6.17/2.56	   mark(U41(x0, x1, x2))
6.17/2.56	   mark(s(x0))
6.17/2.56	   mark(plus(x0, x1))
6.17/2.56	   mark(and(x0, x1))
6.17/2.56	   mark(0)
6.17/2.56	   mark(isNatKind(x0))
6.17/2.56	   U11(mark(x0), x1, x2)
6.17/2.56	   U11(x0, mark(x1), x2)
6.17/2.56	   U11(x0, x1, mark(x2))
6.17/2.56	   U11(active(x0), x1, x2)
6.17/2.56	   U11(x0, active(x1), x2)
6.17/2.56	   U11(x0, x1, active(x2))
6.17/2.56	   U12(mark(x0), x1)
6.17/2.56	   U12(x0, mark(x1))
6.17/2.56	   U12(active(x0), x1)
6.17/2.56	   U12(x0, active(x1))
6.17/2.56	   isNat(mark(x0))
6.17/2.56	   isNat(active(x0))
6.17/2.56	   U13(mark(x0))
6.17/2.56	   U13(active(x0))
6.17/2.56	   U21(mark(x0), x1)
6.17/2.56	   U21(x0, mark(x1))
6.17/2.56	   U21(active(x0), x1)
6.17/2.56	   U21(x0, active(x1))
6.17/2.56	   U22(mark(x0))
6.17/2.56	   U22(active(x0))
6.17/2.56	   U31(mark(x0), x1)
6.17/2.56	   U31(x0, mark(x1))
6.17/2.56	   U31(active(x0), x1)
6.17/2.56	   U31(x0, active(x1))
6.17/2.56	   U41(mark(x0), x1, x2)
6.17/2.56	   U41(x0, mark(x1), x2)
6.17/2.56	   U41(x0, x1, mark(x2))
6.17/2.56	   U41(active(x0), x1, x2)
6.17/2.56	   U41(x0, active(x1), x2)
6.17/2.56	   U41(x0, x1, active(x2))
6.17/2.56	   s(mark(x0))
6.17/2.56	   s(active(x0))
6.17/2.56	   plus(mark(x0), x1)
6.17/2.56	   plus(x0, mark(x1))
6.17/2.56	   plus(active(x0), x1)
6.17/2.56	   plus(x0, active(x1))
6.17/2.56	   and(mark(x0), x1)
6.17/2.56	   and(x0, mark(x1))
6.17/2.56	   and(active(x0), x1)
6.17/2.56	   and(x0, active(x1))
6.17/2.56	   isNatKind(mark(x0))
6.17/2.56	   isNatKind(active(x0))
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(3) QTRSRRRProof (EQUIVALENT)
6.17/2.56	Used ordering:
6.17/2.56	Polynomial interpretation [POLO]:
6.17/2.56	
6.17/2.56	   POL(0) = 2
6.17/2.56	   POL(U11(x_1, x_2, x_3)) = 2 + 2*x_1 + x_2 + 2*x_3
6.17/2.56	   POL(U12(x_1, x_2)) = 2 + x_1 + x_2
6.17/2.56	   POL(U13(x_1)) = 2 + x_1
6.17/2.56	   POL(U21(x_1, x_2)) = 2 + x_1 + 2*x_2
6.17/2.56	   POL(U22(x_1)) = 2 + x_1
6.17/2.56	   POL(U31(x_1, x_2)) = 2 + x_1 + x_2
6.17/2.56	   POL(U41(x_1, x_2, x_3)) = 2 + x_1 + x_2 + x_3
6.17/2.56	   POL(active(x_1)) = 1 + x_1
6.17/2.56	   POL(and(x_1, x_2)) = 2 + x_1 + x_2
6.17/2.56	   POL(isNat(x_1)) = 2 + x_1
6.17/2.56	   POL(isNatKind(x_1)) = 2 + x_1
6.17/2.56	   POL(mark(x_1)) = 2*x_1
6.17/2.56	   POL(plus(x_1, x_2)) = 2 + 2*x_1 + x_2
6.17/2.56	   POL(s(x_1)) = 2 + x_1
6.17/2.56	   POL(tt) = 2
6.17/2.56	With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
6.17/2.56	
6.17/2.56	   active(U13(tt)) -> mark(tt)
6.17/2.56	   active(U22(tt)) -> mark(tt)
6.17/2.56	   mark(U11(X1, X2, X3)) -> active(U11(mark(X1), X2, X3))
6.17/2.56	   mark(tt) -> active(tt)
6.17/2.56	   mark(U12(X1, X2)) -> active(U12(mark(X1), X2))
6.17/2.56	   mark(isNat(X)) -> active(isNat(X))
6.17/2.56	   mark(U13(X)) -> active(U13(mark(X)))
6.17/2.56	   mark(U21(X1, X2)) -> active(U21(mark(X1), X2))
6.17/2.56	   mark(U22(X)) -> active(U22(mark(X)))
6.17/2.56	   mark(U31(X1, X2)) -> active(U31(mark(X1), X2))
6.17/2.56	   mark(U41(X1, X2, X3)) -> active(U41(mark(X1), X2, X3))
6.17/2.56	   mark(s(X)) -> active(s(mark(X)))
6.17/2.56	   mark(plus(X1, X2)) -> active(plus(mark(X1), mark(X2)))
6.17/2.56	   mark(and(X1, X2)) -> active(and(mark(X1), X2))
6.17/2.56	   mark(0) -> active(0)
6.17/2.56	   mark(isNatKind(X)) -> active(isNatKind(X))
6.17/2.56	   U11(active(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, active(X2), X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, X2, active(X3)) -> U11(X1, X2, X3)
6.17/2.56	   U12(active(X1), X2) -> U12(X1, X2)
6.17/2.56	   U12(X1, active(X2)) -> U12(X1, X2)
6.17/2.56	   isNat(active(X)) -> isNat(X)
6.17/2.56	   U13(active(X)) -> U13(X)
6.17/2.56	   U21(active(X1), X2) -> U21(X1, X2)
6.17/2.56	   U21(X1, active(X2)) -> U21(X1, X2)
6.17/2.56	   U22(active(X)) -> U22(X)
6.17/2.56	   U31(active(X1), X2) -> U31(X1, X2)
6.17/2.56	   U31(X1, active(X2)) -> U31(X1, X2)
6.17/2.56	   U41(active(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, active(X2), X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, X2, active(X3)) -> U41(X1, X2, X3)
6.17/2.56	   s(active(X)) -> s(X)
6.17/2.56	   plus(active(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, active(X2)) -> plus(X1, X2)
6.17/2.56	   and(active(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, active(X2)) -> and(X1, X2)
6.17/2.56	   isNatKind(active(X)) -> isNatKind(X)
6.17/2.56	
6.17/2.56	
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(4)
6.17/2.56	Obligation:
6.17/2.56	Q restricted rewrite system:
6.17/2.56	The TRS R consists of the following rules:
6.17/2.56	
6.17/2.56	   U11(mark(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, mark(X2), X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, X2, mark(X3)) -> U11(X1, X2, X3)
6.17/2.56	   U12(mark(X1), X2) -> U12(X1, X2)
6.17/2.56	   U12(X1, mark(X2)) -> U12(X1, X2)
6.17/2.56	   isNat(mark(X)) -> isNat(X)
6.17/2.56	   U13(mark(X)) -> U13(X)
6.17/2.56	   U21(mark(X1), X2) -> U21(X1, X2)
6.17/2.56	   U21(X1, mark(X2)) -> U21(X1, X2)
6.17/2.56	   U22(mark(X)) -> U22(X)
6.17/2.56	   U31(mark(X1), X2) -> U31(X1, X2)
6.17/2.56	   U31(X1, mark(X2)) -> U31(X1, X2)
6.17/2.56	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.17/2.56	   s(mark(X)) -> s(X)
6.17/2.56	   plus(mark(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, mark(X2)) -> plus(X1, X2)
6.17/2.56	   and(mark(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, mark(X2)) -> and(X1, X2)
6.17/2.56	   isNatKind(mark(X)) -> isNatKind(X)
6.17/2.56	
6.17/2.56	The set Q consists of the following terms:
6.17/2.56	
6.17/2.56	   active(U11(tt, x0, x1))
6.17/2.56	   active(U12(tt, x0))
6.17/2.56	   active(U13(tt))
6.17/2.56	   active(U21(tt, x0))
6.17/2.56	   active(U22(tt))
6.17/2.56	   active(U31(tt, x0))
6.17/2.56	   active(U41(tt, x0, x1))
6.17/2.56	   active(and(tt, x0))
6.17/2.56	   active(isNat(0))
6.17/2.56	   active(isNat(plus(x0, x1)))
6.17/2.56	   active(isNat(s(x0)))
6.17/2.56	   active(isNatKind(0))
6.17/2.56	   active(isNatKind(plus(x0, x1)))
6.17/2.56	   active(isNatKind(s(x0)))
6.17/2.56	   active(plus(x0, 0))
6.17/2.56	   active(plus(x0, s(x1)))
6.17/2.56	   mark(U11(x0, x1, x2))
6.17/2.56	   mark(tt)
6.17/2.56	   mark(U12(x0, x1))
6.17/2.56	   mark(isNat(x0))
6.17/2.56	   mark(U13(x0))
6.17/2.56	   mark(U21(x0, x1))
6.17/2.56	   mark(U22(x0))
6.17/2.56	   mark(U31(x0, x1))
6.17/2.56	   mark(U41(x0, x1, x2))
6.17/2.56	   mark(s(x0))
6.17/2.56	   mark(plus(x0, x1))
6.17/2.56	   mark(and(x0, x1))
6.17/2.56	   mark(0)
6.17/2.56	   mark(isNatKind(x0))
6.17/2.56	   U11(mark(x0), x1, x2)
6.17/2.56	   U11(x0, mark(x1), x2)
6.17/2.56	   U11(x0, x1, mark(x2))
6.17/2.56	   U11(active(x0), x1, x2)
6.17/2.56	   U11(x0, active(x1), x2)
6.17/2.56	   U11(x0, x1, active(x2))
6.17/2.56	   U12(mark(x0), x1)
6.17/2.56	   U12(x0, mark(x1))
6.17/2.56	   U12(active(x0), x1)
6.17/2.56	   U12(x0, active(x1))
6.17/2.56	   isNat(mark(x0))
6.17/2.56	   isNat(active(x0))
6.17/2.56	   U13(mark(x0))
6.17/2.56	   U13(active(x0))
6.17/2.56	   U21(mark(x0), x1)
6.17/2.56	   U21(x0, mark(x1))
6.17/2.56	   U21(active(x0), x1)
6.17/2.56	   U21(x0, active(x1))
6.17/2.56	   U22(mark(x0))
6.17/2.56	   U22(active(x0))
6.17/2.56	   U31(mark(x0), x1)
6.17/2.56	   U31(x0, mark(x1))
6.17/2.56	   U31(active(x0), x1)
6.17/2.56	   U31(x0, active(x1))
6.17/2.56	   U41(mark(x0), x1, x2)
6.17/2.56	   U41(x0, mark(x1), x2)
6.17/2.56	   U41(x0, x1, mark(x2))
6.17/2.56	   U41(active(x0), x1, x2)
6.17/2.56	   U41(x0, active(x1), x2)
6.17/2.56	   U41(x0, x1, active(x2))
6.17/2.56	   s(mark(x0))
6.17/2.56	   s(active(x0))
6.17/2.56	   plus(mark(x0), x1)
6.17/2.56	   plus(x0, mark(x1))
6.17/2.56	   plus(active(x0), x1)
6.17/2.56	   plus(x0, active(x1))
6.17/2.56	   and(mark(x0), x1)
6.17/2.56	   and(x0, mark(x1))
6.17/2.56	   and(active(x0), x1)
6.17/2.56	   and(x0, active(x1))
6.17/2.56	   isNatKind(mark(x0))
6.17/2.56	   isNatKind(active(x0))
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(5) QTRSRRRProof (EQUIVALENT)
6.17/2.56	Used ordering:
6.17/2.56	Knuth-Bendix order [KBO] with precedence:mark_1 > isNatKind_1 > and_2 > plus_2 > s_1 > U41_3 > U31_2 > U22_1 > U21_2 > U13_1 > isNat_1 > U11_3 > U12_2
6.17/2.56	
6.17/2.56	and weight map:
6.17/2.56	
6.17/2.56	   mark_1=0
6.17/2.56	   isNat_1=1
6.17/2.56	   U13_1=1
6.17/2.56	   U22_1=1
6.17/2.56	   s_1=1
6.17/2.56	   isNatKind_1=1
6.17/2.56	   U11_3=0
6.17/2.56	   U12_2=0
6.17/2.56	   U21_2=0
6.17/2.56	   U31_2=0
6.17/2.56	   U41_3=0
6.17/2.56	   plus_2=0
6.17/2.56	   and_2=0
6.17/2.56	
6.17/2.56	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.17/2.56	
6.17/2.56	   U11(mark(X1), X2, X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, mark(X2), X3) -> U11(X1, X2, X3)
6.17/2.56	   U11(X1, X2, mark(X3)) -> U11(X1, X2, X3)
6.17/2.56	   U12(mark(X1), X2) -> U12(X1, X2)
6.17/2.56	   U12(X1, mark(X2)) -> U12(X1, X2)
6.17/2.56	   isNat(mark(X)) -> isNat(X)
6.17/2.56	   U13(mark(X)) -> U13(X)
6.17/2.56	   U21(mark(X1), X2) -> U21(X1, X2)
6.17/2.56	   U21(X1, mark(X2)) -> U21(X1, X2)
6.17/2.56	   U22(mark(X)) -> U22(X)
6.17/2.56	   U31(mark(X1), X2) -> U31(X1, X2)
6.17/2.56	   U31(X1, mark(X2)) -> U31(X1, X2)
6.17/2.56	   U41(mark(X1), X2, X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, mark(X2), X3) -> U41(X1, X2, X3)
6.17/2.56	   U41(X1, X2, mark(X3)) -> U41(X1, X2, X3)
6.17/2.56	   s(mark(X)) -> s(X)
6.17/2.56	   plus(mark(X1), X2) -> plus(X1, X2)
6.17/2.56	   plus(X1, mark(X2)) -> plus(X1, X2)
6.17/2.56	   and(mark(X1), X2) -> and(X1, X2)
6.17/2.56	   and(X1, mark(X2)) -> and(X1, X2)
6.17/2.56	   isNatKind(mark(X)) -> isNatKind(X)
6.17/2.56	
6.17/2.56	
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(6)
6.17/2.56	Obligation:
6.17/2.56	Q restricted rewrite system:
6.17/2.56	R is empty.
6.17/2.56	The set Q consists of the following terms:
6.17/2.56	
6.17/2.56	   active(U11(tt, x0, x1))
6.17/2.56	   active(U12(tt, x0))
6.17/2.56	   active(U13(tt))
6.17/2.56	   active(U21(tt, x0))
6.17/2.56	   active(U22(tt))
6.17/2.56	   active(U31(tt, x0))
6.17/2.56	   active(U41(tt, x0, x1))
6.17/2.56	   active(and(tt, x0))
6.17/2.56	   active(isNat(0))
6.17/2.56	   active(isNat(plus(x0, x1)))
6.17/2.56	   active(isNat(s(x0)))
6.17/2.56	   active(isNatKind(0))
6.17/2.56	   active(isNatKind(plus(x0, x1)))
6.17/2.56	   active(isNatKind(s(x0)))
6.17/2.56	   active(plus(x0, 0))
6.17/2.56	   active(plus(x0, s(x1)))
6.17/2.56	   mark(U11(x0, x1, x2))
6.17/2.56	   mark(tt)
6.17/2.56	   mark(U12(x0, x1))
6.17/2.56	   mark(isNat(x0))
6.17/2.56	   mark(U13(x0))
6.17/2.56	   mark(U21(x0, x1))
6.17/2.56	   mark(U22(x0))
6.17/2.56	   mark(U31(x0, x1))
6.17/2.56	   mark(U41(x0, x1, x2))
6.17/2.56	   mark(s(x0))
6.17/2.56	   mark(plus(x0, x1))
6.17/2.56	   mark(and(x0, x1))
6.17/2.56	   mark(0)
6.17/2.56	   mark(isNatKind(x0))
6.17/2.56	   U11(mark(x0), x1, x2)
6.17/2.56	   U11(x0, mark(x1), x2)
6.17/2.56	   U11(x0, x1, mark(x2))
6.17/2.56	   U11(active(x0), x1, x2)
6.17/2.56	   U11(x0, active(x1), x2)
6.17/2.56	   U11(x0, x1, active(x2))
6.17/2.56	   U12(mark(x0), x1)
6.17/2.56	   U12(x0, mark(x1))
6.17/2.56	   U12(active(x0), x1)
6.17/2.56	   U12(x0, active(x1))
6.17/2.56	   isNat(mark(x0))
6.17/2.56	   isNat(active(x0))
6.17/2.56	   U13(mark(x0))
6.17/2.56	   U13(active(x0))
6.17/2.56	   U21(mark(x0), x1)
6.17/2.56	   U21(x0, mark(x1))
6.17/2.56	   U21(active(x0), x1)
6.17/2.56	   U21(x0, active(x1))
6.17/2.56	   U22(mark(x0))
6.17/2.56	   U22(active(x0))
6.17/2.56	   U31(mark(x0), x1)
6.17/2.56	   U31(x0, mark(x1))
6.17/2.56	   U31(active(x0), x1)
6.17/2.56	   U31(x0, active(x1))
6.17/2.56	   U41(mark(x0), x1, x2)
6.17/2.56	   U41(x0, mark(x1), x2)
6.17/2.56	   U41(x0, x1, mark(x2))
6.17/2.56	   U41(active(x0), x1, x2)
6.17/2.56	   U41(x0, active(x1), x2)
6.17/2.56	   U41(x0, x1, active(x2))
6.17/2.56	   s(mark(x0))
6.17/2.56	   s(active(x0))
6.17/2.56	   plus(mark(x0), x1)
6.17/2.56	   plus(x0, mark(x1))
6.17/2.56	   plus(active(x0), x1)
6.17/2.56	   plus(x0, active(x1))
6.17/2.56	   and(mark(x0), x1)
6.17/2.56	   and(x0, mark(x1))
6.17/2.56	   and(active(x0), x1)
6.17/2.56	   and(x0, active(x1))
6.17/2.56	   isNatKind(mark(x0))
6.17/2.56	   isNatKind(active(x0))
6.17/2.56	
6.17/2.56	
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(7) RisEmptyProof (EQUIVALENT)
6.17/2.56	The TRS R is empty. Hence, termination is trivially proven.
6.17/2.56	----------------------------------------
6.17/2.56	
6.17/2.56	(8)
6.17/2.56	YES
6.17/2.59	EOF