(0) Obligation:
Q restricted rewrite system:
The TRS R consists of the following rules:
f(j(x, y), y) → g(f(x, k(y)))
f(x, h1(y, z)) → h2(0, x, h1(y, z))
g(h2(x, y, h1(z, u))) → h2(s(x), y, h1(z, u))
h2(x, j(y, h1(z, u)), h1(z, u)) → h2(s(x), y, h1(s(z), u))
i(f(x, h(y))) → y
i(h2(s(x), y, h1(x, z))) → z
k(h(x)) → h1(0, x)
k(h1(x, y)) → h1(s(x), y)
Q is empty.
(1) QTRSRRRProof (EQUIVALENT transformation)
Used ordering:
Knuth-Bendix order [KBO] with precedence:
h1 > i1 > s1 > 0 > f2 > g1 > j2 > h23 > k1 > h12
and weight map:
0=5
g_1=4
k_1=4
s_1=4
i_1=1
h_1=1
j_2=7
f_2=5
h2_3=0
h1_2=0
The variable weight is 1With this ordering the following rules can be removed by the rule removal processor [LPAR04] because they are oriented strictly:
f(j(x, y), y) → g(f(x, k(y)))
f(x, h1(y, z)) → h2(0, x, h1(y, z))
g(h2(x, y, h1(z, u))) → h2(s(x), y, h1(z, u))
h2(x, j(y, h1(z, u)), h1(z, u)) → h2(s(x), y, h1(s(z), u))
i(f(x, h(y))) → y
i(h2(s(x), y, h1(x, z))) → z
k(h(x)) → h1(0, x)
k(h1(x, y)) → h1(s(x), y)
(2) Obligation:
Q restricted rewrite system:
R is empty.
Q is empty.
(3) RisEmptyProof (EQUIVALENT transformation)
The TRS R is empty. Hence, termination is trivially proven.
(4) YES