Termination Proof using AProVE

Term Rewriting System R:
[x]
a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Innermost Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

A(f, 0) -> A(s, 0)
A(d, a(s, x)) -> A(s, a(s, a(d, a(p, a(s, x)))))
A(d, a(s, x)) -> A(s, a(d, a(p, a(s, x))))
A(d, a(s, x)) -> A(d, a(p, a(s, x)))
A(d, a(s, x)) -> A(p, a(s, x))
A(f, a(s, x)) -> A(d, a(f, a(p, a(s, x))))
A(f, a(s, x)) -> A(f, a(p, a(s, x)))
A(f, a(s, x)) -> A(p, a(s, x))

Furthermore, R contains two SCCs.

     ↳DPs

       →DP Problem 1

         ↳Rewriting Transformation

       →DP Problem 2

         ↳Rw

Dependency Pair:

A(d, a(s, x)) -> A(d, a(p, a(s, x)))

Rules:

a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Strategy:

innermost

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

A(d, a(s, x)) -> A(d, a(p, a(s, x)))

one new Dependency Pair is created:

A(d, a(s, x)) -> A(d, x)

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Rw

           →DP Problem 3

             ↳Argument Filtering and Ordering

       →DP Problem 2

         ↳Rw

Dependency Pair:

A(d, a(s, x)) -> A(d, x)

Rules:

a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Strategy:

innermost

The following dependency pair can be strictly oriented:

A(d, a(s, x)) -> A(d, x)

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(x₁, x₂) -> A(x₁, x₂)
a(x₁, x₂) -> a(x₁, x₂)

     ↳DPs

       →DP Problem 1

         ↳Rw

           →DP Problem 3

             ↳AFS

...

               →DP Problem 4

                 ↳Dependency Graph

       →DP Problem 2

         ↳Rw

Dependency Pair:

Rules:

a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

     ↳DPs

       →DP Problem 1

         ↳Rw

       →DP Problem 2

         ↳Rewriting Transformation

Dependency Pair:

A(f, a(s, x)) -> A(f, a(p, a(s, x)))

Rules:

a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Strategy:

innermost

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

A(f, a(s, x)) -> A(f, a(p, a(s, x)))

one new Dependency Pair is created:

A(f, a(s, x)) -> A(f, x)

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Rw

       →DP Problem 2

         ↳Rw

           →DP Problem 5

             ↳Argument Filtering and Ordering

Dependency Pair:

A(f, a(s, x)) -> A(f, x)

Rules:

a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Strategy:

innermost

The following dependency pair can be strictly oriented:

A(f, a(s, x)) -> A(f, x)

A(x₁, x₂) -> A(x₁, x₂)
a(x₁, x₂) -> a(x₁, x₂)

     ↳DPs

       →DP Problem 1

         ↳Rw

       →DP Problem 2

         ↳Rw

           →DP Problem 5

             ↳AFS

...

               →DP Problem 6

                 ↳Dependency Graph

Dependency Pair:

Rules:

a(f, 0) -> a(s, 0)
a(d, 0) -> 0
a(d, a(s, x)) -> a(s, a(s, a(d, a(p, a(s, x)))))
a(f, a(s, x)) -> a(d, a(f, a(p, a(s, x))))
a(p, a(s, x)) -> x

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

Innermost Termination of R successfully shown.
Duration:
0:00 minutes