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

0 QTRS
↳1 DependencyPairsProof (⇔)
↳2 QDP
↳3 DependencyGraphProof (⇔)
↳4 AND
  ↳5 QDP
    ↳6 QDPOrderProof (⇔)
    ↳7 QDP
    ↳8 PisEmptyProof (⇔)
    ↳9 TRUE
  ↳10 QDP
    ↳11 QDPOrderProof (⇔)
    ↳12 QDP
    ↳13 PisEmptyProof (⇔)
    ↳14 TRUE
  ↳15 QDP
    ↳16 QDPOrderProof (⇔)
    ↳17 QDP
    ↳18 PisEmptyProof (⇔)
    ↳19 TRUE
  ↳20 QDP

(0) Obligation:

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

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(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(free(x)) → TOP(check(new(x)))
TOP(free(x)) → CHECK(new(x))
TOP(free(x)) → NEW(x)
NEW(free(x)) → NEW(x)
OLD(free(x)) → OLD(x)
CHECK(free(x)) → CHECK(x)
CHECK(new(x)) → NEW(check(x))
CHECK(new(x)) → CHECK(x)
CHECK(old(x)) → OLD(check(x))
CHECK(old(x)) → CHECK(x)

The TRS R consists of the following rules:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(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 4 SCCs with 4 less nodes.

(4) Complex Obligation (AND)

(5) Obligation:

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

OLD(free(x)) → OLD(x)

The TRS R consists of the following rules:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(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.


OLD(free(x)) → OLD(x)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
OLD(x1)  =  x1
free(x1)  =  free(x1)
top(x1)  =  x1
check(x1)  =  x1
new(x1)  =  new(x1)
old(x1)  =  old(x1)
serve  =  serve

Lexicographic Path Order [LPO].
Precedence:
[old1, serve] > [free1, new1]


The following usable rules [FROCOS05] were oriented:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

(7) Obligation:

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

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

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

(8) PisEmptyProof (EQUIVALENT transformation)

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

(9) TRUE

(10) Obligation:

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

NEW(free(x)) → NEW(x)

The TRS R consists of the following rules:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

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

(11) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


NEW(free(x)) → NEW(x)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
NEW(x1)  =  x1
free(x1)  =  free(x1)
top(x1)  =  x1
check(x1)  =  x1
new(x1)  =  new(x1)
old(x1)  =  old(x1)
serve  =  serve

Lexicographic Path Order [LPO].
Precedence:
[old1, serve] > [free1, new1]


The following usable rules [FROCOS05] were oriented:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

(12) Obligation:

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

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

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

(13) PisEmptyProof (EQUIVALENT transformation)

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

(14) TRUE

(15) Obligation:

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

CHECK(new(x)) → CHECK(x)
CHECK(free(x)) → CHECK(x)
CHECK(old(x)) → CHECK(x)

The TRS R consists of the following rules:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

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

(16) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].


The following pairs can be oriented strictly and are deleted.


CHECK(new(x)) → CHECK(x)
CHECK(free(x)) → CHECK(x)
CHECK(old(x)) → CHECK(x)
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
CHECK(x1)  =  CHECK(x1)
new(x1)  =  new(x1)
free(x1)  =  free(x1)
old(x1)  =  old(x1)
top(x1)  =  top
check(x1)  =  check(x1)
serve  =  serve

Lexicographic Path Order [LPO].
Precedence:
[new1, old1, top, check1] > free1 > CHECK1
[new1, old1, top, check1] > serve


The following usable rules [FROCOS05] were oriented:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

(17) Obligation:

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

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

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

(18) PisEmptyProof (EQUIVALENT transformation)

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

(19) TRUE

(20) Obligation:

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

TOP(free(x)) → TOP(check(new(x)))

The TRS R consists of the following rules:

top(free(x)) → top(check(new(x)))
new(free(x)) → free(new(x))
old(free(x)) → free(old(x))
new(serve) → free(serve)
old(serve) → free(serve)
check(free(x)) → free(check(x))
check(new(x)) → new(check(x))
check(old(x)) → old(check(x))
check(old(x)) → old(x)

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