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

(0) Obligation:

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

active(f(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
mark(f(X1, X2, X3)) → active(f(X1, X2, mark(X3)))
mark(a) → active(a)
mark(b) → active(b)
mark(c) → active(c)
f(mark(X1), X2, X3) → f(X1, X2, X3)
f(X1, mark(X2), X3) → f(X1, X2, X3)
f(X1, X2, mark(X3)) → f(X1, X2, X3)
f(active(X1), X2, X3) → f(X1, X2, X3)
f(X1, active(X2), X3) → f(X1, X2, X3)
f(X1, X2, active(X3)) → f(X1, X2, X3)

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(f(a, b, X)) → MARK(f(X, X, X))
ACTIVE(f(a, b, X)) → F(X, X, X)
ACTIVE(c) → MARK(a)
ACTIVE(c) → MARK(b)
MARK(f(X1, X2, X3)) → ACTIVE(f(X1, X2, mark(X3)))
MARK(f(X1, X2, X3)) → F(X1, X2, mark(X3))
MARK(f(X1, X2, X3)) → MARK(X3)
MARK(a) → ACTIVE(a)
MARK(b) → ACTIVE(b)
MARK(c) → ACTIVE(c)
F(mark(X1), X2, X3) → F(X1, X2, X3)
F(X1, mark(X2), X3) → F(X1, X2, X3)
F(X1, X2, mark(X3)) → F(X1, X2, X3)
F(active(X1), X2, X3) → F(X1, X2, X3)
F(X1, active(X2), X3) → F(X1, X2, X3)
F(X1, X2, active(X3)) → F(X1, X2, X3)

The TRS R consists of the following rules:

active(f(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
mark(f(X1, X2, X3)) → active(f(X1, X2, mark(X3)))
mark(a) → active(a)
mark(b) → active(b)
mark(c) → active(c)
f(mark(X1), X2, X3) → f(X1, X2, X3)
f(X1, mark(X2), X3) → f(X1, X2, X3)
f(X1, X2, mark(X3)) → f(X1, X2, X3)
f(active(X1), X2, X3) → f(X1, X2, X3)
f(X1, active(X2), X3) → f(X1, X2, X3)
f(X1, X2, active(X3)) → f(X1, X2, X3)

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

(3) DependencyGraphProof (EQUIVALENT transformation)

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

(4) Complex Obligation (AND)

(5) Obligation:

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

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

The TRS R consists of the following rules:

active(f(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
mark(f(X1, X2, X3)) → active(f(X1, X2, mark(X3)))
mark(a) → active(a)
mark(b) → active(b)
mark(c) → active(c)
f(mark(X1), X2, X3) → f(X1, X2, X3)
f(X1, mark(X2), X3) → f(X1, X2, X3)
f(X1, X2, mark(X3)) → f(X1, X2, X3)
f(active(X1), X2, X3) → f(X1, X2, X3)
f(X1, active(X2), X3) → f(X1, X2, X3)
f(X1, X2, active(X3)) → f(X1, X2, X3)

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

(6) QDPSizeChangeProof (EQUIVALENT transformation)

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(X1, mark(X2), X3) → F(X1, X2, X3)
  The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3

• F(mark(X1), X2, X3) → F(X1, X2, X3)
  The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3

• F(X1, X2, mark(X3)) → F(X1, X2, X3)
  The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3

• F(active(X1), X2, X3) → F(X1, X2, X3)
  The graph contains the following edges 1 > 1, 2 >= 2, 3 >= 3

• F(X1, active(X2), X3) → F(X1, X2, X3)
  The graph contains the following edges 1 >= 1, 2 > 2, 3 >= 3

• F(X1, X2, active(X3)) → F(X1, X2, X3)
  The graph contains the following edges 1 >= 1, 2 >= 2, 3 > 3

(7) YES

(8) Obligation:

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

MARK(f(X1, X2, X3)) → ACTIVE(f(X1, X2, mark(X3)))
ACTIVE(f(a, b, X)) → MARK(f(X, X, X))
MARK(f(X1, X2, X3)) → MARK(X3)

The TRS R consists of the following rules:

active(f(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
mark(f(X1, X2, X3)) → active(f(X1, X2, mark(X3)))
mark(a) → active(a)
mark(b) → active(b)
mark(c) → active(c)
f(mark(X1), X2, X3) → f(X1, X2, X3)
f(X1, mark(X2), X3) → f(X1, X2, X3)
f(X1, X2, mark(X3)) → f(X1, X2, X3)
f(active(X1), X2, X3) → f(X1, X2, X3)
f(X1, active(X2), X3) → f(X1, X2, X3)
f(X1, X2, active(X3)) → f(X1, X2, X3)

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

(9) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04,JAR06].

The following pairs can be oriented strictly and are deleted.

MARK(f(X1, X2, X3)) → MARK(X3)

The remaining pairs can at least be oriented weakly.
Used ordering: Polynomial Order [NEGPOLO,POLO] with Interpretation:

POL( ACTIVE(x₁) ) = 2x₁ + 2

POL( f(x₁, ..., x₃) ) = x₃ + 2

POL( mark(x₁) ) = x₁

POL( active(x₁) ) = x₁

POL( a ) = 0

POL( b ) = 0

POL( c ) = 1

POL( MARK(x₁) ) = 2x₁ + 2

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

mark(f(X1, X2, X3)) → active(f(X1, X2, mark(X3)))
active(f(a, b, X)) → mark(f(X, X, X))
mark(a) → active(a)
mark(b) → active(b)
mark(c) → active(c)
f(X1, mark(X2), X3) → f(X1, X2, X3)
f(mark(X1), X2, X3) → f(X1, X2, X3)
f(X1, X2, mark(X3)) → f(X1, X2, X3)
f(active(X1), X2, X3) → f(X1, X2, X3)
f(X1, active(X2), X3) → f(X1, X2, X3)
f(X1, X2, active(X3)) → f(X1, X2, X3)
active(c) → mark(a)
active(c) → mark(b)

(10) Obligation:

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

MARK(f(X1, X2, X3)) → ACTIVE(f(X1, X2, mark(X3)))
ACTIVE(f(a, b, X)) → MARK(f(X, X, X))

The TRS R consists of the following rules:

active(f(a, b, X)) → mark(f(X, X, X))
active(c) → mark(a)
active(c) → mark(b)
mark(f(X1, X2, X3)) → active(f(X1, X2, mark(X3)))
mark(a) → active(a)
mark(b) → active(b)
mark(c) → active(c)
f(mark(X1), X2, X3) → f(X1, X2, X3)
f(X1, mark(X2), X3) → f(X1, X2, X3)
f(X1, X2, mark(X3)) → f(X1, X2, X3)
f(active(X1), X2, X3) → f(X1, X2, X3)
f(X1, active(X2), X3) → f(X1, X2, X3)
f(X1, X2, active(X3)) → f(X1, X2, X3)

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

(11) NonTerminationLoopProof (EQUIVALENT transformation)

We used the non-termination processor [FROCOS05] to show that the DP problem is infinite.
Found a loop by narrowing to the left:

s = ACTIVE(f(active(c), active(c), mark(X3))) evaluates to t =ACTIVE(f(X3, X3, mark(X3)))

Thus s starts an infinite chain as s semiunifies with t with the following substitutions:

• Matcher: [ ]
• Semiunifier: [X3 / active(c)]

---

Rewriting sequence

ACTIVE(f(active(c), active(c), mark(active(c)))) → ACTIVE(f(active(c), mark(b), mark(active(c))))
with rule active(c) → mark(b) at position [0,1] and matcher [ ]

ACTIVE(f(active(c), mark(b), mark(active(c)))) → ACTIVE(f(mark(a), mark(b), mark(active(c))))
with rule active(c) → mark(a) at position [0,0] and matcher [ ]

ACTIVE(f(mark(a), mark(b), mark(active(c)))) → ACTIVE(f(mark(a), mark(b), active(c)))
with rule f(X1, X2, mark(X3)) → f(X1, X2, X3) at position [0] and matcher [X1 / mark(a), X2 / mark(b), X3 / active(c)]

ACTIVE(f(mark(a), mark(b), active(c))) → ACTIVE(f(mark(a), b, active(c)))
with rule f(X1, mark(X2), X3') → f(X1, X2, X3') at position [0] and matcher [X1 / mark(a), X2 / b, X3' / active(c)]

ACTIVE(f(mark(a), b, active(c))) → ACTIVE(f(a, b, active(c)))
with rule f(mark(X1), X2, X3) → f(X1, X2, X3) at position [0] and matcher [X1 / a, X2 / b, X3 / active(c)]

ACTIVE(f(a, b, active(c))) → MARK(f(active(c), active(c), active(c)))
with rule ACTIVE(f(a, b, X)) → MARK(f(X, X, X)) at position [] and matcher [X / active(c)]

MARK(f(active(c), active(c), active(c))) → ACTIVE(f(active(c), active(c), mark(active(c))))
with rule MARK(f(X1, X2, X3)) → ACTIVE(f(X1, X2, mark(X3)))

Now applying the matcher to the start term leads to a term which is equal to the last term in the rewriting sequence


All these steps are and every following step will be a correct step w.r.t to Q.

(12) NO