Termination w.r.t. Q proof of /tmp/tmp-4OdX3/PEANO_nokinds

Termination w.r.t. Q of the given QTRS could be proven:

0 QTRS

↳1 DependencyPairsProof (⇔)

↳2 QDP

↳3 DependencyGraphProof (⇔)

↳4 QDP

↳5 QDPSizeChangeProof (⇔)

↳6 TRUE

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

U11(tt, N) → activate(N)
U21(tt, M, N) → s(plus(activate(N), activate(M)))
and(tt, X) → activate(X)
isNat(n__0) → tt
isNat(n__plus(V1, V2)) → and(isNat(activate(V1)), n__isNat(activate(V2)))
isNat(n__s(V1)) → isNat(activate(V1))
plus(N, 0) → U11(isNat(N), N)
plus(N, s(M)) → U21(and(isNat(M), n__isNat(N)), M, N)
0 → n__0
plus(X1, X2) → n__plus(X1, X2)
isNat(X) → n__isNat(X)
s(X) → n__s(X)
activate(n__0) → 0
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2))
activate(n__isNat(X)) → isNat(X)
activate(n__s(X)) → s(activate(X))
activate(X) → X

Q is empty.

(1) DependencyPairsProof (EQUIVALENT transformation)

Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.

(2) Obligation:

Q DP problem:
The TRS P consists of the following rules:

U11¹(tt, N) → ACTIVATE(N)
U21¹(tt, M, N) → S(plus(activate(N), activate(M)))
U21¹(tt, M, N) → PLUS(activate(N), activate(M))
U21¹(tt, M, N) → ACTIVATE(N)
U21¹(tt, M, N) → ACTIVATE(M)
AND(tt, X) → ACTIVATE(X)
ISNAT(n__plus(V1, V2)) → AND(isNat(activate(V1)), n__isNat(activate(V2)))
ISNAT(n__plus(V1, V2)) → ISNAT(activate(V1))
ISNAT(n__plus(V1, V2)) → ACTIVATE(V1)
ISNAT(n__plus(V1, V2)) → ACTIVATE(V2)
ISNAT(n__s(V1)) → ISNAT(activate(V1))
ISNAT(n__s(V1)) → ACTIVATE(V1)
PLUS(N, 0) → U11¹(isNat(N), N)
PLUS(N, 0) → ISNAT(N)
PLUS(N, s(M)) → U21¹(and(isNat(M), n__isNat(N)), M, N)
PLUS(N, s(M)) → AND(isNat(M), n__isNat(N))
PLUS(N, s(M)) → ISNAT(M)
ACTIVATE(n__0) → 0¹
ACTIVATE(n__plus(X1, X2)) → PLUS(activate(X1), activate(X2))
ACTIVATE(n__plus(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__plus(X1, X2)) → ACTIVATE(X2)
ACTIVATE(n__isNat(X)) → ISNAT(X)
ACTIVATE(n__s(X)) → S(activate(X))
ACTIVATE(n__s(X)) → ACTIVATE(X)

The TRS R consists of the following rules:

U11(tt, N) → activate(N)
U21(tt, M, N) → s(plus(activate(N), activate(M)))
and(tt, X) → activate(X)
isNat(n__0) → tt
isNat(n__plus(V1, V2)) → and(isNat(activate(V1)), n__isNat(activate(V2)))
isNat(n__s(V1)) → isNat(activate(V1))
plus(N, 0) → U11(isNat(N), N)
plus(N, s(M)) → U21(and(isNat(M), n__isNat(N)), M, N)
0 → n__0
plus(X1, X2) → n__plus(X1, X2)
isNat(X) → n__isNat(X)
s(X) → n__s(X)
activate(n__0) → 0
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2))
activate(n__isNat(X)) → isNat(X)
activate(n__s(X)) → s(activate(X))
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(3) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 1 SCC with 3 less nodes.

(4) Obligation:

Q DP problem:
The TRS P consists of the following rules:

ACTIVATE(n__plus(X1, X2)) → PLUS(activate(X1), activate(X2))
PLUS(N, 0) → U11¹(isNat(N), N)
U11¹(tt, N) → ACTIVATE(N)
ACTIVATE(n__plus(X1, X2)) → ACTIVATE(X1)
ACTIVATE(n__plus(X1, X2)) → ACTIVATE(X2)
ACTIVATE(n__isNat(X)) → ISNAT(X)
ISNAT(n__plus(V1, V2)) → AND(isNat(activate(V1)), n__isNat(activate(V2)))
AND(tt, X) → ACTIVATE(X)
ACTIVATE(n__s(X)) → ACTIVATE(X)
ISNAT(n__plus(V1, V2)) → ISNAT(activate(V1))
ISNAT(n__plus(V1, V2)) → ACTIVATE(V1)
ISNAT(n__plus(V1, V2)) → ACTIVATE(V2)
ISNAT(n__s(V1)) → ISNAT(activate(V1))
ISNAT(n__s(V1)) → ACTIVATE(V1)
PLUS(N, 0) → ISNAT(N)
PLUS(N, s(M)) → U21¹(and(isNat(M), n__isNat(N)), M, N)
U21¹(tt, M, N) → PLUS(activate(N), activate(M))
PLUS(N, s(M)) → AND(isNat(M), n__isNat(N))
PLUS(N, s(M)) → ISNAT(M)
U21¹(tt, M, N) → ACTIVATE(N)
U21¹(tt, M, N) → ACTIVATE(M)

