YES
proof of /export/starexec/sandbox2/benchmark/theBenchmark.xml
# AProVE Commit ID: 794c25de1cacf0d048858bcd21c9a779e1221865 marcel 20200619 unpublished dirty


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

(0) QTRS
(1) DependencyPairsProof [EQUIVALENT, 0 ms]
(2) QDP
(3) DependencyGraphProof [EQUIVALENT, 0 ms]
(4) AND
    (5) QDP
        (6) UsableRulesProof [EQUIVALENT, 0 ms]
        (7) QDP
        (8) QReductionProof [EQUIVALENT, 0 ms]
        (9) QDP
        (10) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (11) YES
    (12) QDP
        (13) UsableRulesProof [EQUIVALENT, 0 ms]
        (14) QDP
        (15) QReductionProof [EQUIVALENT, 0 ms]
        (16) QDP
        (17) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (18) YES
    (19) QDP
        (20) UsableRulesProof [EQUIVALENT, 0 ms]
        (21) QDP
        (22) QReductionProof [EQUIVALENT, 0 ms]
        (23) QDP
        (24) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (25) YES
    (26) QDP
        (27) UsableRulesProof [EQUIVALENT, 0 ms]
        (28) QDP
        (29) QReductionProof [EQUIVALENT, 0 ms]
        (30) QDP
        (31) QDPSizeChangeProof [EQUIVALENT, 0 ms]
        (32) YES
    (33) QDP
        (34) MRRProof [EQUIVALENT, 48 ms]
        (35) QDP
        (36) QDPOrderProof [EQUIVALENT, 26 ms]
        (37) QDP
        (38) QDPOrderProof [EQUIVALENT, 0 ms]
        (39) QDP
        (40) DependencyGraphProof [EQUIVALENT, 0 ms]
        (41) AND
            (42) QDP
                (43) TransformationProof [EQUIVALENT, 0 ms]
                (44) QDP
                (45) QDPQMonotonicMRRProof [EQUIVALENT, 28 ms]
                (46) QDP
                (47) MRRProof [EQUIVALENT, 0 ms]
                (48) QDP
                (49) UsableRulesProof [EQUIVALENT, 0 ms]
                (50) QDP
                (51) QReductionProof [EQUIVALENT, 0 ms]
                (52) QDP
                (53) MRRProof [EQUIVALENT, 8 ms]
                (54) QDP
                (55) RFCMatchBoundsDPProof [EQUIVALENT, 0 ms]
                (56) YES
            (57) QDP
                (58) UsableRulesProof [EQUIVALENT, 0 ms]
                (59) QDP
                (60) QReductionProof [EQUIVALENT, 0 ms]
                (61) QDP
                (62) QDPSizeChangeProof [EQUIVALENT, 0 ms]
                (63) YES


----------------------------------------

(0)
Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))


----------------------------------------

(1) DependencyPairsProof (EQUIVALENT)
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(f(0)) -> MARK(cons(0, f(s(0))))
   ACTIVE(f(0)) -> CONS(0, f(s(0)))
   ACTIVE(f(0)) -> F(s(0))
   ACTIVE(f(0)) -> S(0)
   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   ACTIVE(f(s(0))) -> F(p(s(0)))
   ACTIVE(f(s(0))) -> P(s(0))
   ACTIVE(p(s(X))) -> MARK(X)
   MARK(f(X)) -> ACTIVE(f(mark(X)))
   MARK(f(X)) -> F(mark(X))
   MARK(f(X)) -> MARK(X)
   MARK(0) -> ACTIVE(0)
   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   MARK(cons(X1, X2)) -> CONS(mark(X1), X2)
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   MARK(s(X)) -> S(mark(X))
   MARK(s(X)) -> MARK(X)
   MARK(p(X)) -> ACTIVE(p(mark(X)))
   MARK(p(X)) -> P(mark(X))
   MARK(p(X)) -> MARK(X)
   F(mark(X)) -> F(X)
   F(active(X)) -> F(X)
   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)
   S(mark(X)) -> S(X)
   S(active(X)) -> S(X)
   P(mark(X)) -> P(X)
   P(active(X)) -> P(X)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(3) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 5 SCCs with 10 less nodes.
