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

0 QTRS
↳1 DependencyPairsProof (⇔)
↳2 QDP
↳3 DependencyGraphProof (⇔)
↳4 AND
    ↳5 QDP
        ↳6 QDPOrderProof (⇔)
        ↳7 QDP
        ↳8 QDPOrderProof (⇔)
        ↳9 QDP
        ↳10 QDPOrderProof (⇔)
        ↳11 QDP
        ↳12 PisEmptyProof (⇔)
        ↳13 TRUE
    ↳14 QDP
        ↳15 QDPOrderProof (⇔)
        ↳16 QDP
        ↳17 PisEmptyProof (⇔)
        ↳18 TRUE
    ↳19 QDP
        ↳20 QDPOrderProof (⇔)
        ↳21 QDP
        ↳22 PisEmptyProof (⇔)
        ↳23 TRUE
    ↳24 QDP
        ↳25 QDPOrderProof (⇔)
        ↳26 QDP
        ↳27 PisEmptyProof (⇔)
        ↳28 TRUE
    ↳29 QDP
        ↳30 QDPOrderProof (⇔)
        ↳31 QDP
        ↳32 PisEmptyProof (⇔)
        ↳33 TRUE
    ↳34 QDP
        ↳35 QDPOrderProof (⇔)
        ↳36 QDP
        ↳37 QDPOrderProof (⇔)
        ↳38 QDP
        ↳39 QDPOrderProof (⇔)
        ↳40 QDP
        ↳41 PisEmptyProof (⇔)
        ↳42 TRUE

(0) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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:

