Termination Proof using AProVE

Term Rewriting System R:
[N, X, Y, X1, X2, Z]
a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

A_{_TERMS}(N) -> A_{_SQR}(mark(N))
A_{_TERMS}(N) -> MARK(N)
A_{_ADD}(0, X) -> MARK(X)
A_{_FIRST}(s(X), cons(Y, Z)) -> MARK(Y)
MARK(terms(X)) -> A_{_TERMS}(mark(X))
MARK(terms(X)) -> MARK(X)
MARK(sqr(X)) -> A_{_SQR}(mark(X))
MARK(sqr(X)) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(add(X1, X2)) -> MARK(X1)
MARK(add(X1, X2)) -> MARK(X2)
MARK(dbl(X)) -> A_{_DBL}(mark(X))
MARK(dbl(X)) -> MARK(X)
MARK(first(X1, X2)) -> A_{_FIRST}(mark(X1), mark(X2))
MARK(first(X1, X2)) -> MARK(X1)
MARK(first(X1, X2)) -> MARK(X2)
MARK(cons(X1, X2)) -> MARK(X1)
MARK(recip(X)) -> MARK(X)

Furthermore, R contains one SCC.

     ↳DPs

       →DP Problem 1

         ↳Negative Polynomial Order

Dependency Pairs:

MARK(recip(X)) -> MARK(X)
MARK(cons(X1, X2)) -> MARK(X1)
MARK(first(X1, X2)) -> MARK(X2)
MARK(first(X1, X2)) -> MARK(X1)
A_{_FIRST}(s(X), cons(Y, Z)) -> MARK(Y)
MARK(first(X1, X2)) -> A_{_FIRST}(mark(X1), mark(X2))
MARK(dbl(X)) -> MARK(X)
MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)
MARK(terms(X)) -> MARK(X)
MARK(terms(X)) -> A_{_TERMS}(mark(X))
A_{_TERMS}(N) -> MARK(N)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

The following Dependency Pairs can be strictly oriented using the given order.

MARK(recip(X)) -> MARK(X)
MARK(terms(X)) -> MARK(X)
MARK(terms(X)) -> A_{_TERMS}(mark(X))

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil
a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)

Used ordering:
Polynomial Order with Interpretation:

POL( MARK(x₁) ) = x₁

POL( recip(x₁) ) = x₁ + 1

POL( first(x₁, x₂) ) = x₁ + x₂

POL( A_{_ADD}(x₁, x₂) ) = x₂

POL( add(x₁, x₂) ) = x₁ + x₂

POL( mark(x₁) ) = x₁

POL( A_{_TERMS}(x₁) ) = x₁

POL( A_{_FIRST}(x₁, x₂) ) = x₂

POL( cons(x₁, x₂) ) = x₁

POL( dbl(x₁) ) = x₁

POL( terms(x₁) ) = x₁ + 1

POL( sqr(x₁) ) = x₁

POL( a_{_terms}(x₁) ) = x₁ + 1

POL( a_{_sqr}(x₁) ) = x₁

POL( a_{_add}(x₁, x₂) ) = x₁ + x₂

POL( a_{_dbl}(x₁) ) = x₁

POL( a_{_first}(x₁, x₂) ) = x₁ + x₂

POL( s(x₁) ) = 0

POL( 0 ) = 0

POL( nil ) = 0

This results in one new DP problem.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳Dependency Graph

Dependency Pairs:

MARK(cons(X1, X2)) -> MARK(X1)
MARK(first(X1, X2)) -> MARK(X2)
MARK(first(X1, X2)) -> MARK(X1)
A_{_FIRST}(s(X), cons(Y, Z)) -> MARK(Y)
MARK(first(X1, X2)) -> A_{_FIRST}(mark(X1), mark(X2))
MARK(dbl(X)) -> MARK(X)
MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)
A_{_TERMS}(N) -> MARK(N)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

Using the Dependency Graph the DP problem was split into 1 DP problems.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 3

                 ↳Negative Polynomial Order

Dependency Pairs:

MARK(first(X1, X2)) -> MARK(X2)
MARK(first(X1, X2)) -> MARK(X1)
A_{_FIRST}(s(X), cons(Y, Z)) -> MARK(Y)
MARK(first(X1, X2)) -> A_{_FIRST}(mark(X1), mark(X2))
MARK(dbl(X)) -> MARK(X)
MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)
MARK(cons(X1, X2)) -> MARK(X1)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

