(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(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)  =  x1
mark(x1)  =  mark(x1)
and(x1, x2)  =  and(x1, x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x1, x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Recursive Path Order [RPO].
Precedence:
if2 > [FROM1, mark1, and2, add2, first1] > true > [false, nil, cons]
if2 > [FROM1, mark1, and2, add2, first1] > 0 > [false, nil, cons]
from > s > [FROM1, mark1, and2, add2, first1] > true > [false, nil, cons]
from > s > [FROM1, mark1, and2, add2, first1] > 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:
The TRS P consists of the following rules:

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.

(8) 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)
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)
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)  =  x2
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
[active1, mark1] > FROM1 > [and1, false, if2, add1, s, first, nil, from1]
[active1, mark1] > true > [and1, false, if2, add1, s, first, nil, from1]
[active1, mark1] > 0 > [and1, false, if2, add1, s, first, nil, from1]


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)

(9) 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.

(10) PisEmptyProof (EQUIVALENT transformation)

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

(11) TRUE

(12) 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.

(13) 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)  =  CONS(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
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, add1, from1] > [CONS1, false, s, nil, cons]
true > [mark1, add1, from1] > [CONS1, false, s, nil, cons]
if2 > [mark1, add1, from1] > [CONS1, false, s, nil, cons]
0 > [mark1, add1, from1] > [CONS1, false, s, nil, cons]
first > [mark1, add1, from1] > [CONS1, 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)

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

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

Recursive Path Order [RPO].
Precedence:
true > [mark1, and1, from1] > [CONS1, false, s, nil, cons]
if2 > [mark1, and1, from1] > [CONS1, false, s, nil, cons]
add1 > [mark1, and1, from1] > [CONS1, false, s, nil, cons]
0 > [mark1, and1, from1] > [CONS1, false, s, nil, cons]
first > [mark1, and1, from1] > [CONS1, 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)

(16) Obligation:

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

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.

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

Recursive Path Order [RPO].
Precedence:
true > [active1, and1, mark1, false, first, nil] > [CONS1, if2, add1, s, cons, from]
0 > [active1, and1, mark1, false, first, nil] > [CONS1, if2, add1, s, cons, from]


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)

(18) Obligation:

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

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.

(19) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


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)
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(x1, x2)
nil  =  nil
cons(x1, x2)  =  x1
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, first2] > [active1, 0] > CONS1 > [false, nil]
and1 > [mark1, first2] > true > [false, nil]
if2 > [mark1, first2] > [active1, 0] > CONS1 > [false, nil]
if2 > [mark1, first2] > true > [false, nil]
[add1, s, from1] > [mark1, first2] > [active1, 0] > CONS1 > [false, nil]
[add1, s, from1] > [mark1, first2] > true > [false, 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)

(20) 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.

(21) PisEmptyProof (EQUIVALENT transformation)

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

(22) TRUE

(23) 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.

(24) 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)  =  FIRST(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
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, add1, from1] > [FIRST1, false, s, nil, cons]
true > [mark1, add1, from1] > [FIRST1, false, s, nil, cons]
if2 > [mark1, add1, from1] > [FIRST1, false, s, nil, cons]
0 > [mark1, add1, from1] > [FIRST1, false, s, nil, cons]
first > [mark1, add1, from1] > [FIRST1, 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)

(25) 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.

(26) 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)
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)  =  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)

Recursive Path Order [RPO].
Precedence:
true > [mark1, and1, from1] > [FIRST1, false, s, nil, cons]
if2 > [mark1, and1, from1] > [FIRST1, false, s, nil, cons]
add1 > [mark1, and1, from1] > [FIRST1, false, s, nil, cons]
0 > [mark1, and1, from1] > [FIRST1, false, s, nil, cons]
first > [mark1, and1, from1] > [FIRST1, 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)

(27) Obligation:

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

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.

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

Recursive Path Order [RPO].
Precedence:
true > [active1, and1, mark1, false, first, nil] > [FIRST1, if2, add1, s, cons, from]
0 > [active1, and1, mark1, false, first, nil] > [FIRST1, if2, add1, s, cons, from]


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)

(29) Obligation:

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

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.

(30) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


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)
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(x1, x2)
nil  =  nil
cons(x1, x2)  =  x1
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, first2] > [active1, 0] > FIRST1 > [false, nil]
and1 > [mark1, first2] > true > [false, nil]
if2 > [mark1, first2] > [active1, 0] > FIRST1 > [false, nil]
if2 > [mark1, first2] > true > [false, nil]
[add1, s, from1] > [mark1, first2] > [active1, 0] > FIRST1 > [false, nil]
[add1, s, from1] > [mark1, first2] > true > [false, 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)

