3.85/1.71	YES
3.85/1.73	proof of /export/starexec/sandbox/benchmark/theBenchmark.xml
3.85/1.73	# AProVE Commit ID: 48fb2092695e11cc9f56e44b17a92a5f88ffb256 marcel 20180622 unpublished dirty
3.85/1.73	
3.85/1.73	
3.85/1.73	Termination of the given CSR could be proven:
3.85/1.73	
3.85/1.73	(0) CSR
3.85/1.73	(1) CSDependencyPairsProof [EQUIVALENT, 51 ms]
3.85/1.73	(2) QCSDP
3.85/1.73	(3) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.85/1.73	(4) AND
3.85/1.73	    (5) QCSDP
3.85/1.73	        (6) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.85/1.73	        (7) QCSDP
3.85/1.73	        (8) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.85/1.73	        (9) TRUE
3.85/1.73	    (10) QCSDP
3.85/1.73	        (11) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.85/1.73	        (12) QCSDP
3.85/1.73	        (13) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.85/1.73	        (14) TRUE
3.85/1.73	    (15) QCSDP
3.85/1.73	        (16) QCSDPSubtermProof [EQUIVALENT, 0 ms]
3.85/1.73	        (17) QCSDP
3.85/1.73	        (18) QCSDependencyGraphProof [EQUIVALENT, 0 ms]
3.85/1.73	        (19) TRUE
3.85/1.73	
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(0)
3.85/1.73	Obligation:
3.85/1.73	Context-sensitive rewrite system:
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	The replacement map contains the following entries:
3.85/1.73	
3.85/1.73	U11: {1}
3.85/1.73	tt: empty set
3.85/1.73	U12: {1}
3.85/1.73	isNat: empty set
3.85/1.73	U21: {1}
3.85/1.73	U31: {1}
3.85/1.73	U32: {1}
3.85/1.73	U41: {1}
3.85/1.73	U51: {1}
3.85/1.73	U52: {1}
3.85/1.73	s: {1}
3.85/1.73	plus: {1, 2}
3.85/1.73	U61: {1}
3.85/1.73	0: empty set
3.85/1.73	U71: {1}
3.85/1.73	U72: {1}
3.85/1.73	x: {1, 2}
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(1) CSDependencyPairsProof (EQUIVALENT)
3.85/1.73	Using Improved CS-DPs [LPAR08] we result in the following initial Q-CSDP problem.
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(2)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2, U12'_1, U32'_1, PLUS_2, X_2, U21'_1, U61'_1} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U11'_2, U31'_2, U52'_3, U51'_3, U72'_3, U71'_3, U41'_2} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1, ISNAT_1, U_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The ordinary context-sensitive dependency pairs DP_o are:
3.85/1.73	   U11'(tt, V2) -> U12'(isNat(V2))
3.85/1.73	   U11'(tt, V2) -> ISNAT(V2)
3.85/1.73	   U31'(tt, V2) -> U32'(isNat(V2))
3.85/1.73	   U31'(tt, V2) -> ISNAT(V2)
3.85/1.73	   U51'(tt, M, N) -> U52'(isNat(N), M, N)
3.85/1.73	   U51'(tt, M, N) -> ISNAT(N)
3.85/1.73	   U52'(tt, M, N) -> PLUS(N, M)
3.85/1.73	   U71'(tt, M, N) -> U72'(isNat(N), M, N)
3.85/1.73	   U71'(tt, M, N) -> ISNAT(N)
3.85/1.73	   U72'(tt, M, N) -> PLUS(x(N, M), N)
3.85/1.73	   U72'(tt, M, N) -> X(N, M)
3.85/1.73	   ISNAT(plus(V1, V2)) -> U11'(isNat(V1), V2)
3.85/1.73	   ISNAT(plus(V1, V2)) -> ISNAT(V1)
3.85/1.73	   ISNAT(s(V1)) -> U21'(isNat(V1))
3.85/1.73	   ISNAT(s(V1)) -> ISNAT(V1)
3.85/1.73	   ISNAT(x(V1, V2)) -> U31'(isNat(V1), V2)
3.85/1.73	   ISNAT(x(V1, V2)) -> ISNAT(V1)
3.85/1.73	   PLUS(N, 0) -> U41'(isNat(N), N)
3.85/1.73	   PLUS(N, 0) -> ISNAT(N)
3.85/1.73	   PLUS(N, s(M)) -> U51'(isNat(M), M, N)
3.85/1.73	   PLUS(N, s(M)) -> ISNAT(M)
3.85/1.73	   X(N, 0) -> U61'(isNat(N))
3.85/1.73	   X(N, 0) -> ISNAT(N)
3.85/1.73	   X(N, s(M)) -> U71'(isNat(M), M, N)
3.85/1.73	   X(N, s(M)) -> ISNAT(M)
3.85/1.73	
3.85/1.73	The collapsing dependency pairs are DP_c:
3.85/1.73	   U41'(tt, N) -> N
3.85/1.73	   U52'(tt, M, N) -> N
3.85/1.73	   U52'(tt, M, N) -> M
3.85/1.73	   U72'(tt, M, N) -> N
3.85/1.73	   U72'(tt, M, N) -> M
3.85/1.73	
3.85/1.73	
3.85/1.73	The hidden terms of R are:
3.85/1.73	none
3.85/1.73	
3.85/1.73	Every hiding context is built from:none
3.85/1.73	
3.85/1.73	Hence, the new unhiding pairs DP_u are :
3.85/1.73	   U41'(tt, N) -> U(N)
3.85/1.73	   U52'(tt, M, N) -> U(N)
3.85/1.73	   U52'(tt, M, N) -> U(M)
3.85/1.73	   U72'(tt, M, N) -> U(N)
3.85/1.73	   U72'(tt, M, N) -> U(M)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(3) QCSDependencyGraphProof (EQUIVALENT)
3.85/1.73	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 3 SCCs with 17 less nodes.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(4)
3.85/1.73	Complex Obligation (AND)
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(5)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U11'_2, U31'_2} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1, ISNAT_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The TRS P consists of the following rules:
3.85/1.73	
3.85/1.73	   ISNAT(plus(V1, V2)) -> U11'(isNat(V1), V2)
3.85/1.73	   U11'(tt, V2) -> ISNAT(V2)
3.85/1.73	   ISNAT(plus(V1, V2)) -> ISNAT(V1)
3.85/1.73	   ISNAT(s(V1)) -> ISNAT(V1)
3.85/1.73	   ISNAT(x(V1, V2)) -> U31'(isNat(V1), V2)
3.85/1.73	   U31'(tt, V2) -> ISNAT(V2)
3.85/1.73	   ISNAT(x(V1, V2)) -> ISNAT(V1)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(6) QCSDPSubtermProof (EQUIVALENT)
3.85/1.73	We use the subterm processor [DA_EMMES].
3.85/1.73	
3.85/1.73	
3.85/1.73	The following pairs can be oriented strictly and are deleted.
3.85/1.73	
3.85/1.73	   ISNAT(plus(V1, V2)) -> U11'(isNat(V1), V2)
3.85/1.73	   ISNAT(plus(V1, V2)) -> ISNAT(V1)
3.85/1.73	   ISNAT(s(V1)) -> ISNAT(V1)
3.85/1.73	   ISNAT(x(V1, V2)) -> U31'(isNat(V1), V2)
3.85/1.73	   ISNAT(x(V1, V2)) -> ISNAT(V1)
3.85/1.73	The remaining pairs can at least be oriented weakly.
3.85/1.73	
3.85/1.73	   U11'(tt, V2) -> ISNAT(V2)
3.85/1.73	   U31'(tt, V2) -> ISNAT(V2)
3.85/1.73	Used ordering:  Combined order from the following AFS and order.
3.85/1.73	U11'(x1, x2)  =  x2
3.85/1.73	
3.85/1.73	ISNAT(x1)  =  x1
3.85/1.73	
3.85/1.73	U31'(x1, x2)  =  x2
3.85/1.73	
3.85/1.73	
3.85/1.73	Subterm Order
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(7)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U11'_2, U31'_2} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1, ISNAT_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The TRS P consists of the following rules:
3.85/1.73	
3.85/1.73	   U11'(tt, V2) -> ISNAT(V2)
3.85/1.73	   U31'(tt, V2) -> ISNAT(V2)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(8) QCSDependencyGraphProof (EQUIVALENT)
3.85/1.73	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(9)
3.85/1.73	TRUE
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(10)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2, PLUS_2} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U52'_3, U51'_3} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The TRS P consists of the following rules:
3.85/1.73	
3.85/1.73	   U51'(tt, M, N) -> U52'(isNat(N), M, N)
3.85/1.73	   U52'(tt, M, N) -> PLUS(N, M)
3.85/1.73	   PLUS(N, s(M)) -> U51'(isNat(M), M, N)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(11) QCSDPSubtermProof (EQUIVALENT)
3.85/1.73	We use the subterm processor [DA_EMMES].
3.85/1.73	
3.85/1.73	
3.85/1.73	The following pairs can be oriented strictly and are deleted.
3.85/1.73	
3.85/1.73	   PLUS(N, s(M)) -> U51'(isNat(M), M, N)
3.85/1.73	The remaining pairs can at least be oriented weakly.
3.85/1.73	
3.85/1.73	   U51'(tt, M, N) -> U52'(isNat(N), M, N)
3.85/1.73	   U52'(tt, M, N) -> PLUS(N, M)
3.85/1.73	Used ordering:  Combined order from the following AFS and order.
3.85/1.73	U52'(x1, x2, x3)  =  x2
3.85/1.73	
3.85/1.73	U51'(x1, x2, x3)  =  x2
3.85/1.73	
3.85/1.73	PLUS(x1, x2)  =  x2
3.85/1.73	
3.85/1.73	
3.85/1.73	Subterm Order
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(12)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2, PLUS_2} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U52'_3, U51'_3} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The TRS P consists of the following rules:
3.85/1.73	
3.85/1.73	   U51'(tt, M, N) -> U52'(isNat(N), M, N)
3.85/1.73	   U52'(tt, M, N) -> PLUS(N, M)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(13) QCSDependencyGraphProof (EQUIVALENT)
3.85/1.73	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(14)
3.85/1.73	TRUE
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(15)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2, X_2} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U72'_3, U71'_3} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The TRS P consists of the following rules:
3.85/1.73	
3.85/1.73	   U72'(tt, M, N) -> X(N, M)
3.85/1.73	   X(N, s(M)) -> U71'(isNat(M), M, N)
3.85/1.73	   U71'(tt, M, N) -> U72'(isNat(N), M, N)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(16) QCSDPSubtermProof (EQUIVALENT)
3.85/1.73	We use the subterm processor [DA_EMMES].
3.85/1.73	
3.85/1.73	
3.85/1.73	The following pairs can be oriented strictly and are deleted.
3.85/1.73	
3.85/1.73	   X(N, s(M)) -> U71'(isNat(M), M, N)
3.85/1.73	The remaining pairs can at least be oriented weakly.
3.85/1.73	
3.85/1.73	   U72'(tt, M, N) -> X(N, M)
3.85/1.73	   U71'(tt, M, N) -> U72'(isNat(N), M, N)
3.85/1.73	Used ordering:  Combined order from the following AFS and order.
3.85/1.73	X(x1, x2)  =  x2
3.85/1.73	
3.85/1.73	U72'(x1, x2, x3)  =  x2
3.85/1.73	
3.85/1.73	U71'(x1, x2, x3)  =  x2
3.85/1.73	
3.85/1.73	
3.85/1.73	Subterm Order
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(17)
3.85/1.73	Obligation:
3.85/1.73	Q-restricted context-sensitive dependency pair problem:
3.85/1.73	The symbols in {U12_1, U21_1, U32_1, s_1, plus_2, U61_1, x_2, X_2} are replacing on all positions.
3.85/1.73	For all symbols f in {U11_2, U31_2, U41_2, U51_3, U52_3, U71_3, U72_3, U72'_3, U71'_3} we have mu(f) = {1}.
3.85/1.73	The symbols in {isNat_1} are not replacing on any position.
3.85/1.73	
3.85/1.73	The TRS P consists of the following rules:
3.85/1.73	
3.85/1.73	   U72'(tt, M, N) -> X(N, M)
3.85/1.73	   U71'(tt, M, N) -> U72'(isNat(N), M, N)
3.85/1.73	
3.85/1.73	The TRS R consists of the following rules:
3.85/1.73	
3.85/1.73	   U11(tt, V2) -> U12(isNat(V2))
3.85/1.73	   U12(tt) -> tt
3.85/1.73	   U21(tt) -> tt
3.85/1.73	   U31(tt, V2) -> U32(isNat(V2))
3.85/1.73	   U32(tt) -> tt
3.85/1.73	   U41(tt, N) -> N
3.85/1.73	   U51(tt, M, N) -> U52(isNat(N), M, N)
3.85/1.73	   U52(tt, M, N) -> s(plus(N, M))
3.85/1.73	   U61(tt) -> 0
3.85/1.73	   U71(tt, M, N) -> U72(isNat(N), M, N)
3.85/1.73	   U72(tt, M, N) -> plus(x(N, M), N)
3.85/1.73	   isNat(0) -> tt
3.85/1.73	   isNat(plus(V1, V2)) -> U11(isNat(V1), V2)
3.85/1.73	   isNat(s(V1)) -> U21(isNat(V1))
3.85/1.73	   isNat(x(V1, V2)) -> U31(isNat(V1), V2)
3.85/1.73	   plus(N, 0) -> U41(isNat(N), N)
3.85/1.73	   plus(N, s(M)) -> U51(isNat(M), M, N)
3.85/1.73	   x(N, 0) -> U61(isNat(N))
3.85/1.73	   x(N, s(M)) -> U71(isNat(M), M, N)
3.85/1.73	
3.85/1.73	Q is empty.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(18) QCSDependencyGraphProof (EQUIVALENT)
3.85/1.73	The approximation of the Context-Sensitive Dependency Graph [LPAR08] contains 0 SCCs with 2 less nodes.
3.85/1.73	
3.85/1.73	----------------------------------------
3.85/1.73	
3.85/1.73	(19)
3.85/1.73	TRUE
3.85/1.76	EOF