The following Dependency Pairs can be strictly oriented using the given order.

MARK(first(X1, X2)) -> MARK(X2)
MARK(first(X1, X2)) -> MARK(X1)
MARK(first(X1, X2)) -> A_{_FIRST}(mark(X1), mark(X2))

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil
a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)

Used ordering:
Polynomial Order with Interpretation:

POL( MARK(x₁) ) = x₁

POL( first(x₁, x₂) ) = x₁ + x₂ + 1

POL( add(x₁, x₂) ) = x₁ + x₂

POL( A_{_ADD}(x₁, x₂) ) = x₂

POL( mark(x₁) ) = x₁

POL( cons(x₁, x₂) ) = x₁

POL( A_{_FIRST}(x₁, x₂) ) = x₂

POL( dbl(x₁) ) = x₁

POL( sqr(x₁) ) = x₁

POL( terms(x₁) ) = 0

POL( a_{_terms}(x₁) ) = 0

POL( a_{_sqr}(x₁) ) = x₁

POL( a_{_add}(x₁, x₂) ) = x₁ + x₂

POL( a_{_dbl}(x₁) ) = x₁

POL( a_{_first}(x₁, x₂) ) = x₁ + x₂ + 1

POL( recip(x₁) ) = 0

POL( s(x₁) ) = 0

POL( 0 ) = 0

POL( nil ) = 0

This results in one new DP problem.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 4

                 ↳Dependency Graph

Dependency Pairs:

A_{_FIRST}(s(X), cons(Y, Z)) -> MARK(Y)
MARK(dbl(X)) -> MARK(X)
MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)
MARK(cons(X1, X2)) -> MARK(X1)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

Using the Dependency Graph the DP problem was split into 1 DP problems.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 5

                 ↳Negative Polynomial Order

Dependency Pairs:

MARK(cons(X1, X2)) -> MARK(X1)
MARK(dbl(X)) -> MARK(X)
MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

The following Dependency Pair can be strictly oriented using the given order.

MARK(cons(X1, X2)) -> MARK(X1)

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil
a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)

Used ordering:
Polynomial Order with Interpretation:

POL( MARK(x₁) ) = x₁

POL( cons(x₁, x₂) ) = x₁ + 1

POL( A_{_ADD}(x₁, x₂) ) = x₂

POL( add(x₁, x₂) ) = x₁ + x₂

POL( mark(x₁) ) = x₁

POL( dbl(x₁) ) = x₁

POL( sqr(x₁) ) = x₁

POL( terms(x₁) ) = 1

POL( a_{_terms}(x₁) ) = 1

POL( a_{_sqr}(x₁) ) = x₁

POL( a_{_add}(x₁, x₂) ) = x₁ + x₂

POL( a_{_dbl}(x₁) ) = x₁

POL( first(x₁, x₂) ) = x₂

POL( a_{_first}(x₁, x₂) ) = x₂

POL( recip(x₁) ) = 0

POL( s(x₁) ) = 0

POL( 0 ) = 0

POL( nil ) = 0

This results in one new DP problem.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 6

                 ↳Negative Polynomial Order

Dependency Pairs:

MARK(dbl(X)) -> MARK(X)
MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

The following Dependency Pair can be strictly oriented using the given order.

MARK(dbl(X)) -> MARK(X)

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil
a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)

Used ordering:
Polynomial Order with Interpretation:

POL( MARK(x₁) ) = x₁

POL( dbl(x₁) ) = x₁ + 1

POL( add(x₁, x₂) ) = x₁ + x₂

POL( A_{_ADD}(x₁, x₂) ) = x₂

POL( mark(x₁) ) = x₁

POL( sqr(x₁) ) = x₁

POL( terms(x₁) ) = 0

POL( a_{_terms}(x₁) ) = 0

POL( a_{_sqr}(x₁) ) = x₁

POL( a_{_add}(x₁, x₂) ) = x₁ + x₂

POL( a_{_dbl}(x₁) ) = x₁ + 1

POL( first(x₁, x₂) ) = 0