(31) 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.

(32) PisEmptyProof (EQUIVALENT transformation)

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

(33) TRUE

(34) 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.

(35) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


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)  =  x1
mark(x1)  =  mark(x1)
and(x1, x2)  =  and(x1, x2)
true  =  true
false  =  false
if(x1, x2, x3)  =  if(x2, x3)
add(x1, x2)  =  add(x1, x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from

Recursive Path Order [RPO].
Precedence:
if2 > [S1, mark1, and2, add2, first1] > true > [false, nil, cons]
if2 > [S1, mark1, and2, add2, first1] > 0 > [false, nil, cons]
from > s > [S1, mark1, and2, add2, first1] > true > [false, nil, cons]
from > s > [S1, mark1, and2, add2, first1] > 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)

(36) Obligation:

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

S(active(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.

(37) 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)
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)
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)  =  x2
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
[active1, mark1] > S1 > [and1, false, if2, add1, s, first, nil, from1]
[active1, mark1] > true > [and1, false, if2, add1, s, first, nil, from1]
[active1, mark1] > 0 > [and1, false, if2, add1, s, first, nil, from1]


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)

(38) 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.

(39) PisEmptyProof (EQUIVALENT transformation)

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

(40) TRUE

(41) 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.

(42) 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)  =  ADD(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
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, add1, from1] > [ADD1, false, s, nil, cons]
true > [mark1, add1, from1] > [ADD1, false, s, nil, cons]
if2 > [mark1, add1, from1] > [ADD1, false, s, nil, cons]
0 > [mark1, add1, from1] > [ADD1, false, s, nil, cons]
first > [mark1, add1, from1] > [ADD1, 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)

(43) 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.

(44) 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)
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)  =  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)

Recursive Path Order [RPO].
Precedence:
true > [mark1, and1, from1] > [ADD1, false, s, nil, cons]
if2 > [mark1, and1, from1] > [ADD1, false, s, nil, cons]
add1 > [mark1, and1, from1] > [ADD1, false, s, nil, cons]
0 > [mark1, and1, from1] > [ADD1, false, s, nil, cons]
first > [mark1, and1, from1] > [ADD1, 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)

(45) Obligation:

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

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.

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

Recursive Path Order [RPO].
Precedence:
true > [active1, and1, mark1, false, first, nil] > [ADD1, if2, add1, s, cons, from]
0 > [active1, and1, mark1, false, first, nil] > [ADD1, if2, add1, s, cons, from]


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)

(47) Obligation:

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

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.

(48) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


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)
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(x1, x2)
nil  =  nil
cons(x1, x2)  =  x1
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, first2] > [active1, 0] > ADD1 > [false, nil]
and1 > [mark1, first2] > true > [false, nil]
if2 > [mark1, first2] > [active1, 0] > ADD1 > [false, nil]
if2 > [mark1, first2] > true > [false, nil]
[add1, s, from1] > [mark1, first2] > [active1, 0] > ADD1 > [false, nil]
[add1, s, from1] > [mark1, first2] > true > [false, 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)

(49) 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.

(50) PisEmptyProof (EQUIVALENT transformation)

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

(51) TRUE

(52) 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.

(53) 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)
IF(X1, X2, mark(X3)) → IF(X1, X2, X3)
IF(active(X1), X2, X3) → IF(X1, X2, X3)
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(x1, 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
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, active1] > if2 > [IF2, false, cons]
and1 > [mark1, active1] > [first, nil] > [IF2, false, cons]
true > [mark1, active1] > if2 > [IF2, false, cons]
true > [mark1, active1] > [first, nil] > [IF2, false, cons]
add1 > s > [mark1, active1] > if2 > [IF2, false, cons]
add1 > s > [mark1, active1] > [first, nil] > [IF2, false, cons]
0 > [mark1, active1] > if2 > [IF2, false, cons]
0 > [mark1, active1] > [first, nil] > [IF2, false, cons]
from1 > s > [mark1, active1] > if2 > [IF2, false, cons]
from1 > s > [mark1, active1] > [first, nil] > [IF2, false, 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:
The TRS P consists of the following rules:

IF(X1, mark(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.

(55) 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, 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
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
[and1, false] > [mark1, from1] > s > [IF2, nil, cons]
true > [mark1, from1] > s > [IF2, nil, cons]
if2 > [mark1, from1] > s > [IF2, nil, cons]
add1 > [mark1, from1] > s > [IF2, nil, cons]
0 > [mark1, from1] > s > [IF2, nil, cons]
first > [mark1, from1] > s > [IF2, 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)

(56) Obligation:

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

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.

(57) 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)
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(x1, x2)
0  =  0
s(x1)  =  s
first(x1, x2)  =  first(x1, x2)
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, if2, add2, first2] > true > false
and1 > [mark1, if2, add2, first2] > s > [active1, 0, nil, cons] > IF1 > false
from1 > [mark1, if2, add2, first2] > true > false
from1 > [mark1, if2, add2, first2] > s > [active1, 0, nil, cons] > IF1 > false


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)

