(0) Obligation:

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

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(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:

ACTIVE(and(true, X)) → MARK(X)
ACTIVE(and(false, Y)) → MARK(false)
ACTIVE(if(true, X, Y)) → MARK(X)
ACTIVE(if(false, X, Y)) → MARK(Y)
ACTIVE(add(0, X)) → MARK(X)
ACTIVE(add(s(X), Y)) → MARK(s(add(X, Y)))
ACTIVE(add(s(X), Y)) → S(add(X, Y))
ACTIVE(add(s(X), Y)) → ADD(X, Y)
ACTIVE(first(0, X)) → MARK(nil)
ACTIVE(first(s(X), cons(Y, Z))) → MARK(cons(Y, first(X, Z)))
ACTIVE(first(s(X), cons(Y, Z))) → CONS(Y, first(X, Z))
ACTIVE(first(s(X), cons(Y, Z))) → FIRST(X, Z)
ACTIVE(from(X)) → MARK(cons(X, from(s(X))))
ACTIVE(from(X)) → CONS(X, from(s(X)))
ACTIVE(from(X)) → FROM(s(X))
ACTIVE(from(X)) → S(X)
MARK(and(X1, X2)) → ACTIVE(and(mark(X1), X2))
MARK(and(X1, X2)) → AND(mark(X1), X2)
MARK(and(X1, X2)) → MARK(X1)
MARK(true) → ACTIVE(true)
MARK(false) → ACTIVE(false)
MARK(if(X1, X2, X3)) → ACTIVE(if(mark(X1), X2, X3))
MARK(if(X1, X2, X3)) → IF(mark(X1), X2, X3)
MARK(if(X1, X2, X3)) → MARK(X1)
MARK(add(X1, X2)) → ACTIVE(add(mark(X1), X2))
MARK(add(X1, X2)) → ADD(mark(X1), X2)
MARK(add(X1, X2)) → MARK(X1)
MARK(0) → ACTIVE(0)
MARK(s(X)) → ACTIVE(s(X))
MARK(first(X1, X2)) → ACTIVE(first(mark(X1), mark(X2)))
MARK(first(X1, X2)) → FIRST(mark(X1), mark(X2))
MARK(first(X1, X2)) → MARK(X1)
MARK(first(X1, X2)) → MARK(X2)
MARK(nil) → ACTIVE(nil)
MARK(cons(X1, X2)) → ACTIVE(cons(X1, X2))
MARK(from(X)) → ACTIVE(from(X))
AND(mark(X1), X2) → AND(X1, X2)
AND(X1, mark(X2)) → AND(X1, X2)
AND(active(X1), X2) → AND(X1, X2)
AND(X1, active(X2)) → AND(X1, X2)
IF(mark(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, mark(X2), X3) → IF(X1, X2, X3)
IF(X1, X2, mark(X3)) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, active(X2), X3) → IF(X1, X2, X3)
IF(X1, X2, active(X3)) → IF(X1, X2, X3)
ADD(mark(X1), X2) → ADD(X1, X2)
ADD(X1, mark(X2)) → ADD(X1, X2)
ADD(active(X1), X2) → ADD(X1, X2)
ADD(X1, active(X2)) → ADD(X1, X2)
S(mark(X)) → S(X)
S(active(X)) → S(X)
FIRST(mark(X1), X2) → FIRST(X1, X2)
FIRST(X1, mark(X2)) → FIRST(X1, X2)
FIRST(active(X1), X2) → FIRST(X1, X2)
FIRST(X1, active(X2)) → FIRST(X1, X2)
CONS(mark(X1), X2) → CONS(X1, X2)
CONS(X1, mark(X2)) → CONS(X1, X2)
CONS(active(X1), X2) → CONS(X1, X2)
CONS(X1, active(X2)) → CONS(X1, X2)
FROM(mark(X)) → FROM(X)
FROM(active(X)) → FROM(X)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(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 8 SCCs with 17 less nodes.

(4) Complex Obligation (AND)

(5) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FROM(active(X)) → FROM(X)
FROM(mark(X)) → FROM(X)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(6) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


FROM(active(X)) → FROM(X)
FROM(mark(X)) → FROM(X)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
FROM(x1)  =  FROM(x1)
active(x1)  =  active(x1)
mark(x1)  =  mark(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1, x2)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
FROM1 > [false, nil, cons]
and1 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
and1 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]
if2 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
if2 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]
add1 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
add1 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]
from1 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
from1 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(7) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(8) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(9) TRUE

