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

(0) Obligation:

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

intlist(nil) → nil
int(s(x), 0) → nil
int(x, x) → cons(x, nil)
intlist(cons(x, y)) → cons(s(x), intlist(y))
int(s(x), s(y)) → intlist(int(x, y))
int(0, s(y)) → cons(0, int(s(0), s(y)))
intlist(cons(x, nil)) → cons(s(x), nil)

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:

INTLIST(cons(x, y)) → INTLIST(y)
INT(s(x), s(y)) → INTLIST(int(x, y))
INT(s(x), s(y)) → INT(x, y)
INT(0, s(y)) → INT(s(0), s(y))

The TRS R consists of the following rules:

intlist(nil) → nil
int(s(x), 0) → nil
int(x, x) → cons(x, nil)
intlist(cons(x, y)) → cons(s(x), intlist(y))
int(s(x), s(y)) → intlist(int(x, y))
int(0, s(y)) → cons(0, int(s(0), s(y)))
intlist(cons(x, nil)) → cons(s(x), nil)

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 1 less node.

(4) Complex Obligation (AND)

(5) Obligation:

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

INTLIST(cons(x, y)) → INTLIST(y)

The TRS R consists of the following rules:

intlist(nil) → nil
int(s(x), 0) → nil
int(x, x) → cons(x, nil)
intlist(cons(x, y)) → cons(s(x), intlist(y))
int(s(x), s(y)) → intlist(int(x, y))
int(0, s(y)) → cons(0, int(s(0), s(y)))
intlist(cons(x, nil)) → cons(s(x), nil)

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

(6) Obligation:

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

INT(0, s(y)) → INT(s(0), s(y))
INT(s(x), s(y)) → INT(x, y)

The TRS R consists of the following rules:

intlist(nil) → nil
int(s(x), 0) → nil
int(x, x) → cons(x, nil)
intlist(cons(x, y)) → cons(s(x), intlist(y))
int(s(x), s(y)) → intlist(int(x, y))
int(0, s(y)) → cons(0, int(s(0), s(y)))
intlist(cons(x, nil)) → cons(s(x), nil)

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

(7) QDPOrderProof (EQUIVALENT transformation)

We use the reduction pair processor [LPAR04].

The following pairs can be oriented strictly and are deleted.

INT(s(x), s(y)) → INT(x, y)

The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
INT(x1, x2)  =  x2
0  =  0
s(x1)  =  s(x1)
intlist(x1)  =  intlist(x1)
nil  =  nil
int(x1, x2)  =  int(x2)
cons(x1, x2)  =  x2

Lexicographic path order with status [LPO].
Precedence:

int₁ > 0
int₁ > intlist₁ > s₁
int₁ > intlist₁ > nil

Status:

intlist₁: [1]
int₁: [1]
s₁: [1]
0: []
nil: []

The following usable rules [FROCOS05] were oriented:

intlist(nil) → nil
int(s(x), 0) → nil
int(x, x) → cons(x, nil)
intlist(cons(x, y)) → cons(s(x), intlist(y))
int(s(x), s(y)) → intlist(int(x, y))
int(0, s(y)) → cons(0, int(s(0), s(y)))
intlist(cons(x, nil)) → cons(s(x), nil)

(8) Obligation:

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

INT(0, s(y)) → INT(s(0), s(y))

The TRS R consists of the following rules:

intlist(nil) → nil
int(s(x), 0) → nil
int(x, x) → cons(x, nil)
intlist(cons(x, y)) → cons(s(x), intlist(y))
int(s(x), s(y)) → intlist(int(x, y))
int(0, s(y)) → cons(0, int(s(0), s(y)))
intlist(cons(x, nil)) → cons(s(x), nil)

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

(9) DependencyGraphProof (EQUIVALENT transformation)

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

(10) TRUE