(58) 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.

(59) PisEmptyProof (EQUIVALENT transformation)

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

(60) TRUE

(61) 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.

(62) 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)  =  AND(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
nil  =  nil
cons(x1, x2)  =  cons
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, add1, from1] > [AND1, false, s, nil, cons]
true > [mark1, add1, from1] > [AND1, false, s, nil, cons]
if2 > [mark1, add1, from1] > [AND1, false, s, nil, cons]
0 > [mark1, add1, from1] > [AND1, false, s, nil, cons]
first > [mark1, add1, from1] > [AND1, 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)

(63) 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.

(64) 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)
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)  =  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)

Recursive Path Order [RPO].
Precedence:
true > [mark1, and1, from1] > [AND1, false, s, nil, cons]
if2 > [mark1, and1, from1] > [AND1, false, s, nil, cons]
add1 > [mark1, and1, from1] > [AND1, false, s, nil, cons]
0 > [mark1, and1, from1] > [AND1, false, s, nil, cons]
first > [mark1, and1, from1] > [AND1, 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)

(65) Obligation:

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

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.

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

Recursive Path Order [RPO].
Precedence:
true > [active1, and1, mark1, false, first, nil] > [AND1, if2, add1, s, cons, from]
0 > [active1, and1, mark1, false, first, nil] > [AND1, if2, add1, s, cons, from]


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)

(67) Obligation:

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

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.

(68) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


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)
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(x1, x2)
nil  =  nil
cons(x1, x2)  =  x1
from(x1)  =  from(x1)

Recursive Path Order [RPO].
Precedence:
and1 > [mark1, first2] > [active1, 0] > AND1 > [false, nil]
and1 > [mark1, first2] > true > [false, nil]
if2 > [mark1, first2] > [active1, 0] > AND1 > [false, nil]
if2 > [mark1, first2] > true > [false, nil]
[add1, s, from1] > [mark1, first2] > [active1, 0] > AND1 > [false, nil]
[add1, s, from1] > [mark1, first2] > true > [false, 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)

(69) 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.

(70) PisEmptyProof (EQUIVALENT transformation)

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

(71) TRUE

(72) 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.

(73) 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)
ACTIVE(add(s(X), Y)) → MARK(s(add(X, Y)))
MARK(first(X1, X2)) → MARK(X1)
MARK(first(X1, X2)) → MARK(X2)
ACTIVE(first(s(X), cons(Y, Z))) → MARK(cons(Y, first(X, Z)))
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)  =  s(x1)
0  =  0
first(x1, x2)  =  first(x1, x2)
cons(x1, x2)  =  x2
from(x1)  =  from
active(x1)  =  x1
nil  =  nil

Recursive Path Order [RPO].
Precedence:
and2 > [MARK1, ACTIVE1, if3, false, s1, first2, nil]
true > [MARK1, ACTIVE1, if3, false, s1, first2, nil]
add2 > [MARK1, ACTIVE1, if3, false, s1, first2, nil]
0 > [MARK1, ACTIVE1, if3, false, s1, first2, nil]
from > [MARK1, ACTIVE1, if3, false, s1, 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)

(74) 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))
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.

(75) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


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(x2)
ACTIVE(x1)  =  x1
mark(x1)  =  x1
if(x1, x2, x3)  =  if(x1, x2, x3)
add(x1, x2)  =  add(x2)
s(x1)  =  x1
first(x1, x2)  =  first
cons(x1, x2)  =  cons
from(x1)  =  from(x1)
active(x1)  =  x1
true  =  true
false  =  false
0  =  0
nil  =  nil

Recursive Path Order [RPO].
Precedence:
if3 > [and1, add1, first, cons, false, nil]
from1 > [and1, add1, first, cons, false, nil]
true > [and1, add1, first, cons, false, nil]
0 > [and1, add1, first, cons, false, 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)

(76) 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.

(77) DependencyGraphProof (EQUIVALENT transformation)

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

(78) TRUE