Termination Proof using AProVE

Term Rewriting System R:
[x, y]
f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Innermost Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

F(s(x)) -> F(x)
G(x, c(y)) -> G(x, y)
G(x, c(y)) -> G(x, if(f(x), c(g(s(x), y)), c(y)))
G(x, c(y)) -> IF(f(x), c(g(s(x), y)), c(y))
G(x, c(y)) -> F(x)
G(x, c(y)) -> G(s(x), y)

Furthermore, R contains two SCCs.

     ↳DPs

       →DP Problem 1

         ↳Argument Filtering and Ordering

       →DP Problem 2

         ↳Nar

Dependency Pair:

F(s(x)) -> F(x)

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

The following dependency pair can be strictly oriented:

F(s(x)) -> F(x)

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:

F(x₁) -> F(x₁)
s(x₁) -> s(x₁)

     ↳DPs

       →DP Problem 1

         ↳AFS

           →DP Problem 3

             ↳Dependency Graph

       →DP Problem 2

         ↳Nar

Dependency Pair:

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

Using the Dependency Graph resulted in no new DP problems.

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳Narrowing Transformation

Dependency Pairs:

G(x, c(y)) -> G(s(x), y)
G(x, c(y)) -> G(x, if(f(x), c(g(s(x), y)), c(y)))
G(x, c(y)) -> G(x, y)

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

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

G(x, c(y)) -> G(x, if(f(x), c(g(s(x), y)), c(y)))

five new Dependency Pairs are created:

G(0, c(y)) -> G(0, if(true, c(g(s(0), y)), c(y)))
G(1, c(y)) -> G(1, if(false, c(g(s(1), y)), c(y)))
G(s(x''), c(y)) -> G(s(x''), if(f(x''), c(g(s(s(x'')), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(c(g(s(x''), y''))), c(c(y''))))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(s(x'')), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳Nar

           →DP Problem 4

             ↳Rewriting Transformation

Dependency Pairs:

G(s(x''), c(y)) -> G(s(x''), if(f(x''), c(g(s(s(x'')), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(s(x'')), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))
G(1, c(y)) -> G(1, if(false, c(g(s(1), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(c(g(s(x''), y''))), c(c(y''))))
G(0, c(y)) -> G(0, if(true, c(g(s(0), y)), c(y)))
G(x, c(y)) -> G(x, y)
G(x, c(y)) -> G(s(x), y)

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

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

G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(s(x'')), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))

one new Dependency Pair is created:

G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(x''), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳Nar

           →DP Problem 4

             ↳Rw

...

               →DP Problem 5

                 ↳Forward Instantiation Transformation

Dependency Pairs:

G(1, c(y)) -> G(1, if(false, c(g(s(1), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(x''), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))
G(0, c(y)) -> G(0, if(true, c(g(s(0), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(c(g(s(x''), y''))), c(c(y''))))
G(x, c(y)) -> G(s(x), y)
G(x, c(y)) -> G(x, y)
G(s(x''), c(y)) -> G(s(x''), if(f(x''), c(g(s(s(x'')), y)), c(y)))

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

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

G(x, c(y)) -> G(x, y)

five new Dependency Pairs are created:

G(x'', c(c(y''))) -> G(x'', c(y''))
G(0, c(c(y''))) -> G(0, c(y''))
G(1, c(c(y''))) -> G(1, c(y''))
G(s(x''''), c(c(y''))) -> G(s(x''''), c(y''))
G(x', c(c(c(y'''')))) -> G(x', c(c(y'''')))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳Nar

           →DP Problem 4

             ↳Rw

...

               →DP Problem 6

                 ↳Forward Instantiation Transformation

Dependency Pairs:

G(s(x''''), c(c(y''))) -> G(s(x''''), c(y''))
G(1, c(c(y''))) -> G(1, c(y''))
G(x', c(c(c(y'''')))) -> G(x', c(c(y'''')))
G(0, c(c(y''))) -> G(0, c(y''))
G(x'', c(c(y''))) -> G(x'', c(y''))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(x''), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))
G(0, c(y)) -> G(0, if(true, c(g(s(0), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(c(g(s(x''), y''))), c(c(y''))))
G(s(x''), c(y)) -> G(s(x''), if(f(x''), c(g(s(s(x'')), y)), c(y)))
G(x, c(y)) -> G(s(x), y)
G(1, c(y)) -> G(1, if(false, c(g(s(1), y)), c(y)))

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

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

G(x, c(y)) -> G(s(x), y)

four new Dependency Pairs are created:

G(x'', c(c(y''))) -> G(s(x''), c(y''))
G(x', c(c(y''))) -> G(s(x'), c(y''))
G(x', c(c(c(y'''')))) -> G(s(x'), c(c(y'''')))
G(x', c(c(c(c(y''''''))))) -> G(s(x'), c(c(c(y''''''))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳AFS

       →DP Problem 2

         ↳Nar

           →DP Problem 4

             ↳Rw

...

               →DP Problem 7

                 ↳Remaining Obligation(s)

The following remains to be proven:
Dependency Pairs:

G(x', c(c(c(c(y''''''))))) -> G(s(x'), c(c(c(y''''''))))
G(x', c(c(c(y'''')))) -> G(s(x'), c(c(y'''')))
G(x', c(c(y''))) -> G(s(x'), c(y''))
G(x'', c(c(y''))) -> G(s(x''), c(y''))
G(1, c(c(y''))) -> G(1, c(y''))
G(x', c(c(c(y'''')))) -> G(x', c(c(y'''')))
G(0, c(c(y''))) -> G(0, c(y''))
G(x'', c(c(y''))) -> G(x'', c(y''))
G(1, c(y)) -> G(1, if(false, c(g(s(1), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(g(s(x''), if(f(x''), c(g(s(s(x'')), y'')), c(y'')))), c(c(y''))))
G(0, c(y)) -> G(0, if(true, c(g(s(0), y)), c(y)))
G(x'', c(c(y''))) -> G(x'', if(f(x''), c(c(g(s(x''), y''))), c(c(y''))))
G(s(x''), c(y)) -> G(s(x''), if(f(x''), c(g(s(s(x'')), y)), c(y)))
G(s(x''''), c(c(y''))) -> G(s(x''''), c(y''))

Rules:

f(0) -> true
f(1) -> false
f(s(x)) -> f(x)
if(true, s(x), s(y)) -> s(x)
if(false, s(x), s(y)) -> s(y)
g(x, c(y)) -> c(g(x, y))
g(x, c(y)) -> g(x, if(f(x), c(g(s(x), y)), c(y)))

Strategy:

innermost

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