----------------------------------------

(4)
Complex Obligation (AND)

----------------------------------------

(5)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(active(X)) -> P(X)
   P(mark(X)) -> P(X)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(6) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(7)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(active(X)) -> P(X)
   P(mark(X)) -> P(X)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(8) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))


----------------------------------------

(9)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   P(active(X)) -> P(X)
   P(mark(X)) -> P(X)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))

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

(10) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*P(active(X)) -> P(X)
The graph contains the following edges 1 > 1


*P(mark(X)) -> P(X)
The graph contains the following edges 1 > 1


----------------------------------------

(11)
YES

----------------------------------------

(12)
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(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(13) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(14)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   S(active(X)) -> S(X)
   S(mark(X)) -> S(X)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(15) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))


----------------------------------------

(16)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   S(active(X)) -> S(X)
   S(mark(X)) -> S(X)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))

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

(17) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*S(active(X)) -> S(X)
The graph contains the following edges 1 > 1


*S(mark(X)) -> S(X)
The graph contains the following edges 1 > 1


----------------------------------------

(18)
YES

----------------------------------------

(19)
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(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(20) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

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

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(22) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))


----------------------------------------

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

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))

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

(24) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*CONS(X1, mark(X2)) -> CONS(X1, X2)
The graph contains the following edges 1 >= 1, 2 > 2


*CONS(mark(X1), X2) -> CONS(X1, X2)
The graph contains the following edges 1 > 1, 2 >= 2


*CONS(active(X1), X2) -> CONS(X1, X2)
The graph contains the following edges 1 > 1, 2 >= 2


*CONS(X1, active(X2)) -> CONS(X1, X2)
The graph contains the following edges 1 >= 1, 2 > 2


----------------------------------------

(25)
YES

----------------------------------------

(26)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(active(X)) -> F(X)
   F(mark(X)) -> F(X)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(27) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(28)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(active(X)) -> F(X)
   F(mark(X)) -> F(X)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(29) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))


----------------------------------------

(30)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   F(active(X)) -> F(X)
   F(mark(X)) -> F(X)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))

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

(31) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*F(active(X)) -> F(X)
The graph contains the following edges 1 > 1


*F(mark(X)) -> F(X)
The graph contains the following edges 1 > 1


----------------------------------------

(32)
YES

----------------------------------------

(33)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   ACTIVE(f(0)) -> MARK(cons(0, f(s(0))))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(f(X)) -> ACTIVE(f(mark(X)))
   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(X)) -> MARK(X)
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   ACTIVE(p(s(X))) -> MARK(X)
   MARK(s(X)) -> MARK(X)
   MARK(p(X)) -> ACTIVE(p(mark(X)))
   MARK(p(X)) -> MARK(X)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(34) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.

Strictly oriented dependency pairs:

   MARK(f(X)) -> MARK(X)


Used ordering: Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = 2*x_1
   POL(MARK(x_1)) = 2*x_1
   POL(active(x_1)) = x_1
   POL(cons(x_1, x_2)) = 2*x_1 + x_2
   POL(f(x_1)) = 1 + 2*x_1
   POL(mark(x_1)) = x_1
   POL(p(x_1)) = 2*x_1
   POL(s(x_1)) = 2*x_1


----------------------------------------

(35)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   ACTIVE(f(0)) -> MARK(cons(0, f(s(0))))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(f(X)) -> ACTIVE(f(mark(X)))
   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   ACTIVE(p(s(X))) -> MARK(X)
   MARK(s(X)) -> MARK(X)
   MARK(p(X)) -> ACTIVE(p(mark(X)))
   MARK(p(X)) -> MARK(X)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(36) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   ACTIVE(f(0)) -> MARK(cons(0, f(s(0))))
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
MARK(x1)  =  x1

