Termination Proof using AProVE

Term Rewriting System R:
[X, Y, X1, X2]
a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Innermost Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

A_{_FROM}(X) -> MARK(X)
A_{_LENGTH}(cons(X, Y)) -> A_{_LENGTH1}(Y)
A_{_LENGTH1}(X) -> A_{_LENGTH}(X)
MARK(from(X)) -> A_{_FROM}(mark(X))
MARK(from(X)) -> MARK(X)
MARK(length(X)) -> A_{_LENGTH}(X)
MARK(length1(X)) -> A_{_LENGTH1}(X)
MARK(cons(X1, X2)) -> MARK(X1)
MARK(s(X)) -> MARK(X)

Furthermore, R contains two SCCs.

     ↳DPs

       →DP Problem 1

         ↳Argument Filtering and Ordering

       →DP Problem 2

         ↳FwdInst

Dependency Pairs:

A_{_LENGTH1}(X) -> A_{_LENGTH}(X)
A_{_LENGTH}(cons(X, Y)) -> A_{_LENGTH1}(Y)

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

The following dependency pair can be strictly oriented:

A_{_LENGTH}(cons(X, Y)) -> A_{_LENGTH1}(Y)

There are no usable rules for innermost w.r.t. to the AFS that need to be oriented.
Used ordering: Homeomorphic Embedding Order with EMB
resulting in one new DP problem.
Used Argument Filtering System:

A_{_LENGTH1}(x₁) -> x₁
A_{_LENGTH}(x₁) -> x₁
cons(x₁, x₂) -> cons(x₁, x₂)

     ↳DPs

       →DP Problem 1

         ↳AFS

           →DP Problem 3

             ↳Dependency Graph

       →DP Problem 2

         ↳FwdInst

Dependency Pair:

A_{_LENGTH1}(X) -> A_{_LENGTH}(X)

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳Forward Instantiation Transformation

Dependency Pairs:

MARK(s(X)) -> MARK(X)
MARK(cons(X1, X2)) -> MARK(X1)
MARK(from(X)) -> MARK(X)
MARK(from(X)) -> A_{_FROM}(mark(X))
A_{_FROM}(X) -> MARK(X)

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

A_{_FROM}(X) -> MARK(X)

three new Dependency Pairs are created:

A_{_FROM}(from(X'')) -> MARK(from(X''))
A_{_FROM}(cons(X1'', X2'')) -> MARK(cons(X1'', X2''))
A_{_FROM}(s(X'')) -> MARK(s(X''))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳FwdInst

           →DP Problem 4

             ↳Narrowing Transformation

Dependency Pairs:

A_{_FROM}(s(X'')) -> MARK(s(X''))
A_{_FROM}(cons(X1'', X2'')) -> MARK(cons(X1'', X2''))
MARK(cons(X1, X2)) -> MARK(X1)
MARK(from(X)) -> MARK(X)
A_{_FROM}(from(X'')) -> MARK(from(X''))
MARK(from(X)) -> A_{_FROM}(mark(X))
MARK(s(X)) -> MARK(X)

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

On this DP problem, a Narrowing SCC transformation can be performed.
As a result of transforming the rule

MARK(from(X)) -> A_{_FROM}(mark(X))

seven new Dependency Pairs are created:

MARK(from(from(X''))) -> A_{_FROM}(a_{_from}(mark(X'')))
MARK(from(length(X''))) -> A_{_FROM}(a_{_length}(X''))
MARK(from(length1(X''))) -> A_{_FROM}(a_{_length1}(X''))
MARK(from(cons(X1', X2'))) -> A_{_FROM}(cons(mark(X1'), X2'))
MARK(from(s(X''))) -> A_{_FROM}(s(mark(X'')))
MARK(from(nil)) -> A_{_FROM}(nil)
MARK(from(0)) -> A_{_FROM}(0)

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳FwdInst

           →DP Problem 4

             ↳Nar

...

               →DP Problem 5

                 ↳Forward Instantiation Transformation

Dependency Pairs:

MARK(from(s(X''))) -> A_{_FROM}(s(mark(X'')))
MARK(from(cons(X1', X2'))) -> A_{_FROM}(cons(mark(X1'), X2'))
MARK(from(length1(X''))) -> A_{_FROM}(a_{_length1}(X''))
A_{_FROM}(cons(X1'', X2'')) -> MARK(cons(X1'', X2''))
MARK(from(length(X''))) -> A_{_FROM}(a_{_length}(X''))
A_{_FROM}(from(X'')) -> MARK(from(X''))
MARK(from(from(X''))) -> A_{_FROM}(a_{_from}(mark(X'')))
MARK(cons(X1, X2)) -> MARK(X1)
MARK(from(X)) -> MARK(X)
MARK(s(X)) -> MARK(X)
A_{_FROM}(s(X'')) -> MARK(s(X''))

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

MARK(from(X)) -> MARK(X)

eight new Dependency Pairs are created:

MARK(from(from(X''))) -> MARK(from(X''))
MARK(from(cons(X1'', X2''))) -> MARK(cons(X1'', X2''))
MARK(from(s(X''))) -> MARK(s(X''))
MARK(from(from(from(X'''')))) -> MARK(from(from(X'''')))
MARK(from(from(length(X'''')))) -> MARK(from(length(X'''')))
MARK(from(from(length1(X'''')))) -> MARK(from(length1(X'''')))
MARK(from(from(cons(X1''', X2''')))) -> MARK(from(cons(X1''', X2''')))
MARK(from(from(s(X'''')))) -> MARK(from(s(X'''')))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳FwdInst

           →DP Problem 4

             ↳Nar

...

               →DP Problem 6

                 ↳Forward Instantiation Transformation

Dependency Pairs:

MARK(from(from(s(X'''')))) -> MARK(from(s(X'''')))
MARK(from(from(cons(X1''', X2''')))) -> MARK(from(cons(X1''', X2''')))
MARK(from(from(length1(X'''')))) -> MARK(from(length1(X'''')))
MARK(from(from(length(X'''')))) -> MARK(from(length(X'''')))
MARK(from(from(from(X'''')))) -> MARK(from(from(X'''')))
MARK(from(s(X''))) -> MARK(s(X''))
MARK(from(cons(X1'', X2''))) -> MARK(cons(X1'', X2''))
MARK(from(from(X''))) -> MARK(from(X''))
MARK(from(cons(X1', X2'))) -> A_{_FROM}(cons(mark(X1'), X2'))
MARK(from(length1(X''))) -> A_{_FROM}(a_{_length1}(X''))
A_{_FROM}(cons(X1'', X2'')) -> MARK(cons(X1'', X2''))
MARK(from(length(X''))) -> A_{_FROM}(a_{_length}(X''))
A_{_FROM}(from(X'')) -> MARK(from(X''))
MARK(from(from(X''))) -> A_{_FROM}(a_{_from}(mark(X'')))
MARK(cons(X1, X2)) -> MARK(X1)
MARK(s(X)) -> MARK(X)
A_{_FROM}(s(X'')) -> MARK(s(X''))
MARK(from(s(X''))) -> A_{_FROM}(s(mark(X'')))

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

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

13 new Dependency Pairs are created:

MARK(cons(cons(X1'', X2''), X2)) -> MARK(cons(X1'', X2''))
MARK(cons(s(X''), X2)) -> MARK(s(X''))
MARK(cons(from(from(X'''')), X2)) -> MARK(from(from(X'''')))
MARK(cons(from(length(X'''')), X2)) -> MARK(from(length(X'''')))
MARK(cons(from(length1(X'''')), X2)) -> MARK(from(length1(X'''')))
MARK(cons(from(cons(X1''', X2''')), X2)) -> MARK(from(cons(X1''', X2''')))
MARK(cons(from(s(X'''')), X2)) -> MARK(from(s(X'''')))
MARK(cons(from(cons(X1'''', X2'''')), X2)) -> MARK(from(cons(X1'''', X2'''')))
MARK(cons(from(from(from(X''''''))), X2)) -> MARK(from(from(from(X''''''))))
MARK(cons(from(from(length(X''''''))), X2)) -> MARK(from(from(length(X''''''))))
MARK(cons(from(from(length1(X''''''))), X2)) -> MARK(from(from(length1(X''''''))))
MARK(cons(from(from(cons(X1''''', X2'''''))), X2)) -> MARK(from(from(cons(X1''''', X2'''''))))
MARK(cons(from(from(s(X''''''))), X2)) -> MARK(from(from(s(X''''''))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳FwdInst

           →DP Problem 4

             ↳Nar

...

               →DP Problem 7

                 ↳Forward Instantiation Transformation

Dependency Pairs:

MARK(cons(from(from(s(X''''''))), X2)) -> MARK(from(from(s(X''''''))))
MARK(cons(from(from(cons(X1''''', X2'''''))), X2)) -> MARK(from(from(cons(X1''''', X2'''''))))
MARK(cons(from(from(length1(X''''''))), X2)) -> MARK(from(from(length1(X''''''))))
MARK(cons(from(from(length(X''''''))), X2)) -> MARK(from(from(length(X''''''))))
MARK(from(from(cons(X1''', X2''')))) -> MARK(from(cons(X1''', X2''')))
MARK(from(from(length1(X'''')))) -> MARK(from(length1(X'''')))
MARK(from(from(length(X'''')))) -> MARK(from(length(X'''')))
MARK(from(from(from(X'''')))) -> MARK(from(from(X'''')))
MARK(cons(from(from(from(X''''''))), X2)) -> MARK(from(from(from(X''''''))))
MARK(cons(from(cons(X1'''', X2'''')), X2)) -> MARK(from(cons(X1'''', X2'''')))
MARK(from(s(X''))) -> MARK(s(X''))
MARK(cons(from(s(X'''')), X2)) -> MARK(from(s(X'''')))
MARK(cons(from(cons(X1''', X2''')), X2)) -> MARK(from(cons(X1''', X2''')))
MARK(cons(from(length1(X'''')), X2)) -> MARK(from(length1(X'''')))
MARK(cons(from(length(X'''')), X2)) -> MARK(from(length(X'''')))
MARK(from(cons(X1'', X2''))) -> MARK(cons(X1'', X2''))
MARK(from(cons(X1', X2'))) -> A_{_FROM}(cons(mark(X1'), X2'))
MARK(from(length1(X''))) -> A_{_FROM}(a_{_length1}(X''))
MARK(from(from(X''))) -> MARK(from(X''))
MARK(cons(from(from(X'''')), X2)) -> MARK(from(from(X'''')))
MARK(cons(s(X''), X2)) -> MARK(s(X''))
MARK(cons(cons(X1'', X2''), X2)) -> MARK(cons(X1'', X2''))
A_{_FROM}(cons(X1'', X2'')) -> MARK(cons(X1'', X2''))
MARK(from(length(X''))) -> A_{_FROM}(a_{_length}(X''))
A_{_FROM}(from(X'')) -> MARK(from(X''))
MARK(from(from(X''))) -> A_{_FROM}(a_{_from}(mark(X'')))
MARK(s(X)) -> MARK(X)
A_{_FROM}(s(X'')) -> MARK(s(X''))
MARK(from(s(X''))) -> A_{_FROM}(s(mark(X'')))
MARK(from(from(s(X'''')))) -> MARK(from(s(X'''')))

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

On this DP problem, a Forward Instantiation SCC transformation can be performed.
As a result of transforming the rule

MARK(s(X)) -> MARK(X)

25 new Dependency Pairs are created:

MARK(s(s(X''))) -> MARK(s(X''))
MARK(s(from(from(X'''')))) -> MARK(from(from(X'''')))
MARK(s(from(length(X'''')))) -> MARK(from(length(X'''')))
MARK(s(from(length1(X'''')))) -> MARK(from(length1(X'''')))
MARK(s(from(cons(X1''', X2''')))) -> MARK(from(cons(X1''', X2''')))
MARK(s(from(s(X'''')))) -> MARK(from(s(X'''')))
MARK(s(from(cons(X1'''', X2'''')))) -> MARK(from(cons(X1'''', X2'''')))
MARK(s(from(from(from(X''''''))))) -> MARK(from(from(from(X''''''))))
MARK(s(from(from(length(X''''''))))) -> MARK(from(from(length(X''''''))))
MARK(s(from(from(length1(X''''''))))) -> MARK(from(from(length1(X''''''))))
MARK(s(from(from(cons(X1''''', X2'''''))))) -> MARK(from(from(cons(X1''''', X2'''''))))
MARK(s(from(from(s(X''''''))))) -> MARK(from(from(s(X''''''))))
MARK(s(cons(cons(X1'''', X2''''), X2''))) -> MARK(cons(cons(X1'''', X2''''), X2''))
MARK(s(cons(s(X''''), X2''))) -> MARK(cons(s(X''''), X2''))
MARK(s(cons(from(from(X'''''')), X2''))) -> MARK(cons(from(from(X'''''')), X2''))
MARK(s(cons(from(length(X'''''')), X2''))) -> MARK(cons(from(length(X'''''')), X2''))
MARK(s(cons(from(length1(X'''''')), X2''))) -> MARK(cons(from(length1(X'''''')), X2''))
MARK(s(cons(from(cons(X1''''', X2''''')), X2''))) -> MARK(cons(from(cons(X1''''', X2''''')), X2''))
MARK(s(cons(from(s(X'''''')), X2''))) -> MARK(cons(from(s(X'''''')), X2''))
MARK(s(cons(from(cons(X1'''''', X2'''''')), X2''))) -> MARK(cons(from(cons(X1'''''', X2'''''')), X2''))
MARK(s(cons(from(from(from(X''''''''))), X2''))) -> MARK(cons(from(from(from(X''''''''))), X2''))
MARK(s(cons(from(from(length(X''''''''))), X2''))) -> MARK(cons(from(from(length(X''''''''))), X2''))
MARK(s(cons(from(from(length1(X''''''''))), X2''))) -> MARK(cons(from(from(length1(X''''''''))), X2''))
MARK(s(cons(from(from(cons(X1''''''', X2'''''''))), X2''))) -> MARK(cons(from(from(cons(X1''''''', X2'''''''))), X2''))
MARK(s(cons(from(from(s(X''''''''))), X2''))) -> MARK(cons(from(from(s(X''''''''))), X2''))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳FwdInst

           →DP Problem 4

             ↳Nar

...

               →DP Problem 8

                 ↳Remaining Obligation(s)

The following remains to be proven:
Dependency Pairs:

MARK(s(cons(from(from(s(X''''''''))), X2''))) -> MARK(cons(from(from(s(X''''''''))), X2''))
MARK(s(cons(from(from(cons(X1''''''', X2'''''''))), X2''))) -> MARK(cons(from(from(cons(X1''''''', X2'''''''))), X2''))
MARK(s(cons(from(from(length1(X''''''''))), X2''))) -> MARK(cons(from(from(length1(X''''''''))), X2''))
MARK(s(cons(from(from(length(X''''''''))), X2''))) -> MARK(cons(from(from(length(X''''''''))), X2''))
MARK(s(cons(from(from(from(X''''''''))), X2''))) -> MARK(cons(from(from(from(X''''''''))), X2''))
MARK(s(cons(from(cons(X1'''''', X2'''''')), X2''))) -> MARK(cons(from(cons(X1'''''', X2'''''')), X2''))
MARK(cons(from(s(X'''')), X2)) -> MARK(from(s(X'''')))
MARK(s(cons(from(s(X'''''')), X2''))) -> MARK(cons(from(s(X'''''')), X2''))
MARK(cons(from(cons(X1'''', X2'''')), X2)) -> MARK(from(cons(X1'''', X2'''')))
MARK(cons(from(cons(X1''', X2''')), X2)) -> MARK(from(cons(X1''', X2''')))
MARK(s(cons(from(cons(X1''''', X2''''')), X2''))) -> MARK(cons(from(cons(X1''''', X2''''')), X2''))
MARK(cons(from(length1(X'''')), X2)) -> MARK(from(length1(X'''')))
MARK(s(cons(from(length1(X'''''')), X2''))) -> MARK(cons(from(length1(X'''''')), X2''))
MARK(cons(from(length(X'''')), X2)) -> MARK(from(length(X'''')))
MARK(s(cons(from(length(X'''''')), X2''))) -> MARK(cons(from(length(X'''''')), X2''))
MARK(cons(from(from(cons(X1''''', X2'''''))), X2)) -> MARK(from(from(cons(X1''''', X2'''''))))
MARK(cons(from(from(length1(X''''''))), X2)) -> MARK(from(from(length1(X''''''))))
MARK(cons(from(from(length(X''''''))), X2)) -> MARK(from(from(length(X''''''))))
MARK(cons(from(from(from(X''''''))), X2)) -> MARK(from(from(from(X''''''))))
MARK(s(cons(from(from(X'''''')), X2''))) -> MARK(cons(from(from(X'''''')), X2''))
MARK(s(cons(s(X''''), X2''))) -> MARK(cons(s(X''''), X2''))
MARK(s(cons(cons(X1'''', X2''''), X2''))) -> MARK(cons(cons(X1'''', X2''''), X2''))
MARK(s(from(from(s(X''''''))))) -> MARK(from(from(s(X''''''))))
MARK(s(from(from(cons(X1''''', X2'''''))))) -> MARK(from(from(cons(X1''''', X2'''''))))
MARK(s(from(from(length1(X''''''))))) -> MARK(from(from(length1(X''''''))))
MARK(s(from(from(length(X''''''))))) -> MARK(from(from(length(X''''''))))
MARK(s(from(from(from(X''''''))))) -> MARK(from(from(from(X''''''))))
MARK(s(from(cons(X1'''', X2'''')))) -> MARK(from(cons(X1'''', X2'''')))
MARK(s(from(s(X'''')))) -> MARK(from(s(X'''')))
MARK(from(s(X''))) -> MARK(s(X''))
MARK(from(s(X''))) -> A_{_FROM}(s(mark(X'')))
MARK(from(from(s(X'''')))) -> MARK(from(s(X'''')))
MARK(from(from(cons(X1''', X2''')))) -> MARK(from(cons(X1''', X2''')))
MARK(from(from(length1(X'''')))) -> MARK(from(length1(X'''')))
MARK(from(from(length(X'''')))) -> MARK(from(length(X'''')))
MARK(from(from(from(X'''')))) -> MARK(from(from(X'''')))
MARK(cons(from(from(X'''')), X2)) -> MARK(from(from(X'''')))
MARK(from(cons(X1'', X2''))) -> MARK(cons(X1'', X2''))
MARK(from(cons(X1', X2'))) -> A_{_FROM}(cons(mark(X1'), X2'))
MARK(s(from(cons(X1''', X2''')))) -> MARK(from(cons(X1''', X2''')))
MARK(s(from(length1(X'''')))) -> MARK(from(length1(X'''')))
MARK(s(from(length(X'''')))) -> MARK(from(length(X'''')))
A_{_FROM}(s(X'')) -> MARK(s(X''))
MARK(from(length1(X''))) -> A_{_FROM}(a_{_length1}(X''))
MARK(from(from(X''))) -> MARK(from(X''))
MARK(s(from(from(X'''')))) -> MARK(from(from(X'''')))
MARK(s(s(X''))) -> MARK(s(X''))
MARK(cons(s(X''), X2)) -> MARK(s(X''))
MARK(cons(cons(X1'', X2''), X2)) -> MARK(cons(X1'', X2''))
A_{_FROM}(cons(X1'', X2'')) -> MARK(cons(X1'', X2''))
MARK(from(length(X''))) -> A_{_FROM}(a_{_length}(X''))
A_{_FROM}(from(X'')) -> MARK(from(X''))
MARK(from(from(X''))) -> A_{_FROM}(a_{_from}(mark(X'')))
MARK(cons(from(from(s(X''''''))), X2)) -> MARK(from(from(s(X''''''))))

Rules:

a_{_from}(X) -> cons(mark(X), from(s(X)))
a_{_from}(X) -> from(X)
a_{_length}(nil) -> 0
a_{_length}(cons(X, Y)) -> s(a_{_length1}(Y))
a_{_length}(X) -> length(X)
a_{_length1}(X) -> a_{_length}(X)
a_{_length1}(X) -> length1(X)
mark(from(X)) -> a_{_from}(mark(X))
mark(length(X)) -> a_{_length}(X)
mark(length1(X)) -> a_{_length1}(X)
mark(cons(X1, X2)) -> cons(mark(X1), X2)
mark(s(X)) -> s(mark(X))
mark(nil) -> nil
mark(0) -> 0

Strategy:

innermost

Innermost Termination of R could not be shown.
Duration:
0:24 minutes