POL( a_{_first}(x₁, x₂) ) = 0

POL( cons(x₁, x₂) ) = 0

POL( recip(x₁) ) = 0

POL( s(x₁) ) = 0

POL( 0 ) = 0

POL( nil ) = 0

This results in one new DP problem.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 7

                 ↳Negative Polynomial Order

Dependency Pairs:

MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
A_{_ADD}(0, X) -> MARK(X)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))
MARK(sqr(X)) -> MARK(X)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

The following Dependency Pairs can be strictly oriented using the given order.

MARK(add(X1, X2)) -> MARK(X2)
MARK(add(X1, X2)) -> MARK(X1)
MARK(add(X1, X2)) -> A_{_ADD}(mark(X1), mark(X2))

Moreover, the following usable rules (regarding the implicit AFS) are oriented.

mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil
a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)

Used ordering:
Polynomial Order with Interpretation:

POL( MARK(x₁) ) = x₁

POL( add(x₁, x₂) ) = x₁ + x₂ + 1

POL( A_{_ADD}(x₁, x₂) ) = x₂

POL( mark(x₁) ) = x₁

POL( sqr(x₁) ) = x₁

POL( terms(x₁) ) = 0

POL( a_{_terms}(x₁) ) = 0

POL( a_{_sqr}(x₁) ) = x₁

POL( a_{_add}(x₁, x₂) ) = x₁ + x₂ + 1

POL( dbl(x₁) ) = 0

POL( a_{_dbl}(x₁) ) = 0

POL( first(x₁, x₂) ) = 0

POL( a_{_first}(x₁, x₂) ) = 0

POL( cons(x₁, x₂) ) = 0

POL( recip(x₁) ) = 0

POL( s(x₁) ) = 0

POL( 0 ) = 0

POL( nil ) = 0

This results in one new DP problem.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 8

                 ↳Dependency Graph

Dependency Pairs:

A_{_ADD}(0, X) -> MARK(X)
MARK(sqr(X)) -> MARK(X)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

Using the Dependency Graph the DP problem was split into 1 DP problems.

     ↳DPs

       →DP Problem 1

         ↳Neg POLO

           →DP Problem 2

             ↳DGraph

...

               →DP Problem 9

                 ↳Size-Change Principle

Dependency Pair:

MARK(sqr(X)) -> MARK(X)

Rules:

a_{_terms}(N) -> cons(recip(a_{_sqr}(mark(N))), terms(s(N)))
a_{_terms}(X) -> terms(X)
a_{_sqr}(0) -> 0
a_{_sqr}(s(X)) -> s(add(sqr(X), dbl(X)))
a_{_sqr}(X) -> sqr(X)
a_{_dbl}(0) -> 0
a_{_dbl}(s(X)) -> s(s(dbl(X)))
a_{_dbl}(X) -> dbl(X)
a_{_add}(0, X) -> mark(X)
a_{_add}(s(X), Y) -> s(add(X, Y))
a_{_add}(X1, X2) -> add(X1, X2)
a_{_first}(0, X) -> nil
a_{_first}(s(X), cons(Y, Z)) -> cons(mark(Y), first(X, Z))
a_{_first}(X1, X2) -> first(X1, X2)
mark(terms(X)) -> a_{_terms}(mark(X))
mark(sqr(X)) -> a_{_sqr}(mark(X))
mark(add(X1, X2)) -> a_{_add}(mark(X1), mark(X2))
mark(dbl(X)) -> a_{_dbl}(mark(X))
mark(first(X1, X2)) -> a_{_first}(mark(X1), mark(X2))
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(recip(X)) -> recip(mark(X))
mark(s(X)) -> s(X)
mark(0) -> 0
mark(nil) -> nil

We number the DPs as follows:

MARK(sqr(X)) -> MARK(X)

and get the following Size-Change Graph(s):

{1}	,	{1}
1	>	1

which lead(s) to this/these maximal multigraph(s):

{1}	,	{1}
1	>	1

D_P: empty set
Oriented Rules: none

We used the order Homeomorphic Embedding Order with Non-Strict Precedence.

trivial

with Argument Filtering System:

sqr(x₁) -> sqr(x₁)

We obtain no new DP problems.

Termination of R successfully shown.
Duration:
0:03 minutes