TOP(active(c)) → TOP(mark(c))
TOP(mark(x)) → TOP(check(x))
TOP(mark(x)) → CHECK(x)
CHECK(f(x)) → F(check(x))
CHECK(f(x)) → CHECK(x)
CHECK(x) → START(match(f(X), x))
CHECK(x) → MATCH(f(X), x)
CHECK(x) → F(X)
MATCH(f(x), f(y)) → F(match(x, y))
MATCH(f(x), f(y)) → MATCH(x, y)
MATCH(X, x) → PROPER(x)
PROPER(f(x)) → F(proper(x))
PROPER(f(x)) → PROPER(x)
F(ok(x)) → F(x)
F(found(x)) → F(x)
TOP(found(x)) → TOP(active(x))
TOP(found(x)) → ACTIVE(x)
ACTIVE(f(x)) → F(active(x))
ACTIVE(f(x)) → ACTIVE(x)
F(mark(x)) → F(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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 6 SCCs with 10 less nodes.

(4) Complex Obligation (AND)

(5) Obligation:

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

F(found(x)) → F(x)
F(ok(x)) → F(x)
F(mark(x)) → F(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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.


F(found(x)) → F(x)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
F(x0, x1)  =  F(x1)

Tags:
F has argument tags [1,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(F(x1)) = 1   
POL(found(x1)) = 1 + x1   
POL(mark(x1)) = x1   
POL(ok(x1)) = x1   

The following usable rules [FROCOS05] were oriented: none

(7) Obligation:

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

F(ok(x)) → F(x)
F(mark(x)) → F(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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.


F(ok(x)) → F(x)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
F(x0, x1)  =  F(x1)

Tags:
F has argument tags [0,0] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(F(x1)) = 1   
POL(mark(x1)) = x1   
POL(ok(x1)) = 1 + x1   

The following usable rules [FROCOS05] were oriented: none

(9) Obligation:

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

F(mark(x)) → F(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(10) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


F(mark(x)) → F(x)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
F(x0, x1)  =  F(x1)

Tags:
F has argument tags [1,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(F(x1)) = 0   
POL(mark(x1)) = 1 + x1   

The following usable rules [FROCOS05] were oriented: none

(11) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(12) PisEmptyProof (EQUIVALENT transformation)

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

(13) TRUE

(14) Obligation:

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

ACTIVE(f(x)) → ACTIVE(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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.


ACTIVE(f(x)) → ACTIVE(x)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
ACTIVE(x0, x1)  =  ACTIVE(x1)

Tags:
ACTIVE has argument tags [1,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(ACTIVE(x1)) = 0   
POL(f(x1)) = 1 + x1   

The following usable rules [FROCOS05] were oriented: none

(16) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(17) PisEmptyProof (EQUIVALENT transformation)

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

(18) TRUE

(19) Obligation:

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

PROPER(f(x)) → PROPER(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(20) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


PROPER(f(x)) → PROPER(x)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
PROPER(x0, x1)  =  PROPER(x1)

Tags:
PROPER has argument tags [1,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(PROPER(x1)) = 0   
POL(f(x1)) = 1 + x1   

The following usable rules [FROCOS05] were oriented: none

(21) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(22) PisEmptyProof (EQUIVALENT transformation)

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

(23) TRUE

(24) Obligation:

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

MATCH(f(x), f(y)) → MATCH(x, y)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(25) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


MATCH(f(x), f(y)) → MATCH(x, y)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
MATCH(x0, x1, x2)  =  MATCH(x0, x1, x2)

Tags:
MATCH has argument tags [2,3,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(MATCH(x1, x2)) = 1   
POL(f(x1)) = 1 + x1   

The following usable rules [FROCOS05] were oriented: none

(26) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(27) PisEmptyProof (EQUIVALENT transformation)

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

(28) TRUE

(29) Obligation:

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

CHECK(f(x)) → CHECK(x)

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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.


CHECK(f(x)) → CHECK(x)
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
CHECK(x0, x1)  =  CHECK(x1)

Tags:
CHECK has argument tags [1,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(CHECK(x1)) = 0   
POL(f(x1)) = 1 + x1   

The following usable rules [FROCOS05] were oriented: none

(31) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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:

TOP(mark(x)) → TOP(check(x))
TOP(found(x)) → TOP(active(x))
TOP(active(c)) → TOP(mark(c))

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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.


TOP(active(c)) → TOP(mark(c))
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
TOP(x0, x1)  =  TOP(x0)

Tags:
TOP has argument tags [1,0] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(TOP(x1)) = 1 + x1   
POL(X) = 0   
POL(active(x1)) = x1   
POL(c) = 1   
POL(check(x1)) = 0   
POL(f(x1)) = 0   
POL(found(x1)) = x1   
POL(mark(x1)) = 0   
POL(match(x1, x2)) = 0   
POL(ok(x1)) = x1   
POL(proper(x1)) = 0   
POL(start(x1)) = x1   

The following usable rules [FROCOS05] were oriented:

check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
active(f(x)) → mark(x)
active(f(x)) → f(active(x))
f(ok(x)) → ok(f(x))
f(found(x)) → found(f(x))
f(mark(x)) → mark(f(x))
match(f(x), f(y)) → f(match(x, y))
start(ok(x)) → found(x)

(36) Obligation:

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

TOP(mark(x)) → TOP(check(x))
TOP(found(x)) → TOP(active(x))

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(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.


TOP(mark(x)) → TOP(check(x))
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
TOP(x0, x1)  =  TOP(x0)

Tags:
TOP has argument tags [1,0] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(TOP(x1)) = 1 + x1   
POL(X) = 0   
POL(active(x1)) = x1   
POL(c) = 0   
POL(check(x1)) = x1   
POL(f(x1)) = 1 + x1   
POL(found(x1)) = x1   
POL(mark(x1)) = 1 + x1   
POL(match(x1, x2)) = x2   
POL(ok(x1)) = x1   
POL(proper(x1)) = x1   
POL(start(x1)) = x1   

The following usable rules [FROCOS05] were oriented:

check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
active(f(x)) → mark(x)
active(f(x)) → f(active(x))
f(ok(x)) → ok(f(x))
f(found(x)) → found(f(x))
f(mark(x)) → mark(f(x))
match(f(x), f(y)) → f(match(x, y))
start(ok(x)) → found(x)
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))

(38) Obligation:

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

TOP(found(x)) → TOP(active(x))

The TRS R consists of the following rules:

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(39) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


TOP(found(x)) → TOP(active(x))
The remaining pairs can at least be oriented weakly.
Used ordering: SCNP Order with the following components:
Level mapping:
Top level AFS:
TOP(x0, x1)  =  TOP(x1)

Tags:
TOP has argument tags [1,1] and root tag 0

Comparison: MAX
Underlying order for the size change arcs and the rules of R:
Polynomial interpretation [POLO]:

POL(TOP(x1)) = 0   
POL(active(x1)) = 0   
POL(f(x1)) = x1   
POL(found(x1)) = 1   
POL(mark(x1)) = 0   
POL(ok(x1)) = 1   

The following usable rules [FROCOS05] were oriented: none

(40) Obligation:

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

active(f(x)) → mark(x)
top(active(c)) → top(mark(c))
top(mark(x)) → top(check(x))
check(f(x)) → f(check(x))
check(x) → start(match(f(X), x))
match(f(x), f(y)) → f(match(x, y))
match(X, x) → proper(x)
proper(c) → ok(c)
proper(f(x)) → f(proper(x))
f(ok(x)) → ok(f(x))
start(ok(x)) → found(x)
f(found(x)) → found(f(x))
top(found(x)) → top(active(x))
active(f(x)) → f(active(x))
f(mark(x)) → mark(f(x))

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

(41) PisEmptyProof (EQUIVALENT transformation)

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

(42) TRUE