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

         ↳Remaining

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 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

         ↳Remaining

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

         ↳Remaining Obligation(s)

The following remains to be proven:
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

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