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 QDP
  ↳7 QDP
    ↳8 QDPOrderProof (⇔)
    ↳9 QDP
    ↳10 QDPOrderProof (⇔)
    ↳11 QDP
    ↳12 PisEmptyProof (⇔)
    ↳13 TRUE

(0) Obligation:

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

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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:

I(x, x) → I(a, b)
G(x, x) → G(a, b)
H(s(f(x))) → H(f(x))
F(s(x)) → F(h(s(x)))
F(s(x)) → H(s(x))
F(g(s(x), y)) → F(g(x, s(y)))
F(g(s(x), y)) → G(x, s(y))
H(g(x, s(y))) → H(g(s(x), y))
H(g(x, s(y))) → G(s(x), y)
H(i(x, y)) → I(i(c, h(h(y))), x)
H(i(x, y)) → I(c, h(h(y)))
H(i(x, y)) → H(h(y))
H(i(x, y)) → H(y)
G(a, g(x, g(b, g(a, g(x, y))))) → G(a, g(a, g(a, g(x, g(b, g(b, y))))))
G(a, g(x, g(b, g(a, g(x, y))))) → G(a, g(a, g(x, g(b, g(b, y)))))
G(a, g(x, g(b, g(a, g(x, y))))) → G(a, g(x, g(b, g(b, y))))
G(a, g(x, g(b, g(a, g(x, y))))) → G(x, g(b, g(b, y)))
G(a, g(x, g(b, g(a, g(x, y))))) → G(b, g(b, y))
G(a, g(x, g(b, g(a, g(x, y))))) → G(b, y)

The TRS R consists of the following rules:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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 3 SCCs with 10 less nodes.

(4) Complex Obligation (AND)

(5) Obligation:

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

G(a, g(x, g(b, g(a, g(x, y))))) → G(a, g(x, g(b, g(b, y))))
G(a, g(x, g(b, g(a, g(x, y))))) → G(a, g(a, g(x, g(b, g(b, y)))))
G(a, g(x, g(b, g(a, g(x, y))))) → G(x, g(b, g(b, y)))

The TRS R consists of the following rules:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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:

H(g(x, s(y))) → H(g(s(x), y))
H(s(f(x))) → H(f(x))
H(i(x, y)) → H(h(y))
H(i(x, y)) → H(y)

The TRS R consists of the following rules:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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

(7) Obligation:

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

F(g(s(x), y)) → F(g(x, s(y)))
F(s(x)) → F(h(s(x)))

The TRS R consists of the following rules:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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(s(x)) → F(h(s(x)))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
F(x1)  =  F(x1)
g(x1, x2)  =  g
s(x1)  =  s(x1)
h(x1)  =  h
i(x1, x2)  =  i
a  =  a
b  =  b
f(x1)  =  f(x1)
c  =  c

Lexicographic path order with status [LPO].
Precedence:
a > i
b > i
f1 > g > F1 > i
f1 > g > h > i
f1 > s1 > F1 > i
f1 > s1 > h > i
c > i

Status:
i: []
c: []
a: []
f1: [1]
g: []
s1: [1]
b: []
h: []
F1: [1]

The following usable rules [FROCOS05] were oriented:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

(9) Obligation:

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

F(g(s(x), y)) → F(g(x, s(y)))

The TRS R consists of the following rules:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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(g(s(x), y)) → F(g(x, s(y)))
The remaining pairs can at least be oriented weakly.
Used ordering: Combined order from the following AFS and order.
F(x1)  =  F(x1)
g(x1, x2)  =  x1
s(x1)  =  s(x1)
i(x1, x2)  =  i
a  =  a
b  =  b
h(x1)  =  h
f(x1)  =  f(x1)
c  =  c

Lexicographic path order with status [LPO].
Precedence:
b > a
f1 > s1 > F1 > a
f1 > s1 > h > i > a
f1 > s1 > h > c > a

Status:
i: []
c: []
f1: [1]
a: []
b: []
s1: [1]
h: []
F1: [1]

The following usable rules [FROCOS05] were oriented:

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

(11) Obligation:

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

i(x, x) → i(a, b)
g(x, x) → g(a, b)
h(s(f(x))) → h(f(x))
f(s(x)) → s(s(f(h(s(x)))))
f(g(s(x), y)) → f(g(x, s(y)))
h(g(x, s(y))) → h(g(s(x), y))
h(i(x, y)) → i(i(c, h(h(y))), x)
g(a, g(x, g(b, g(a, g(x, y))))) → g(a, g(a, g(a, g(x, g(b, g(b, y))))))

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