cons(x1, x2)  =  x1

ACTIVE(x1)  =  x1

mark(x1)  =  x1

f(x1)  =  f

0  =  0

s(x1)  =  x1

p(x1)  =  x1

active(x1)  =  x1


Knuth-Bendix order [KBO] with precedence:f > 0

and weight map:

   0=1
   f=1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   mark(f(X)) -> active(f(mark(X)))
   active(p(s(X))) -> mark(X)
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   mark(0) -> active(0)
   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)
   f(active(X)) -> f(X)
   f(mark(X)) -> f(X)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   p(active(X)) -> p(X)
   p(mark(X)) -> p(X)


----------------------------------------

(37)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(f(X)) -> ACTIVE(f(mark(X)))
   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   ACTIVE(p(s(X))) -> MARK(X)
   MARK(s(X)) -> MARK(X)
   MARK(p(X)) -> ACTIVE(p(mark(X)))
   MARK(p(X)) -> MARK(X)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(38) QDPOrderProof (EQUIVALENT)
We use the reduction pair processor [LPAR04,JAR06].


The following pairs can be oriented strictly and are deleted.

   ACTIVE(p(s(X))) -> MARK(X)
   MARK(p(X)) -> MARK(X)
The remaining pairs can at least be oriented weakly.
Used ordering:  Combined order from the following AFS and order.
MARK(x1)  =  x1

cons(x1, x2)  =  x1

ACTIVE(x1)  =  x1

mark(x1)  =  x1

f(x1)  =  f

s(x1)  =  x1

p(x1)  =  p(x1)

active(x1)  =  x1

0  =  0


Knuth-Bendix order [KBO] with precedence:f > 0

and weight map:

   0=1
   p_1=1
   f=1

The following usable rules [FROCOS05] with respect to the argument filtering of the ordering [JAR06] were oriented:

   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   mark(f(X)) -> active(f(mark(X)))
   active(p(s(X))) -> mark(X)
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   mark(0) -> active(0)
   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)
   f(active(X)) -> f(X)
   f(mark(X)) -> f(X)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   p(active(X)) -> p(X)
   p(mark(X)) -> p(X)


----------------------------------------

(39)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(cons(X1, X2)) -> ACTIVE(cons(mark(X1), X2))
   MARK(cons(X1, X2)) -> MARK(X1)
   MARK(f(X)) -> ACTIVE(f(mark(X)))
   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(s(X)) -> ACTIVE(s(mark(X)))
   MARK(s(X)) -> MARK(X)
   MARK(p(X)) -> ACTIVE(p(mark(X)))

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(40) DependencyGraphProof (EQUIVALENT)
The approximation of the Dependency Graph [LPAR04,FROCOS05,EDGSTAR] contains 2 SCCs with 3 less nodes.
----------------------------------------

(41)
Complex Obligation (AND)

----------------------------------------

(42)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(X)) -> ACTIVE(f(mark(X)))

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(43) TransformationProof (EQUIVALENT)
By instantiating [LPAR04] the rule MARK(f(X)) -> ACTIVE(f(mark(X))) we obtained the following new rules [LPAR04]:

   (MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0))))),MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0))))))


----------------------------------------

(44)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(45) QDPQMonotonicMRRProof (EQUIVALENT)
By using the Q-monotonic rule removal processor with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented such that it always occurs at a strongly monotonic position in a (P,Q,R)-chain.


Strictly oriented rules of the TRS R:

   active(f(0)) -> mark(cons(0, f(s(0))))

Used ordering: Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = 2*x_1
   POL(MARK(x_1)) = 2
   POL(active(x_1)) = x_1
   POL(cons(x_1, x_2)) = x_1
   POL(f(x_1)) = 1 + x_1
   POL(mark(x_1)) = x_1
   POL(p(x_1)) = 2*x_1
   POL(s(x_1)) = 2*x_1


----------------------------------------

(46)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The TRS R consists of the following rules:

   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(47) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.


