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.



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


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



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



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



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



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



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



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



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



   R
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