Termination w.r.t. Q of the given QTRS could be proven:

(0) Obligation:

Q restricted rewrite system:
The TRS R consists of the following rules:

and(x, or(y, z)) → or(and(x, y), and(x, z))
and(x, and(y, y)) → and(x, y)
or(or(x, y), and(y, z)) → or(x, y)
or(x, and(x, y)) → x
or(true, y) → true
or(x, false) → x
or(x, x) → x
or(x, or(y, y)) → or(x, y)
and(x, true) → x
and(false, y) → false
and(x, x) → x

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:

AND(x, or(y, z)) → OR(and(x, y), and(x, z))
AND(x, or(y, z)) → AND(x, y)
AND(x, or(y, z)) → AND(x, z)
AND(x, and(y, y)) → AND(x, y)
OR(x, or(y, y)) → OR(x, y)

The TRS R consists of the following rules:

and(x, or(y, z)) → or(and(x, y), and(x, z))
and(x, and(y, y)) → and(x, y)
or(or(x, y), and(y, z)) → or(x, y)
or(x, and(x, y)) → x
or(true, y) → true
or(x, false) → x
or(x, x) → x
or(x, or(y, y)) → or(x, y)
and(x, true) → x
and(false, y) → false
and(x, x) → x

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:

OR(x, or(y, y)) → OR(x, y)

The TRS R consists of the following rules:

and(x, or(y, z)) → or(and(x, y), and(x, z))
and(x, and(y, y)) → and(x, y)
or(or(x, y), and(y, z)) → or(x, y)
or(x, and(x, y)) → x
or(true, y) → true
or(x, false) → x
or(x, x) → x
or(x, or(y, y)) → or(x, y)
and(x, true) → x
and(false, y) → false
and(x, x) → x

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(x2)

From the DPs we obtained the following set of size-change graphs:

• OR(x, or(y, y)) → OR(x, y) (allowed arguments on rhs = {1, 2})
  The graph contains the following edges 1 >= 1, 2 > 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:

AND(x, or(y, z)) → AND(x, z)
AND(x, or(y, z)) → AND(x, y)
AND(x, and(y, y)) → AND(x, y)

The TRS R consists of the following rules:

and(x, or(y, z)) → or(and(x, y), and(x, z))
and(x, and(y, y)) → and(x, y)
or(or(x, y), and(y, z)) → or(x, y)
or(x, and(x, y)) → x
or(true, y) → true
or(x, false) → x
or(x, x) → x
or(x, or(y, y)) → or(x, y)
and(x, true) → x
and(false, y) → false
and(x, x) → x

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(x2)
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(x, and(y, y)) → AND(x, y) (allowed arguments on rhs = {1, 2})
  The graph contains the following edges 1 >= 1, 2 > 2

We oriented the following set of usable rules [AAECC05,FROCOS05]. none

(10) TRUE