(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
not(not(x)) → x
not(or(x, y)) → and(not(x), not(y))
not(and(x, y)) → or(not(x), not(y))
and(x, or(y, z)) → or(and(x, y), and(x, z))
and(or(y, z), x) → or(and(x, y), and(x, z))
Q is empty.
(1) DependencyPairsProof (EQUIVALENT transformation)
Using Dependency Pairs [AG00,LPAR04] we result in the following initial DP problem.
(2) Obligation:
Q DP problem:
The TRS P consists of the following rules:
NOT(or(x, y)) → AND(not(x), not(y))
NOT(or(x, y)) → NOT(x)
NOT(or(x, y)) → NOT(y)
NOT(and(x, y)) → NOT(x)
NOT(and(x, y)) → NOT(y)
AND(x, or(y, z)) → AND(x, y)
AND(x, or(y, z)) → AND(x, z)
AND(or(y, z), x) → AND(x, y)
AND(or(y, z), x) → AND(x, z)
The TRS R consists of the following rules:
not(not(x)) → x
not(or(x, y)) → and(not(x), not(y))
not(and(x, y)) → or(not(x), not(y))
and(x, or(y, z)) → or(and(x, y), and(x, z))
and(or(y, z), x) → or(and(x, y), and(x, z))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(3) DependencyGraphProof (EQUIVALENT transformation)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 1 less node.
(4) Complex Obligation (AND)
(5) Obligation:
Q DP problem:
The TRS P consists of the following rules:
AND(x, or(y, z)) → AND(x, z)
AND(x, or(y, z)) → AND(x, y)
AND(or(y, z), x) → AND(x, y)
AND(or(y, z), x) → AND(x, z)
The TRS R consists of the following rules:
not(not(x)) → x
not(or(x, y)) → and(not(x), not(y))
not(and(x, y)) → or(not(x), not(y))
and(x, or(y, z)) → or(and(x, y), and(x, z))
and(or(y, z), x) → or(and(x, y), and(x, z))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(6) QDPSizeChangeProof (EQUIVALENT transformation)
We used the following order and afs together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem.
Order:Homeomorphic Embedding Order
AFS:
or(x1, x2) = or(x1, x2)
From the DPs we obtained the following set of size-change graphs:
- AND(x, or(y, z)) → AND(x, z) (allowed arguments on rhs = {1, 2})
The graph contains the following edges 1 >= 1, 2 > 2
- AND(x, or(y, z)) → AND(x, y) (allowed arguments on rhs = {1, 2})
The graph contains the following edges 1 >= 1, 2 > 2
- AND(or(y, z), x) → AND(x, y) (allowed arguments on rhs = {1, 2})
The graph contains the following edges 2 >= 1, 1 > 2
- AND(or(y, z), x) → AND(x, z) (allowed arguments on rhs = {1, 2})
The graph contains the following edges 2 >= 1, 1 > 2
We oriented the following set of usable rules [AAECC05,FROCOS05].
none
(7) TRUE
(8) Obligation:
Q DP problem:
The TRS P consists of the following rules:
NOT(or(x, y)) → NOT(y)
NOT(or(x, y)) → NOT(x)
NOT(and(x, y)) → NOT(x)
NOT(and(x, y)) → NOT(y)
The TRS R consists of the following rules:
not(not(x)) → x
not(or(x, y)) → and(not(x), not(y))
not(and(x, y)) → or(not(x), not(y))
and(x, or(y, z)) → or(and(x, y), and(x, z))
and(or(y, z), x) → or(and(x, y), and(x, z))
Q is empty.
We have to consider all minimal (P,Q,R)-chains.
(9) QDPSizeChangeProof (EQUIVALENT transformation)
We used the following order and afs together with the size-change analysis [AAECC05] to show that there are no infinite chains for this DP problem.
Order:Homeomorphic Embedding Order
AFS:
and(x1, x2) = and(x1, x2)
or(x1, x2) = or(x1, x2)
From the DPs we obtained the following set of size-change graphs:
- NOT(or(x, y)) → NOT(y) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
- NOT(or(x, y)) → NOT(x) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
- NOT(and(x, y)) → NOT(x) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
- NOT(and(x, y)) → NOT(y) (allowed arguments on rhs = {1})
The graph contains the following edges 1 > 1
We oriented the following set of usable rules [AAECC05,FROCOS05].
none
(10) TRUE