Termination Proof using AProVE

Term Rewriting System R:
[x, y]
not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Innermost Termination of R to be shown.

     ↳Dependency Pair Analysis

R contains the following Dependency Pairs:

NOT(or(x, y)) -> NOT(not(not(x)))
NOT(or(x, y)) -> NOT(not(x))
NOT(or(x, y)) -> NOT(x)
NOT(or(x, y)) -> NOT(not(not(y)))
NOT(or(x, y)) -> NOT(not(y))
NOT(or(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(not(x)))
NOT(and(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(y)

Furthermore, R contains one SCC.

     ↳DPs

       →DP Problem 1

         ↳Narrowing Transformation

Dependency Pairs:

NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(not(not(x)))
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(not(y))
NOT(or(x, y)) -> NOT(not(not(y)))
NOT(or(x, y)) -> NOT(x)
NOT(or(x, y)) -> NOT(not(x))
NOT(or(x, y)) -> NOT(not(not(x)))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(or(x, y)) -> NOT(not(not(x)))

four new Dependency Pairs are created:

NOT(or(x'', y)) -> NOT(x'')
NOT(or(not(x''), y)) -> NOT(not(x''))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Narrowing Transformation

Dependency Pairs:

NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(not(not(x)))
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(not(y))
NOT(or(x, y)) -> NOT(not(not(y)))
NOT(or(x, y)) -> NOT(x)
NOT(or(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(y)

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(or(x, y)) -> NOT(not(x))

three new Dependency Pairs are created:

NOT(or(not(x''), y)) -> NOT(x'')
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 3

                 ↳Narrowing Transformation

Dependency Pairs:

NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(not(not(x)))
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(not(y))
NOT(or(x, y)) -> NOT(not(not(y)))
NOT(or(x, y)) -> NOT(x)
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(or(x, y)) -> NOT(not(not(y)))

four new Dependency Pairs are created:

NOT(or(x, y')) -> NOT(y')
NOT(or(x, not(x''))) -> NOT(not(x''))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 4

                 ↳Narrowing Transformation

Dependency Pairs:

NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, y')) -> NOT(y')
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(not(not(x)))
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(not(y))
NOT(or(x, y)) -> NOT(x)
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(or(x, y)) -> NOT(not(y))

three new Dependency Pairs are created:

NOT(or(x, not(x''))) -> NOT(x'')
NOT(or(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 5

                 ↳Narrowing Transformation

Dependency Pairs:

NOT(or(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, y')) -> NOT(y')
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(x))
NOT(and(x, y)) -> NOT(not(not(x)))
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(x)
NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(and(x, y)) -> NOT(not(not(x)))

four new Dependency Pairs are created:

NOT(and(x'', y)) -> NOT(x'')
NOT(and(not(x''), y)) -> NOT(not(x''))
NOT(and(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(and(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 6

                 ↳Narrowing Transformation

Dependency Pairs:

NOT(and(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(and(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, y')) -> NOT(y')
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x'', y)) -> NOT(x'')
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(and(x, y)) -> NOT(not(x))
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(x)
NOT(or(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(and(x, y)) -> NOT(not(x))

three new Dependency Pairs are created:

NOT(and(not(x''), y)) -> NOT(x'')
NOT(and(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(and(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 7

                 ↳Narrowing Transformation

Dependency Pairs:

NOT(and(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, y')) -> NOT(y')
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x'', y)) -> NOT(x'')
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(not(not(y)))
NOT(and(x, y)) -> NOT(x)
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(x)
NOT(and(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(and(x, y)) -> NOT(not(not(y)))

four new Dependency Pairs are created:

NOT(and(x, y')) -> NOT(y')
NOT(and(x, not(x''))) -> NOT(not(x''))
NOT(and(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(and(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 8

                 ↳Narrowing Transformation

Dependency Pairs:

NOT(and(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(and(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(and(x, y')) -> NOT(y')
NOT(and(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(and(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, y')) -> NOT(y')
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x'', y)) -> NOT(x'')
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(not(y))
NOT(and(x, y)) -> NOT(x)
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(x)
NOT(and(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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

NOT(and(x, y)) -> NOT(not(y))

three new Dependency Pairs are created:

NOT(and(x, not(x''))) -> NOT(x'')
NOT(and(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))

The transformation is resulting in one new DP problem:

     ↳DPs

       →DP Problem 1

         ↳Nar

           →DP Problem 2

             ↳Nar

...

               →DP Problem 9

                 ↳Remaining Obligation(s)

The following remains to be proven:
Dependency Pairs:

NOT(and(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(and(x, y')) -> NOT(y')
NOT(and(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(and(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, and(x'', y''))) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, or(x'', y''))) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x, y')) -> NOT(y')
NOT(or(and(x'', y''), y)) -> NOT(or(not(not(not(x''))), not(not(not(y'')))))
NOT(and(x'', y)) -> NOT(x'')
NOT(or(or(x'', y''), y)) -> NOT(and(not(not(not(x''))), not(not(not(y'')))))
NOT(or(and(x'', y''), y)) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))
NOT(or(or(x'', y''), y)) -> NOT(not(and(not(not(not(x''))), not(not(not(y''))))))
NOT(or(x'', y)) -> NOT(x'')
NOT(and(x, y)) -> NOT(y)
NOT(and(x, y)) -> NOT(x)
NOT(or(x, y)) -> NOT(y)
NOT(or(x, y)) -> NOT(x)
NOT(and(x, and(x'', y''))) -> NOT(not(or(not(not(not(x''))), not(not(not(y''))))))

Rules:

not(not(x)) -> x
not(or(x, y)) -> and(not(not(not(x))), not(not(not(y))))
not(and(x, y)) -> or(not(not(not(x))), not(not(not(y))))

Strategy:

innermost

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