6.22/2.41	YES
6.22/2.42	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
6.22/2.42	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
6.22/2.42	
6.22/2.42	
6.22/2.42	Termination w.r.t. Q of the given QTRS could be proven:
6.22/2.42	
6.22/2.42	(0) QTRS
6.22/2.42	(1) QTRSToCSRProof [SOUND, 0 ms]
6.22/2.42	(2) CSR
6.22/2.42	(3) CSDependencyPairsProof [EQUIVALENT, 0 ms]
6.22/2.42	(4) QCSDP
6.22/2.42	(5) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
6.22/2.42	(6) AND
6.22/2.42	    (7) QCSDP
6.22/2.42	        (8) QCSDPReductionPairProof [EQUIVALENT, 117 ms]
6.22/2.42	        (9) QCSDP
6.22/2.42	        (10) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
6.22/2.42	        (11) TRUE
6.22/2.42	    (12) QCSDP
6.22/2.42	        (13) QCSDPSubtermProof [EQUIVALENT, 0 ms]
6.22/2.42	        (14) QCSDP
6.22/2.42	        (15) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
6.22/2.42	        (16) TRUE
6.22/2.42	    (17) QCSDP
6.22/2.42	        (18) QCSDPSubtermProof [EQUIVALENT, 2 ms]
6.22/2.42	        (19) QCSDP
6.22/2.42	        (20) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
6.22/2.42	        (21) TRUE
6.22/2.42	
6.22/2.42	
6.22/2.42	----------------------------------------
6.22/2.42	
6.22/2.42	(0)
6.22/2.42	Obligation:
6.22/2.42	Q restricted rewrite system:
6.22/2.42	The TRS R consists of the following rules:
6.22/2.42	
6.22/2.42	   active(U11(tt, N)) -> mark(N)
6.22/2.42	   active(U21(tt, M, N)) -> mark(s(plus(N, M)))
6.22/2.42	   active(U31(tt)) -> mark(0)
6.22/2.42	   active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
6.22/2.42	   active(and(tt, X)) -> mark(X)
6.22/2.42	   active(isNat(0)) -> mark(tt)
6.22/2.42	   active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.22/2.42	   active(isNat(s(V1))) -> mark(isNat(V1))
6.22/2.42	   active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.22/2.42	   active(plus(N, 0)) -> mark(U11(isNat(N), N))
6.22/2.42	   active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
6.22/2.42	   active(x(N, 0)) -> mark(U31(isNat(N)))
6.22/2.42	   active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
6.22/2.42	   active(U11(X1, X2)) -> U11(active(X1), X2)
6.22/2.42	   active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
6.22/2.42	   active(s(X)) -> s(active(X))
6.22/2.42	   active(plus(X1, X2)) -> plus(active(X1), X2)
6.22/2.42	   active(plus(X1, X2)) -> plus(X1, active(X2))
6.22/2.42	   active(U31(X)) -> U31(active(X))
6.22/2.42	   active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
6.22/2.42	   active(x(X1, X2)) -> x(active(X1), X2)
6.22/2.42	   active(x(X1, X2)) -> x(X1, active(X2))
6.22/2.42	   active(and(X1, X2)) -> and(active(X1), X2)
6.22/2.42	   U11(mark(X1), X2) -> mark(U11(X1, X2))
6.22/2.42	   U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
6.22/2.42	   s(mark(X)) -> mark(s(X))
6.22/2.42	   plus(mark(X1), X2) -> mark(plus(X1, X2))
6.22/2.42	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
6.22/2.42	   U31(mark(X)) -> mark(U31(X))
6.22/2.42	   U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
6.22/2.42	   x(mark(X1), X2) -> mark(x(X1, X2))
6.22/2.42	   x(X1, mark(X2)) -> mark(x(X1, X2))
6.22/2.42	   and(mark(X1), X2) -> mark(and(X1, X2))
6.22/2.42	   proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
6.22/2.42	   proper(tt) -> ok(tt)
6.22/2.42	   proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
6.22/2.42	   proper(s(X)) -> s(proper(X))
6.22/2.42	   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
6.22/2.42	   proper(U31(X)) -> U31(proper(X))
6.22/2.42	   proper(0) -> ok(0)
6.22/2.42	   proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
6.22/2.42	   proper(x(X1, X2)) -> x(proper(X1), proper(X2))
6.22/2.42	   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
6.22/2.42	   proper(isNat(X)) -> isNat(proper(X))
6.22/2.42	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
6.22/2.42	   U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
6.22/2.43	   s(ok(X)) -> ok(s(X))
6.22/2.43	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
6.22/2.43	   U31(ok(X)) -> ok(U31(X))
6.22/2.43	   U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
6.22/2.43	   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
6.22/2.43	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
6.22/2.43	   isNat(ok(X)) -> ok(isNat(X))
6.22/2.43	   top(mark(X)) -> top(proper(X))
6.22/2.43	   top(ok(X)) -> top(active(X))
6.22/2.43	
6.22/2.43	The set Q consists of the following terms:
6.22/2.43	
6.22/2.43	   active(isNat(0))
6.22/2.43	   active(isNat(plus(x0, x1)))
6.22/2.43	   active(isNat(s(x0)))
6.22/2.43	   active(isNat(x(x0, x1)))
6.22/2.43	   active(U11(x0, x1))
6.22/2.43	   active(U21(x0, x1, x2))
6.22/2.43	   active(s(x0))
6.22/2.43	   active(plus(x0, x1))
6.22/2.43	   active(U31(x0))
6.22/2.43	   active(U41(x0, x1, x2))
6.22/2.43	   active(x(x0, x1))
6.22/2.43	   active(and(x0, x1))
6.22/2.43	   U11(mark(x0), x1)
6.22/2.43	   U21(mark(x0), x1, x2)
6.22/2.43	   s(mark(x0))
6.22/2.43	   plus(mark(x0), x1)
6.22/2.43	   plus(x0, mark(x1))
6.22/2.43	   U31(mark(x0))
6.22/2.43	   U41(mark(x0), x1, x2)
6.22/2.43	   x(mark(x0), x1)
6.22/2.43	   x(x0, mark(x1))
6.22/2.43	   and(mark(x0), x1)
6.22/2.43	   proper(U11(x0, x1))
6.22/2.43	   proper(tt)
6.22/2.43	   proper(U21(x0, x1, x2))
6.22/2.43	   proper(s(x0))
6.22/2.43	   proper(plus(x0, x1))
6.22/2.43	   proper(U31(x0))
6.22/2.43	   proper(0)
6.22/2.43	   proper(U41(x0, x1, x2))
6.22/2.43	   proper(x(x0, x1))
6.22/2.43	   proper(and(x0, x1))
6.22/2.43	   proper(isNat(x0))
6.22/2.43	   U11(ok(x0), ok(x1))
6.22/2.43	   U21(ok(x0), ok(x1), ok(x2))
6.22/2.43	   s(ok(x0))
6.22/2.43	   plus(ok(x0), ok(x1))
6.22/2.43	   U31(ok(x0))
6.22/2.43	   U41(ok(x0), ok(x1), ok(x2))
6.22/2.43	   x(ok(x0), ok(x1))
6.22/2.43	   and(ok(x0), ok(x1))
6.22/2.43	   isNat(ok(x0))
6.22/2.43	   top(mark(x0))
6.22/2.43	   top(ok(x0))
6.22/2.43	
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(1) QTRSToCSRProof (SOUND)
6.22/2.43	The following Q TRS is given: Q restricted rewrite system:
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   active(U11(tt, N)) -> mark(N)
6.22/2.43	   active(U21(tt, M, N)) -> mark(s(plus(N, M)))
6.22/2.43	   active(U31(tt)) -> mark(0)
6.22/2.43	   active(U41(tt, M, N)) -> mark(plus(x(N, M), N))
6.22/2.43	   active(and(tt, X)) -> mark(X)
6.22/2.43	   active(isNat(0)) -> mark(tt)
6.22/2.43	   active(isNat(plus(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.22/2.43	   active(isNat(s(V1))) -> mark(isNat(V1))
6.22/2.43	   active(isNat(x(V1, V2))) -> mark(and(isNat(V1), isNat(V2)))
6.22/2.43	   active(plus(N, 0)) -> mark(U11(isNat(N), N))
6.22/2.43	   active(plus(N, s(M))) -> mark(U21(and(isNat(M), isNat(N)), M, N))
6.22/2.43	   active(x(N, 0)) -> mark(U31(isNat(N)))
6.22/2.43	   active(x(N, s(M))) -> mark(U41(and(isNat(M), isNat(N)), M, N))
6.22/2.43	   active(U11(X1, X2)) -> U11(active(X1), X2)
6.22/2.43	   active(U21(X1, X2, X3)) -> U21(active(X1), X2, X3)
6.22/2.43	   active(s(X)) -> s(active(X))
6.22/2.43	   active(plus(X1, X2)) -> plus(active(X1), X2)
6.22/2.43	   active(plus(X1, X2)) -> plus(X1, active(X2))
6.22/2.43	   active(U31(X)) -> U31(active(X))
6.22/2.43	   active(U41(X1, X2, X3)) -> U41(active(X1), X2, X3)
6.22/2.43	   active(x(X1, X2)) -> x(active(X1), X2)
6.22/2.43	   active(x(X1, X2)) -> x(X1, active(X2))
6.22/2.43	   active(and(X1, X2)) -> and(active(X1), X2)
6.22/2.43	   U11(mark(X1), X2) -> mark(U11(X1, X2))
6.22/2.43	   U21(mark(X1), X2, X3) -> mark(U21(X1, X2, X3))
6.22/2.43	   s(mark(X)) -> mark(s(X))
6.22/2.43	   plus(mark(X1), X2) -> mark(plus(X1, X2))
6.22/2.43	   plus(X1, mark(X2)) -> mark(plus(X1, X2))
6.22/2.43	   U31(mark(X)) -> mark(U31(X))
6.22/2.43	   U41(mark(X1), X2, X3) -> mark(U41(X1, X2, X3))
6.22/2.43	   x(mark(X1), X2) -> mark(x(X1, X2))
6.22/2.43	   x(X1, mark(X2)) -> mark(x(X1, X2))
6.22/2.43	   and(mark(X1), X2) -> mark(and(X1, X2))
6.22/2.43	   proper(U11(X1, X2)) -> U11(proper(X1), proper(X2))
6.22/2.43	   proper(tt) -> ok(tt)
6.22/2.43	   proper(U21(X1, X2, X3)) -> U21(proper(X1), proper(X2), proper(X3))
6.22/2.43	   proper(s(X)) -> s(proper(X))
6.22/2.43	   proper(plus(X1, X2)) -> plus(proper(X1), proper(X2))
6.22/2.43	   proper(U31(X)) -> U31(proper(X))
6.22/2.43	   proper(0) -> ok(0)
6.22/2.43	   proper(U41(X1, X2, X3)) -> U41(proper(X1), proper(X2), proper(X3))
6.22/2.43	   proper(x(X1, X2)) -> x(proper(X1), proper(X2))
6.22/2.43	   proper(and(X1, X2)) -> and(proper(X1), proper(X2))
6.22/2.43	   proper(isNat(X)) -> isNat(proper(X))
6.22/2.43	   U11(ok(X1), ok(X2)) -> ok(U11(X1, X2))
6.22/2.43	   U21(ok(X1), ok(X2), ok(X3)) -> ok(U21(X1, X2, X3))
6.22/2.43	   s(ok(X)) -> ok(s(X))
6.22/2.43	   plus(ok(X1), ok(X2)) -> ok(plus(X1, X2))
6.22/2.43	   U31(ok(X)) -> ok(U31(X))
6.22/2.43	   U41(ok(X1), ok(X2), ok(X3)) -> ok(U41(X1, X2, X3))
6.22/2.43	   x(ok(X1), ok(X2)) -> ok(x(X1, X2))
6.22/2.43	   and(ok(X1), ok(X2)) -> ok(and(X1, X2))
6.22/2.43	   isNat(ok(X)) -> ok(isNat(X))
6.22/2.43	   top(mark(X)) -> top(proper(X))
6.22/2.43	   top(ok(X)) -> top(active(X))
6.22/2.43	
6.22/2.43	The set Q consists of the following terms:
6.22/2.43	
6.22/2.43	   active(isNat(0))
6.22/2.43	   active(isNat(plus(x0, x1)))
6.22/2.43	   active(isNat(s(x0)))
6.22/2.43	   active(isNat(x(x0, x1)))
6.22/2.43	   active(U11(x0, x1))
6.22/2.43	   active(U21(x0, x1, x2))
6.22/2.43	   active(s(x0))
6.22/2.43	   active(plus(x0, x1))
6.22/2.43	   active(U31(x0))
6.22/2.43	   active(U41(x0, x1, x2))
6.22/2.43	   active(x(x0, x1))
6.22/2.43	   active(and(x0, x1))
6.22/2.43	   U11(mark(x0), x1)
6.22/2.43	   U21(mark(x0), x1, x2)
6.22/2.43	   s(mark(x0))
6.22/2.43	   plus(mark(x0), x1)
6.22/2.43	   plus(x0, mark(x1))
6.22/2.43	   U31(mark(x0))
6.22/2.43	   U41(mark(x0), x1, x2)
6.22/2.43	   x(mark(x0), x1)
6.22/2.43	   x(x0, mark(x1))
6.22/2.43	   and(mark(x0), x1)
6.22/2.43	   proper(U11(x0, x1))
6.22/2.43	   proper(tt)
6.22/2.43	   proper(U21(x0, x1, x2))
6.22/2.43	   proper(s(x0))
6.22/2.43	   proper(plus(x0, x1))
6.22/2.43	   proper(U31(x0))
6.22/2.43	   proper(0)
6.22/2.43	   proper(U41(x0, x1, x2))
6.22/2.43	   proper(x(x0, x1))
6.22/2.43	   proper(and(x0, x1))
6.22/2.43	   proper(isNat(x0))
6.22/2.43	   U11(ok(x0), ok(x1))
6.22/2.43	   U21(ok(x0), ok(x1), ok(x2))
6.22/2.43	   s(ok(x0))
6.22/2.43	   plus(ok(x0), ok(x1))
6.22/2.43	   U31(ok(x0))
6.22/2.43	   U41(ok(x0), ok(x1), ok(x2))
6.22/2.43	   x(ok(x0), ok(x1))
6.22/2.43	   and(ok(x0), ok(x1))
6.22/2.43	   isNat(ok(x0))
6.22/2.43	   top(mark(x0))
6.22/2.43	   top(ok(x0))
6.22/2.43	
6.22/2.43	Special symbols used for the transformation (see [GM04]):
6.22/2.43	top: top_1, active: active_1, mark: mark_1, ok: ok_1, proper: proper_1
6.22/2.43	The replacement map contains the following entries:
6.22/2.43	
6.22/2.43	U11: {1}
6.22/2.43	tt: empty set
6.22/2.43	U21: {1}
6.22/2.43	s: {1}
6.22/2.43	plus: {1, 2}
6.22/2.43	U31: {1}
6.22/2.43	0: empty set
6.22/2.43	U41: {1}
6.22/2.43	x: {1, 2}
6.22/2.43	and: {1}
6.22/2.43	isNat: empty set
6.22/2.43	The QTRS contained just a subset of rules created by the complete Giesl-Middeldorp transformation. Therefore, the inverse transformation is sound, but not necessarily complete.
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(2)
6.22/2.43	Obligation:
6.22/2.43	Context-sensitive rewrite system:
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	The replacement map contains the following entries:
6.22/2.43	
6.22/2.43	U11: {1}
6.22/2.43	tt: empty set
6.22/2.43	U21: {1}
6.22/2.43	s: {1}
6.22/2.43	plus: {1, 2}
6.22/2.43	U31: {1}
6.22/2.43	0: empty set
6.22/2.43	U41: {1}
6.22/2.43	x: {1, 2}
6.22/2.43	and: {1}
6.22/2.43	isNat: empty set
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(3) CSDependencyPairsProof (EQUIVALENT)
6.22/2.43	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(4)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2, PLUS_2, X_2, U31'_1} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, U21'_3, U41'_3, AND_2, U11'_2} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1, ISNAT_1, U_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The ordinary context-sensitive dependency pairs DP_o are:
6.22/2.43	   U21'(tt, M, N) -> PLUS(N, M)
6.22/2.43	   U41'(tt, M, N) -> PLUS(x(N, M), N)
6.22/2.43	   U41'(tt, M, N) -> X(N, M)
6.22/2.43	   ISNAT(plus(V1, V2)) -> AND(isNat(V1), isNat(V2))
6.22/2.43	   ISNAT(plus(V1, V2)) -> ISNAT(V1)
6.22/2.43	   ISNAT(s(V1)) -> ISNAT(V1)
6.22/2.43	   ISNAT(x(V1, V2)) -> AND(isNat(V1), isNat(V2))
6.22/2.43	   ISNAT(x(V1, V2)) -> ISNAT(V1)
6.22/2.43	   PLUS(N, 0) -> U11'(isNat(N), N)
6.22/2.43	   PLUS(N, 0) -> ISNAT(N)
6.22/2.43	   PLUS(N, s(M)) -> U21'(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   PLUS(N, s(M)) -> AND(isNat(M), isNat(N))
6.22/2.43	   PLUS(N, s(M)) -> ISNAT(M)
6.22/2.43	   X(N, 0) -> U31'(isNat(N))
6.22/2.43	   X(N, 0) -> ISNAT(N)
6.22/2.43	   X(N, s(M)) -> U41'(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   X(N, s(M)) -> AND(isNat(M), isNat(N))
6.22/2.43	   X(N, s(M)) -> ISNAT(M)
6.22/2.43	
6.22/2.43	The collapsing dependency pairs are DP_c:
6.22/2.43	   U11'(tt, N) -> N
6.22/2.43	   U21'(tt, M, N) -> N
6.22/2.43	   U21'(tt, M, N) -> M
6.22/2.43	   U41'(tt, M, N) -> N
6.22/2.43	   U41'(tt, M, N) -> M
6.22/2.43	   AND(tt, X) -> X
6.22/2.43	
6.22/2.43	
6.22/2.43	The hidden terms of R are:
6.22/2.43	
6.22/2.43	   isNat(x0)
6.22/2.43	
6.22/2.43	Every hiding context is built from:none
6.22/2.43	
6.22/2.43	Hence, the new unhiding pairs DP_u are :
6.22/2.43	   U11'(tt, N) -> U(N)
6.22/2.43	   U21'(tt, M, N) -> U(N)
6.22/2.43	   U21'(tt, M, N) -> U(M)
6.22/2.43	   U41'(tt, M, N) -> U(N)
6.22/2.43	   U41'(tt, M, N) -> U(M)
6.22/2.43	   AND(tt, X) -> U(X)
6.22/2.43	   U(isNat(x0)) -> ISNAT(x0)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(5) QCSDependencyGraphProof (EQUIVALENT)
6.22/2.43	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 14 less nodes.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(6)
6.22/2.43	Complex Obligation (AND)
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(7)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, AND_2} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1, U_1, ISNAT_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The TRS P consists of the following rules:
6.22/2.43	
6.22/2.43	   AND(tt, X) -> U(X)
6.22/2.43	   U(isNat(x0)) -> ISNAT(x0)
6.22/2.43	   ISNAT(plus(V1, V2)) -> AND(isNat(V1), isNat(V2))
6.22/2.43	   ISNAT(plus(V1, V2)) -> ISNAT(V1)
6.22/2.43	   ISNAT(s(V1)) -> ISNAT(V1)
6.22/2.43	   ISNAT(x(V1, V2)) -> AND(isNat(V1), isNat(V2))
6.22/2.43	   ISNAT(x(V1, V2)) -> ISNAT(V1)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(8) QCSDPReductionPairProof (EQUIVALENT)
6.22/2.43	Using the order
6.22/2.43	
6.22/2.43	AND/2)NO,YES(
6.22/2.43	tt/0)
6.22/2.43	U/1)YES(
6.22/2.43	isNat/1(YES)
6.22/2.43	ISNAT/1(YES)
6.22/2.43	plus/2(YES,YES)
6.22/2.43	s/1(YES)
6.22/2.43	x/2(YES,YES)
6.22/2.43	0/0)
6.22/2.43	and/2)NO,YES(
6.22/2.43	U11/2(YES,YES)
6.22/2.43	U21/3(YES,YES,YES)
6.22/2.43	U31/1(NO)
6.22/2.43	U41/3(YES,YES,YES)
6.22/2.43	
6.22/2.43	Quasi precedence:
6.22/2.43	[x_2, 0, U31, U41_3] > tt > [plus_2, U21_3] > s_1 > [isNat_1, ISNAT_1] > U11_2
6.22/2.43	
6.22/2.43	
6.22/2.43	Status:
6.22/2.43	tt: multiset status
6.22/2.43	isNat_1: multiset status
6.22/2.43	ISNAT_1: multiset status
6.22/2.43	plus_2: [1,2]
6.22/2.43	s_1: [1]
6.22/2.43	x_2: [2,1]
6.22/2.43	0: multiset status
6.22/2.43	U11_2: [1,2]
6.22/2.43	U21_3: [3,2,1]
6.22/2.43	U31: []
6.22/2.43	U41_3: [2,3,1]
6.22/2.43	
6.22/2.43	
6.22/2.43	
6.22/2.43	the following usable rules
6.22/2.43	
6.22/2.43	
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	
6.22/2.43	
6.22/2.43	could all be oriented weakly.
6.22/2.43	
6.22/2.43	Furthermore, the pairs
6.22/2.43	
6.22/2.43	
6.22/2.43	   ISNAT(plus(V1, V2)) -> AND(isNat(V1), isNat(V2))
6.22/2.43	   ISNAT(plus(V1, V2)) -> ISNAT(V1)
6.22/2.43	   ISNAT(s(V1)) -> ISNAT(V1)
6.22/2.43	   ISNAT(x(V1, V2)) -> AND(isNat(V1), isNat(V2))
6.22/2.43	   ISNAT(x(V1, V2)) -> ISNAT(V1)
6.22/2.43	
6.22/2.43	
6.22/2.43	could be oriented strictly and thus removed by the CS-Reduction Pair Processor [LPAR08,DA_EMMES].
6.22/2.43	
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(9)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, AND_2} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1, U_1, ISNAT_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The TRS P consists of the following rules:
6.22/2.43	
6.22/2.43	   AND(tt, X) -> U(X)
6.22/2.43	   U(isNat(x0)) -> ISNAT(x0)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(10) QCSDependencyGraphProof (EQUIVALENT)
6.22/2.43	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(11)
6.22/2.43	TRUE
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(12)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2, PLUS_2} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, U21'_3} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The TRS P consists of the following rules:
6.22/2.43	
6.22/2.43	   PLUS(N, s(M)) -> U21'(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   U21'(tt, M, N) -> PLUS(N, M)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(13) QCSDPSubtermProof (EQUIVALENT)
6.22/2.43	We use the subterm processor [DA_EMMES].
6.22/2.43	
6.22/2.43	
6.22/2.43	The following pairs can be oriented strictly and are deleted.
6.22/2.43	
6.22/2.43	   PLUS(N, s(M)) -> U21'(and(isNat(M), isNat(N)), M, N)
6.22/2.43	The remaining pairs can at least be oriented weakly.
6.22/2.43	
6.22/2.43	   U21'(tt, M, N) -> PLUS(N, M)
6.22/2.43	Used ordering:  Combined order from the following AFS and order.
6.22/2.43	U21'(x1, x2, x3)  =  x2
6.22/2.43	
6.22/2.43	PLUS(x1, x2)  =  x2
6.22/2.43	
6.22/2.43	
6.22/2.43	Subterm Order
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(14)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2, PLUS_2} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, U21'_3} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The TRS P consists of the following rules:
6.22/2.43	
6.22/2.43	   U21'(tt, M, N) -> PLUS(N, M)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(15) QCSDependencyGraphProof (EQUIVALENT)
6.22/2.43	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 1 less node.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(16)
6.22/2.43	TRUE
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(17)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2, X_2} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, U41'_3} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The TRS P consists of the following rules:
6.22/2.43	
6.22/2.43	   U41'(tt, M, N) -> X(N, M)
6.22/2.43	   X(N, s(M)) -> U41'(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(18) QCSDPSubtermProof (EQUIVALENT)
6.22/2.43	We use the subterm processor [DA_EMMES].
6.22/2.43	
6.22/2.43	
6.22/2.43	The following pairs can be oriented strictly and are deleted.
6.22/2.43	
6.22/2.43	   X(N, s(M)) -> U41'(and(isNat(M), isNat(N)), M, N)
6.22/2.43	The remaining pairs can at least be oriented weakly.
6.22/2.43	
6.22/2.43	   U41'(tt, M, N) -> X(N, M)
6.22/2.43	Used ordering:  Combined order from the following AFS and order.
6.22/2.43	X(x1, x2)  =  x2
6.22/2.43	
6.22/2.43	U41'(x1, x2, x3)  =  x2
6.22/2.43	
6.22/2.43	
6.22/2.43	Subterm Order
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(19)
6.22/2.43	Obligation:
6.22/2.43	Q-restricted context-sensitive dependency pair problem:
6.22/2.43	The symbols in {s_1, plus_2, U31_1, x_2, X_2} are replacing on all positions.
6.22/2.43	For all symbols f in {U11_2, U21_3, U41_3, and_2, U41'_3} we have mu(f) = {1}.
6.22/2.43	The symbols in {isNat_1} are not replacing on any position.
6.22/2.43	
6.22/2.43	The TRS P consists of the following rules:
6.22/2.43	
6.22/2.43	   U41'(tt, M, N) -> X(N, M)
6.22/2.43	
6.22/2.43	The TRS R consists of the following rules:
6.22/2.43	
6.22/2.43	   U11(tt, N) -> N
6.22/2.43	   U21(tt, M, N) -> s(plus(N, M))
6.22/2.43	   U31(tt) -> 0
6.22/2.43	   U41(tt, M, N) -> plus(x(N, M), N)
6.22/2.43	   and(tt, X) -> X
6.22/2.43	   isNat(0) -> tt
6.22/2.43	   isNat(plus(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   isNat(s(V1)) -> isNat(V1)
6.22/2.43	   isNat(x(V1, V2)) -> and(isNat(V1), isNat(V2))
6.22/2.43	   plus(N, 0) -> U11(isNat(N), N)
6.22/2.43	   plus(N, s(M)) -> U21(and(isNat(M), isNat(N)), M, N)
6.22/2.43	   x(N, 0) -> U31(isNat(N))
6.22/2.43	   x(N, s(M)) -> U41(and(isNat(M), isNat(N)), M, N)
6.22/2.43	
6.22/2.43	Q is empty.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(20) QCSDependencyGraphProof (EQUIVALENT)
6.22/2.43	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 1 less node.
6.22/2.43	
6.22/2.43	----------------------------------------
6.22/2.43	
6.22/2.43	(21)
6.22/2.43	TRUE
6.22/2.46	EOF