(10) Obligation:

Q DP problem:
The TRS P consists of the following rules:

CONS(X1, mark(X2)) → CONS(X1, X2)
CONS(mark(X1), X2) → CONS(X1, X2)
CONS(active(X1), X2) → CONS(X1, X2)
CONS(X1, active(X2)) → CONS(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(11) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


CONS(X1, mark(X2)) → CONS(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
CONS(x1, x2)  =  x2
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, false, first1, nil, cons]
true > [mark1, false, first1, nil, cons]
if2 > [mark1, false, first1, nil, cons]
add1 > s > [mark1, false, first1, nil, cons]
0 > [mark1, false, first1, nil, cons]
from1 > [mark1, false, first1, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(12) Obligation:

Q DP problem:
The TRS P consists of the following rules:

CONS(mark(X1), X2) → CONS(X1, X2)
CONS(active(X1), X2) → CONS(X1, X2)
CONS(X1, active(X2)) → CONS(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(13) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


CONS(X1, active(X2)) → CONS(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
CONS(x1, x2)  =  CONS(x2)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  x2
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Lexicographic Path Order [LPO].
Precedence:
CONS1 > [false, first, nil, cons]
[mark1, active1, and1, if2, 0, from] > true > [false, first, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(14) Obligation:

Q DP problem:
The TRS P consists of the following rules:

CONS(mark(X1), X2) → CONS(X1, X2)
CONS(active(X1), X2) → CONS(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(15) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


CONS(mark(X1), X2) → CONS(X1, X2)
CONS(active(X1), X2) → CONS(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
CONS(x1, x2)  =  CONS(x1)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  x2
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
true > [mark1, active1] > and1 > [CONS1, false, add1, first, nil]
true > [mark1, active1] > if2 > [CONS1, false, add1, first, nil]
true > [mark1, active1] > 0 > [CONS1, false, add1, first, nil]
true > [mark1, active1] > from1 > [CONS1, false, add1, first, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(16) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(17) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(18) TRUE

(19) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FIRST(X1, mark(X2)) → FIRST(X1, X2)
FIRST(mark(X1), X2) → FIRST(X1, X2)
FIRST(active(X1), X2) → FIRST(X1, X2)
FIRST(X1, active(X2)) → FIRST(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(20) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


FIRST(X1, mark(X2)) → FIRST(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
FIRST(x1, x2)  =  x2
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, false, first1, nil, cons]
true > [mark1, false, first1, nil, cons]
if2 > [mark1, false, first1, nil, cons]
add1 > s > [mark1, false, first1, nil, cons]
0 > [mark1, false, first1, nil, cons]
from1 > [mark1, false, first1, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(21) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FIRST(mark(X1), X2) → FIRST(X1, X2)
FIRST(active(X1), X2) → FIRST(X1, X2)
FIRST(X1, active(X2)) → FIRST(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(22) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


FIRST(X1, active(X2)) → FIRST(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
FIRST(x1, x2)  =  FIRST(x2)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  x2
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Lexicographic Path Order [LPO].
Precedence:
FIRST1 > [false, first, nil, cons]
[mark1, active1, and1, if2, 0, from] > true > [false, first, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(23) Obligation:

Q DP problem:
The TRS P consists of the following rules:

FIRST(mark(X1), X2) → FIRST(X1, X2)
FIRST(active(X1), X2) → FIRST(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(24) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


FIRST(mark(X1), X2) → FIRST(X1, X2)
FIRST(active(X1), X2) → FIRST(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
FIRST(x1, x2)  =  FIRST(x1)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  x2
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
true > [mark1, active1] > and1 > [FIRST1, false, add1, first, nil]
true > [mark1, active1] > if2 > [FIRST1, false, add1, first, nil]
true > [mark1, active1] > 0 > [FIRST1, false, add1, first, nil]
true > [mark1, active1] > from1 > [FIRST1, false, add1, first, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(25) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(26) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(27) TRUE

(28) Obligation:

Q DP problem:
The TRS P consists of the following rules:

S(active(X)) → S(X)
S(mark(X)) → S(X)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(29) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


S(active(X)) → S(X)
S(mark(X)) → S(X)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
S(x1)  =  S(x1)
active(x1)  =  active(x1)
mark(x1)  =  mark(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1, x2)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
S1 > [false, nil, cons]
and1 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
and1 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]
if2 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
if2 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]
add1 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
add1 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]
from1 > [mark1, first2] > true > [active1, 0] > [false, nil, cons]
from1 > [mark1, first2] > s > [active1, 0] > [false, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(30) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(31) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(32) TRUE

(33) Obligation:

Q DP problem:
The TRS P consists of the following rules:

ADD(X1, mark(X2)) → ADD(X1, X2)
ADD(mark(X1), X2) → ADD(X1, X2)
ADD(active(X1), X2) → ADD(X1, X2)
ADD(X1, active(X2)) → ADD(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(34) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


ADD(X1, mark(X2)) → ADD(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
ADD(x1, x2)  =  x2
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, false, first1, nil, cons]
true > [mark1, false, first1, nil, cons]
if2 > [mark1, false, first1, nil, cons]
add1 > s > [mark1, false, first1, nil, cons]
0 > [mark1, false, first1, nil, cons]
from1 > [mark1, false, first1, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(35) Obligation:

Q DP problem:
The TRS P consists of the following rules:

ADD(mark(X1), X2) → ADD(X1, X2)
ADD(active(X1), X2) → ADD(X1, X2)
ADD(X1, active(X2)) → ADD(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(36) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


ADD(X1, active(X2)) → ADD(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
ADD(x1, x2)  =  ADD(x2)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  x2
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Lexicographic Path Order [LPO].
Precedence:
ADD1 > [false, first, nil, cons]
[mark1, active1, and1, if2, 0, from] > true > [false, first, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(37) Obligation:

Q DP problem:
The TRS P consists of the following rules:

ADD(mark(X1), X2) → ADD(X1, X2)
ADD(active(X1), X2) → ADD(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(38) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


ADD(mark(X1), X2) → ADD(X1, X2)
ADD(active(X1), X2) → ADD(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
ADD(x1, x2)  =  ADD(x1)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  x2
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
true > [mark1, active1] > and1 > [ADD1, false, add1, first, nil]
true > [mark1, active1] > if2 > [ADD1, false, add1, first, nil]
true > [mark1, active1] > 0 > [ADD1, false, add1, first, nil]
true > [mark1, active1] > from1 > [ADD1, false, add1, first, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(39) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(40) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(41) TRUE

(42) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(X1, mark(X2), X3) → IF(X1, X2, X3)
IF(mark(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, X2, mark(X3)) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, active(X2), X3) → IF(X1, X2, X3)
IF(X1, X2, active(X3)) → IF(X1, X2, X3)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(43) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


IF(X1, X2, mark(X3)) → IF(X1, X2, X3)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
IF(x1, x2, x3)  =  IF(x3)
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
IF1 > [mark1, false, add1, s, first1, nil, cons]
and1 > [mark1, false, add1, s, first1, nil, cons]
true > [mark1, false, add1, s, first1, nil, cons]
if2 > [mark1, false, add1, s, first1, nil, cons]
0 > [mark1, false, add1, s, first1, nil, cons]
from1 > [mark1, false, add1, s, first1, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(44) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(X1, mark(X2), X3) → IF(X1, X2, X3)
IF(mark(X1), X2, X3) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, active(X2), X3) → IF(X1, X2, X3)
IF(X1, X2, active(X3)) → IF(X1, X2, X3)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(45) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


IF(X1, X2, active(X3)) → IF(X1, X2, X3)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
IF(x1, x2, x3)  =  IF(x3)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1, x2)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, first2] > [active1, 0] > [IF1, false, s, nil, cons]
and1 > [mark1, first2] > true > [IF1, false, s, nil, cons]
if2 > [mark1, first2] > [active1, 0] > [IF1, false, s, nil, cons]
if2 > [mark1, first2] > true > [IF1, false, s, nil, cons]
add1 > [mark1, first2] > [active1, 0] > [IF1, false, s, nil, cons]
add1 > [mark1, first2] > true > [IF1, false, s, nil, cons]
from > [mark1, first2] > [active1, 0] > [IF1, false, s, nil, cons]
from > [mark1, first2] > true > [IF1, false, s, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(46) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(X1, mark(X2), X3) → IF(X1, X2, X3)
IF(mark(X1), X2, X3) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, active(X2), X3) → IF(X1, X2, X3)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(47) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


IF(X1, mark(X2), X3) → IF(X1, X2, X3)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
IF(x1, x2, x3)  =  IF(x2)
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1, x2)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, first2] > true > [IF1, false, s, nil, cons]
if2 > [mark1, first2] > true > [IF1, false, s, nil, cons]
add1 > [mark1, first2] > true > [IF1, false, s, nil, cons]
0 > [mark1, first2] > true > [IF1, false, s, nil, cons]
from1 > [mark1, first2] > true > [IF1, false, s, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(48) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(mark(X1), X2, X3) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)
IF(X1, active(X2), X3) → IF(X1, X2, X3)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(49) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


IF(X1, active(X2), X3) → IF(X1, X2, X3)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
IF(x1, x2, x3)  =  IF(x2)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > mark1 > [active1, 0] > [IF1, false, s, nil, cons]
and1 > mark1 > true > [IF1, false, s, nil, cons]
if2 > mark1 > [active1, 0] > [IF1, false, s, nil, cons]
if2 > mark1 > true > [IF1, false, s, nil, cons]
add1 > mark1 > [active1, 0] > [IF1, false, s, nil, cons]
add1 > mark1 > true > [IF1, false, s, nil, cons]
first > mark1 > [active1, 0] > [IF1, false, s, nil, cons]
first > mark1 > true > [IF1, false, s, nil, cons]
from1 > mark1 > [active1, 0] > [IF1, false, s, nil, cons]
from1 > mark1 > true > [IF1, false, s, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(50) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(mark(X1), X2, X3) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(51) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


IF(mark(X1), X2, X3) → IF(X1, X2, X3)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
IF(x1, x2, x3)  =  IF(x1)
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x2)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, first1] > IF1 > [false, s, nil]
and1 > [mark1, first1] > true > [false, s, nil]
and1 > [mark1, first1] > 0 > [false, s, nil]
and1 > [mark1, first1] > cons > [false, s, nil]
if2 > [mark1, first1] > IF1 > [false, s, nil]
if2 > [mark1, first1] > true > [false, s, nil]
if2 > [mark1, first1] > 0 > [false, s, nil]
if2 > [mark1, first1] > cons > [false, s, nil]
add1 > [mark1, first1] > IF1 > [false, s, nil]
add1 > [mark1, first1] > true > [false, s, nil]
add1 > [mark1, first1] > 0 > [false, s, nil]
add1 > [mark1, first1] > cons > [false, s, nil]
from1 > [mark1, first1] > IF1 > [false, s, nil]
from1 > [mark1, first1] > true > [false, s, nil]
from1 > [mark1, first1] > 0 > [false, s, nil]
from1 > [mark1, first1] > cons > [false, s, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(52) Obligation:

Q DP problem:
The TRS P consists of the following rules:

IF(active(X1), X2, X3) → IF(X1, X2, X3)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(53) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


IF(active(X1), X2, X3) → IF(X1, X2, X3)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
IF(x1, x2, x3)  =  IF(x1, x2)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
mark(x1)  =  mark(x1)
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > mark1 > [active1, 0] > IF2 > [false, s, nil, cons]
true > mark1 > [active1, 0] > IF2 > [false, s, nil, cons]
if2 > mark1 > [active1, 0] > IF2 > [false, s, nil, cons]
add1 > mark1 > [active1, 0] > IF2 > [false, s, nil, cons]
first > mark1 > [active1, 0] > IF2 > [false, s, nil, cons]
from1 > mark1 > [active1, 0] > IF2 > [false, s, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(54) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(55) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(56) TRUE

(57) Obligation:

Q DP problem:
The TRS P consists of the following rules:

AND(X1, mark(X2)) → AND(X1, X2)
AND(mark(X1), X2) → AND(X1, X2)
AND(active(X1), X2) → AND(X1, X2)
AND(X1, active(X2)) → AND(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(58) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


AND(X1, mark(X2)) → AND(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
AND(x1, x2)  =  x2
mark(x1)  =  mark(x1)
active(x1)  =  x1
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
and1 > [mark1, false, first1, nil, cons]
true > [mark1, false, first1, nil, cons]
if2 > [mark1, false, first1, nil, cons]
add1 > s > [mark1, false, first1, nil, cons]
0 > [mark1, false, first1, nil, cons]
from1 > [mark1, false, first1, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(59) Obligation:

Q DP problem:
The TRS P consists of the following rules:

AND(mark(X1), X2) → AND(X1, X2)
AND(active(X1), X2) → AND(X1, X2)
AND(X1, active(X2)) → AND(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(60) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


AND(X1, active(X2)) → AND(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
AND(x1, x2)  =  AND(x2)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  x2
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Lexicographic Path Order [LPO].
Precedence:
AND1 > [false, first, nil, cons]
[mark1, active1, and1, if2, 0, from] > true > [false, first, nil, cons]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(61) Obligation:

Q DP problem:
The TRS P consists of the following rules:

AND(mark(X1), X2) → AND(X1, X2)
AND(active(X1), X2) → AND(X1, X2)

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(62) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


AND(mark(X1), X2) → AND(X1, X2)
AND(active(X1), X2) → AND(X1, X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
AND(x1, x2)  =  AND(x1)
mark(x1)  =  mark(x1)
active(x1)  =  active(x1)
and(x1, x2)  =  and(x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
0  =  0
s(x1)  =  x1
first(x1, x2)  =  first
nil  =  nil
cons(x1, x2)  =  x2
from(x1)  =  from(x1)

Lexicographic Path Order [LPO].
Precedence:
true > [mark1, active1] > and1 > [AND1, false, add1, first, nil]
true > [mark1, active1] > if2 > [AND1, false, add1, first, nil]
true > [mark1, active1] > 0 > [AND1, false, add1, first, nil]
true > [mark1, active1] > from1 > [AND1, false, add1, first, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(63) Obligation:

Q DP problem:
P is empty.
The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(64) PisEmptyProof (EQUIVALENT transformation)

The TRS P is empty. Hence, there is no (P,Q,R) chain.

(65) TRUE

(66) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MARK(and(X1, X2)) → ACTIVE(and(mark(X1), X2))
ACTIVE(and(true, X)) → MARK(X)
MARK(and(X1, X2)) → MARK(X1)
MARK(if(X1, X2, X3)) → ACTIVE(if(mark(X1), X2, X3))
ACTIVE(if(true, X, Y)) → MARK(X)
MARK(if(X1, X2, X3)) → MARK(X1)
MARK(add(X1, X2)) → ACTIVE(add(mark(X1), X2))
ACTIVE(if(false, X, Y)) → MARK(Y)
MARK(add(X1, X2)) → MARK(X1)
MARK(s(X)) → ACTIVE(s(X))
ACTIVE(add(0, X)) → MARK(X)
MARK(first(X1, X2)) → ACTIVE(first(mark(X1), mark(X2)))
ACTIVE(add(s(X), Y)) → MARK(s(add(X, Y)))
MARK(first(X1, X2)) → MARK(X1)
MARK(first(X1, X2)) → MARK(X2)
MARK(cons(X1, X2)) → ACTIVE(cons(X1, X2))
ACTIVE(first(s(X), cons(Y, Z))) → MARK(cons(Y, first(X, Z)))
MARK(from(X)) → ACTIVE(from(X))
ACTIVE(from(X)) → MARK(cons(X, from(s(X))))

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(67) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


ACTIVE(and(true, X)) → MARK(X)
MARK(and(X1, X2)) → MARK(X1)
ACTIVE(if(true, X, Y)) → MARK(X)
MARK(if(X1, X2, X3)) → MARK(X1)
ACTIVE(if(false, X, Y)) → MARK(Y)
MARK(add(X1, X2)) → MARK(X1)
ACTIVE(add(0, X)) → MARK(X)
MARK(first(X1, X2)) → MARK(X1)
MARK(first(X1, X2)) → MARK(X2)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
MARK(x1)  =  MARK(x1)
and(x1, x2)  =  and(x1, x2)
ACTIVE(x1)  =  ACTIVE(x1)
mark(x1)  =  x1
true  =  true
if(x1, x2, x3)  =  if(x1, x2, x3)
add(x1, x2)  =  add(x1, x2)
false  =  false
s(x1)  =  x1
0  =  0
first(x1, x2)  =  first(x1, x2)
cons(x1, x2)  =  x2
from(x1)  =  x1
active(x1)  =  x1
nil  =  nil

Lexicographic Path Order [LPO].
Precedence:
and2 > [MARK1, ACTIVE1, add2, first2, nil]
true > [MARK1, ACTIVE1, add2, first2, nil]
if3 > [MARK1, ACTIVE1, add2, first2, nil]
false > [MARK1, ACTIVE1, add2, first2, nil]
0 > [MARK1, ACTIVE1, add2, first2, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(68) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MARK(and(X1, X2)) → ACTIVE(and(mark(X1), X2))
MARK(if(X1, X2, X3)) → ACTIVE(if(mark(X1), X2, X3))
MARK(add(X1, X2)) → ACTIVE(add(mark(X1), X2))
MARK(s(X)) → ACTIVE(s(X))
MARK(first(X1, X2)) → ACTIVE(first(mark(X1), mark(X2)))
ACTIVE(add(s(X), Y)) → MARK(s(add(X, Y)))
MARK(cons(X1, X2)) → ACTIVE(cons(X1, X2))
ACTIVE(first(s(X), cons(Y, Z))) → MARK(cons(Y, first(X, Z)))
MARK(from(X)) → ACTIVE(from(X))
ACTIVE(from(X)) → MARK(cons(X, from(s(X))))

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(69) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


ACTIVE(add(s(X), Y)) → MARK(s(add(X, Y)))
ACTIVE(first(s(X), cons(Y, Z))) → MARK(cons(Y, first(X, Z)))
ACTIVE(from(X)) → MARK(cons(X, from(s(X))))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
MARK(x1)  =  x1
and(x1, x2)  =  and(x1, x2)
ACTIVE(x1)  =  x1
mark(x1)  =  x1
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x2)
s(x1)  =  s
first(x1, x2)  =  first(x2)
cons(x1, x2)  =  cons
from(x1)  =  from(x1)
active(x1)  =  x1
true  =  true
false  =  false
0  =  0
nil  =  nil

Lexicographic Path Order [LPO].
Precedence:
and2 > [add1, s, first1, cons, from1, nil]
if2 > [add1, s, first1, cons, from1, nil]
true > [add1, s, first1, cons, from1, nil]
false > [add1, s, first1, cons, from1, nil]
0 > [add1, s, first1, cons, from1, nil]


The following usable rules [FROCOS05] were oriented:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

(70) Obligation:

Q DP problem:
The TRS P consists of the following rules:

MARK(and(X1, X2)) → ACTIVE(and(mark(X1), X2))
MARK(if(X1, X2, X3)) → ACTIVE(if(mark(X1), X2, X3))
MARK(add(X1, X2)) → ACTIVE(add(mark(X1), X2))
MARK(s(X)) → ACTIVE(s(X))
MARK(first(X1, X2)) → ACTIVE(first(mark(X1), mark(X2)))
MARK(cons(X1, X2)) → ACTIVE(cons(X1, X2))
MARK(from(X)) → ACTIVE(from(X))

The TRS R consists of the following rules:

active(and(true, X)) → mark(X)
active(and(false, Y)) → mark(false)
active(if(true, X, Y)) → mark(X)
active(if(false, X, Y)) → mark(Y)
active(add(0, X)) → mark(X)
active(add(s(X), Y)) → mark(s(add(X, Y)))
active(first(0, X)) → mark(nil)
active(first(s(X), cons(Y, Z))) → mark(cons(Y, first(X, Z)))
active(from(X)) → mark(cons(X, from(s(X))))
mark(and(X1, X2)) → active(and(mark(X1), X2))
mark(true) → active(true)
mark(false) → active(false)
mark(if(X1, X2, X3)) → active(if(mark(X1), X2, X3))
mark(add(X1, X2)) → active(add(mark(X1), X2))
mark(0) → active(0)
mark(s(X)) → active(s(X))
mark(first(X1, X2)) → active(first(mark(X1), mark(X2)))
mark(nil) → active(nil)
mark(cons(X1, X2)) → active(cons(X1, X2))
mark(from(X)) → active(from(X))
and(mark(X1), X2) → and(X1, X2)
and(X1, mark(X2)) → and(X1, X2)
and(active(X1), X2) → and(X1, X2)
and(X1, active(X2)) → and(X1, X2)
if(mark(X1), X2, X3) → if(X1, X2, X3)
if(X1, mark(X2), X3) → if(X1, X2, X3)
if(X1, X2, mark(X3)) → if(X1, X2, X3)
if(active(X1), X2, X3) → if(X1, X2, X3)
if(X1, active(X2), X3) → if(X1, X2, X3)
if(X1, X2, active(X3)) → if(X1, X2, X3)
add(mark(X1), X2) → add(X1, X2)
add(X1, mark(X2)) → add(X1, X2)
add(active(X1), X2) → add(X1, X2)
add(X1, active(X2)) → add(X1, X2)
s(mark(X)) → s(X)
s(active(X)) → s(X)
first(mark(X1), X2) → first(X1, X2)
first(X1, mark(X2)) → first(X1, X2)
first(active(X1), X2) → first(X1, X2)
first(X1, active(X2)) → first(X1, X2)
cons(mark(X1), X2) → cons(X1, X2)
cons(X1, mark(X2)) → cons(X1, X2)
cons(active(X1), X2) → cons(X1, X2)
cons(X1, active(X2)) → cons(X1, X2)
from(mark(X)) → from(X)
from(active(X)) → from(X)

Q is empty.
We have to consider all minimal (P,Q,R)-chains.

(71) DependencyGraphProof (EQUIVALENT transformation)

The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 0 SCCs with 7 less nodes.

(72) TRUE