Termination proof of /tmp/tmp25rned/ExSec11_1

Termination of the following Term Rewriting System could be proven:

Context-sensitive rewrite system:
The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

The replacement map contains the following entries:

terms: {1}
cons: {1}
recip: {1}
sqr: {1}
s: {1}
0: empty set
add: {1, 2}
dbl: {1}
first: {1, 2}
nil: empty set
half: {1}

↳ CSR

  ↳ CSDependencyPairsProof

Context-sensitive rewrite system:
The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

The replacement map contains the following entries:

terms: {1}
cons: {1}
recip: {1}
sqr: {1}
s: {1}
0: empty set
add: {1, 2}
dbl: {1}
first: {1, 2}
nil: empty set
half: {1}

Using Improved CS-DPs we result in the following initial Q-CSDP problem.

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half, SQR, TERMS, ADD, DBL, HALF, FIRST} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.
The symbols in {U} are not replacing on any position.

The ordinary context-sensitive dependency pairs DP_o are:

TERMS(N) → SQR(N)
SQR(s(X)) → ADD(sqr(X), dbl(X))
SQR(s(X)) → SQR(X)
SQR(s(X)) → DBL(X)
DBL(s(X)) → DBL(X)
ADD(s(X), Y) → ADD(X, Y)
HALF(s(s(X))) → HALF(X)

The hidden terms of R are:

terms(s(N))
first(X, Z)

Every hiding context is built from:

s on positions {1}
terms on positions {1}
first on positions {1, 2}

Hence, the new unhiding pairs DP_u are :

U(s(x_0)) → U(x_0)
U(terms(x_0)) → U(x_0)
U(first(x_0, x_1)) → U(x_0)
U(first(x_0, x_1)) → U(x_1)
U(terms(s(N))) → TERMS(s(N))
U(first(X, Z)) → FIRST(X, Z)

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

The approximation of the Context-Sensitive Dependency Graph contains 5 SCCs with 5 less nodes.

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

            ↳ QCSDPSubtermProof

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half, HALF} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.

The TRS P consists of the following rules:

HALF(s(s(X))) → HALF(X)

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

We use the subterm processor [20].

The following pairs can be oriented strictly and are deleted.

HALF(s(s(X))) → HALF(X)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
HALF(x1) = x1

Subterm Order

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

            ↳ QCSDPSubtermProof

              ↳ QCSDP

                ↳ PIsEmptyProof

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.

The TRS P consists of the following rules:
none

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half, DBL} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.

The TRS P consists of the following rules:

DBL(s(X)) → DBL(X)

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

We use the subterm processor [20].

The following pairs can be oriented strictly and are deleted.

DBL(s(X)) → DBL(X)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
DBL(x1) = x1

Subterm Order

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

              ↳ QCSDP

                ↳ PIsEmptyProof

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

          ↳ QCSDP

          ↳ QCSDP

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half, ADD} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.

The TRS P consists of the following rules:

ADD(s(X), Y) → ADD(X, Y)

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

We use the subterm processor [20].

The following pairs can be oriented strictly and are deleted.

ADD(s(X), Y) → ADD(X, Y)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
ADD(x1, x2) = x1

Subterm Order

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

              ↳ QCSDP

                ↳ PIsEmptyProof

          ↳ QCSDP

          ↳ QCSDP

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

          ↳ QCSDP

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half, SQR} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.

The TRS P consists of the following rules:

SQR(s(X)) → SQR(X)

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

We use the subterm processor [20].

The following pairs can be oriented strictly and are deleted.

SQR(s(X)) → SQR(X)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
SQR(x1) = x1

Subterm Order

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

              ↳ QCSDP

                ↳ PIsEmptyProof

          ↳ QCSDP

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

Q-restricted context-sensitive dependency pair problem:
The symbols in {terms, recip, sqr, s, add, dbl, first, half} are replacing on all positions.
For all symbols f in {cons} we have µ(f) = {1}.
The symbols in {U} are not replacing on any position.

The TRS P consists of the following rules:

U(s(x_0)) → U(x_0)
U(terms(x_0)) → U(x_0)
U(first(x_0, x_1)) → U(x_0)
U(first(x_0, x_1)) → U(x_1)

The TRS R consists of the following rules:

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

We use the subterm processor [20].

The following pairs can be oriented strictly and are deleted.

U(s(x_0)) → U(x_0)
U(terms(x_0)) → U(x_0)
U(first(x_0, x_1)) → U(x_0)
U(first(x_0, x_1)) → U(x_1)

The remaining pairs can at least be oriented weakly.
none
Used ordering: Combined order from the following AFS and order.
U(x1) = x1

Subterm Order

↳ CSR

  ↳ CSDependencyPairsProof

    ↳ QCSDP

      ↳ QCSDependencyGraphProof

        ↳ AND

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

          ↳ QCSDP

            ↳ QCSDPSubtermProof

              ↳ QCSDP

                ↳ PIsEmptyProof

terms(N) → cons(recip(sqr(N)), terms(s(N)))
sqr(0) → 0
sqr(s(X)) → s(add(sqr(X), dbl(X)))
dbl(0) → 0
dbl(s(X)) → s(s(dbl(X)))
add(0, X) → X
add(s(X), Y) → s(add(X, Y))
first(0, X) → nil
first(s(X), cons(Y, Z)) → cons(Y, first(X, Z))
half(0) → 0
half(s(0)) → 0
half(s(s(X))) → s(half(X))
half(dbl(X)) → X

Q is empty.

The TRS P is empty. Hence, there is no (P,Q,R,µ)-chain.