The TRS R consists of the following rules:

U11(tt, N) → activate(N)
U21(tt, M, N) → s(plus(activate(N), activate(M)))
and(tt, X) → activate(X)
isNat(n__0) → tt
isNat(n__plus(V1, V2)) → and(isNat(activate(V1)), n__isNat(activate(V2)))
isNat(n__s(V1)) → isNat(activate(V1))
plus(N, 0) → U11(isNat(N), N)
plus(N, s(M)) → U21(and(isNat(M), n__isNat(N)), M, N)
0 → n__0
plus(X1, X2) → n__plus(X1, X2)
isNat(X) → n__isNat(X)
s(X) → n__s(X)
activate(n__0) → 0
activate(n__plus(X1, X2)) → plus(activate(X1), activate(X2))
activate(n__isNat(X)) → isNat(X)
activate(n__s(X)) → s(activate(X))
activate(X) → X

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(5) QDPSizeChangeProof (EQUIVALENT transformation)

We used the following order and afs together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem.

Order:Combined order from the following AFS and order.
activate(x1) = x1
n__0 = n__0
0 = 0
n__plus(x1, x2) = n__plus(x1, x2)
plus(x1, x2) = plus(x1, x2)
U11(x1, x2) = U11(x1, x2)
isNat(x1) = x1
tt = tt
n__isNat(x1) = x1
and(x1, x2) = and(x2)
n__s(x1) = n__s(x1)
s(x1) = s(x1)
U21(x1, x2, x3) = U21(x1, x2, x3)

Lexicographic path order with status [LPO].
Quasi-Precedence:

[n_₀, 0] > U11₂ > and₁
[n_₀, 0] > tt > and₁
[n_{_plus₂}, plus₂, U21₃] > U11₂ > and₁
[n_{_plus₂}, plus₂, U21₃] > [n_{_s₁}, s₁] > and₁

Status:

n_₀: []
0: []
n_{_plus₂}: [2,1]
plus₂: [2,1]
U11₂: [1,2]
tt: []
and₁: [1]
n_{_s₁}: [1]
s₁: [1]
U21₃: [2,3,1]

AFS:
activate(x1) = x1
n__0 = n__0
0 = 0
n__plus(x1, x2) = n__plus(x1, x2)
plus(x1, x2) = plus(x1, x2)
U11(x1, x2) = U11(x1, x2)
isNat(x1) = x1
tt = tt
n__isNat(x1) = x1
and(x1, x2) = and(x2)
n__s(x1) = n__s(x1)
s(x1) = s(x1)
U21(x1, x2, x3) = U21(x1, x2, x3)

From the DPs we obtained the following set of size-change graphs:

U11¹(tt, N) → ACTIVATE(N) (allowed arguments on rhs = {1})
The graph contains the following edges 2 >= 1
PLUS(N, 0) → U11¹(isNat(N), N) (allowed arguments on rhs = {2})
The graph contains the following edges 1 >= 2
ACTIVATE(n__plus(X1, X2)) → PLUS(activate(X1), activate(X2)) (allowed arguments on rhs = {1, 2})
The graph contains the following edges 1 > 1, 1 > 2
U21¹(tt, M, N) → PLUS(activate(N), activate(M)) (allowed arguments on rhs = {1, 2})
The graph contains the following edges 3 >= 1, 2 >= 2
ACTIVATE(n__isNat(X)) → ISNAT(X) (allowed arguments on rhs = {1})
The graph contains the following edges 1 >= 1
AND(tt, X) → ACTIVATE(X) (allowed arguments on rhs = {1})
The graph contains the following edges 2 >= 1
ISNAT(n__plus(V1, V2)) → AND(isNat(activate(V1)), n__isNat(activate(V2))) (allowed arguments on rhs = {2})
The graph contains the following edges 1 > 2
PLUS(N, s(M)) → AND(isNat(M), n__isNat(N)) (allowed arguments on rhs = {2})
The graph contains the following edges 1 >= 2
PLUS(N, s(M)) → U21¹(and(isNat(M), n__isNat(N)), M, N) (allowed arguments on rhs = {2, 3})
The graph contains the following edges 2 > 2, 1 >= 3
PLUS(N, 0) → ISNAT(N) (allowed arguments on rhs = {1})
The graph contains the following edges 1 >= 1
PLUS(N, s(M)) → ISNAT(M) (allowed arguments on rhs = {1})
The graph contains the following edges 2 > 1
ACTIVATE(n__plus(X1, X2)) → ACTIVATE(X1) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
ACTIVATE(n__plus(X1, X2)) → ACTIVATE(X2) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
ACTIVATE(n__s(X)) → ACTIVATE(X) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
ISNAT(n__plus(V1, V2)) → ACTIVATE(V1) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
ISNAT(n__plus(V1, V2)) → ACTIVATE(V2) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
ISNAT(n__s(V1)) → ACTIVATE(V1) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
U21¹(tt, M, N) → ACTIVATE(N) (allowed arguments on rhs = {1})
The graph contains the following edges 3 >= 1
U21¹(tt, M, N) → ACTIVATE(M) (allowed arguments on rhs = {1})
The graph contains the following edges 2 >= 1
ISNAT(n__plus(V1, V2)) → ISNAT(activate(V1)) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
ISNAT(n__s(V1)) → ISNAT(activate(V1)) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1

We oriented the following set of usable rules [AAECC05,FROCOS05].