Strictly oriented rules of the TRS R:

   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))

Used ordering: Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = x_1
   POL(MARK(x_1)) = 2*x_1
   POL(active(x_1)) = x_1
   POL(cons(x_1, x_2)) = 1 + x_1 + 2*x_2
   POL(f(x_1)) = x_1
   POL(mark(x_1)) = 2*x_1
   POL(p(x_1)) = x_1
   POL(s(x_1)) = 2*x_1


----------------------------------------

(48)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The TRS R consists of the following rules:

   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(49) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(50)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The TRS R consists of the following rules:

   mark(f(X)) -> active(f(mark(X)))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(active(X)) -> f(X)
   f(mark(X)) -> f(X)
   mark(0) -> active(0)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   p(active(X)) -> p(X)
   p(mark(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(51) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))


----------------------------------------

(52)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The TRS R consists of the following rules:

   mark(f(X)) -> active(f(mark(X)))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(active(X)) -> f(X)
   f(mark(X)) -> f(X)
   mark(0) -> active(0)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   p(active(X)) -> p(X)
   p(mark(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(53) MRRProof (EQUIVALENT)
By using the rule removal processor [LPAR04] with the following ordering, at least one Dependency Pair or term rewrite system rule of this QDP problem can be strictly oriented.


Strictly oriented rules of the TRS R:

   active(p(s(X))) -> mark(X)

Used ordering: Polynomial interpretation [POLO]:

   POL(0) = 0
   POL(ACTIVE(x_1)) = 2 + 2*x_1
   POL(MARK(x_1)) = 2 + 2*x_1
   POL(active(x_1)) = x_1
   POL(f(x_1)) = 1 + x_1
   POL(mark(x_1)) = x_1
   POL(p(x_1)) = x_1
   POL(s(x_1)) = 2 + x_1


----------------------------------------

(54)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The TRS R consists of the following rules:

   mark(f(X)) -> active(f(mark(X)))
   active(f(s(0))) -> mark(f(p(s(0))))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(active(X)) -> f(X)
   f(mark(X)) -> f(X)
   mark(0) -> active(0)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   p(active(X)) -> p(X)
   p(mark(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(55) RFCMatchBoundsDPProof (EQUIVALENT)
Finiteness of the DP problem can be shown by a matchbound of 3. 
As the DP problem is minimal we only have to initialize the certificate graph by the rules of P:

   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

To find matches we regarded all rules of R and P:

   mark(f(X)) -> active(f(mark(X)))
   active(f(s(0))) -> mark(f(p(s(0))))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(active(X)) -> f(X)
   f(mark(X)) -> f(X)
   mark(0) -> active(0)
   s(active(X)) -> s(X)
   s(mark(X)) -> s(X)
   p(active(X)) -> p(X)
   p(mark(X)) -> p(X)
   ACTIVE(f(s(0))) -> MARK(f(p(s(0))))
   MARK(f(p(s(0)))) -> ACTIVE(f(mark(p(s(0)))))

The certificate found is represented by the following graph.
The certificate consists of the following enumerated nodes:
359, 360, 361, 362, 363, 364, 365, 366, 367, 368, 369, 370, 371, 372, 373, 374, 375, 376, 377, 378, 379, 380, 381, 382, 383

Node 359 is start node and node 360 is final node.

Those nodes are connected through the following edges:

* 359 to 361 labelled MARK_1(0)* 359 to 365 labelled ACTIVE_1(0)* 359 to 372 labelled ACTIVE_1(1)* 360 to 360 labelled #_1(0)* 361 to 362 labelled f_1(0)* 362 to 363 labelled p_1(0)* 363 to 364 labelled s_1(0)* 364 to 360 labelled 0(0)* 365 to 366 labelled f_1(0)* 365 to 367 labelled f_1(1)* 365 to 370 labelled f_1(1)* 366 to 367 labelled mark_1(0)* 366 to 370 labelled active_1(1)* 367 to 368 labelled p_1(0)* 368 to 369 labelled s_1(0)* 369 to 360 labelled 0(0)* 370 to 371 labelled p_1(1)* 370 to 368 labelled p_1(2)* 370 to 377 labelled p_1(2)* 371 to 368 labelled mark_1(1)* 371 to 377 labelled active_1(1)* 372 to 373 labelled f_1(1)* 372 to 374 labelled f_1(2)* 372 to 379 labelled f_1(2)* 373 to 374 labelled mark_1(1)* 373 to 379 labelled active_1(2)* 374 to 375 labelled p_1(1)* 375 to 376 labelled s_1(1)* 376 to 360 labelled 0(1)* 377 to 378 labelled s_1(1)* 377 to 369 labelled s_1(2)* 377 to 376 labelled s_1(2)* 378 to 369 labelled mark_1(1)* 378 to 376 labelled active_1(1)* 379 to 380 labelled p_1(2)* 379 to 375 labelled p_1(3)* 379 to 381 labelled p_1(3)* 380 to 375 labelled mark_1(2)* 380 to 381 labelled active_1(2)* 381 to 382 labelled s_1(2)* 381 to 376 labelled s_1(3)* 381 to 383 labelled s_1(3)* 382 to 376 labelled mark_1(2)* 382 to 383 labelled active_1(2)* 383 to 360 labelled 0(2)


----------------------------------------

(56)
YES

----------------------------------------

(57)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(s(X)) -> MARK(X)
   MARK(cons(X1, X2)) -> MARK(X1)

The TRS R consists of the following rules:

   active(f(0)) -> mark(cons(0, f(s(0))))
   active(f(s(0))) -> mark(f(p(s(0))))
   active(p(s(X))) -> mark(X)
   mark(f(X)) -> active(f(mark(X)))
   mark(0) -> active(0)
   mark(cons(X1, X2)) -> active(cons(mark(X1), X2))
   mark(s(X)) -> active(s(mark(X)))
   mark(p(X)) -> active(p(mark(X)))
   f(mark(X)) -> f(X)
   f(active(X)) -> f(X)
   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)
   s(mark(X)) -> s(X)
   s(active(X)) -> s(X)
   p(mark(X)) -> p(X)
   p(active(X)) -> p(X)

The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(58) UsableRulesProof (EQUIVALENT)
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [LPAR04] we can delete all non-usable rules [FROCOS05] from R.
----------------------------------------

(59)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(s(X)) -> MARK(X)
   MARK(cons(X1, X2)) -> MARK(X1)

R is empty.
The set Q consists of the following terms:

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))
   p(mark(x0))
   p(active(x0))

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

(60) QReductionProof (EQUIVALENT)
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.[THIEMANN].

   active(f(0))
   active(f(s(0)))
   active(p(s(x0)))
   mark(f(x0))
   mark(0)
   mark(cons(x0, x1))
   mark(s(x0))
   mark(p(x0))
   f(mark(x0))
   f(active(x0))
   p(mark(x0))
   p(active(x0))


----------------------------------------

(61)
Obligation:
Q DP problem:
The TRS P consists of the following rules:

   MARK(s(X)) -> MARK(X)
   MARK(cons(X1, X2)) -> MARK(X1)

R is empty.
The set Q consists of the following terms:

   cons(mark(x0), x1)
   cons(x0, mark(x1))
   cons(active(x0), x1)
   cons(x0, active(x1))
   s(mark(x0))
   s(active(x0))

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

(62) QDPSizeChangeProof (EQUIVALENT)
By using the subterm criterion [SUBTERM_CRITERION] together with the size-change analysis [AAECC05] we have proven that there are no infinite chains for this DP problem. 

From the DPs we obtained the following set of size-change graphs:
*MARK(s(X)) -> MARK(X)
The graph contains the following edges 1 > 1


*MARK(cons(X1, X2)) -> MARK(X1)
The graph contains the following edges 1 > 1


----------------------------------------

(63)
YES