(0) Obligation:
The Runtime Complexity (innermost) of the given
CpxTRS could be proven to be
BOUNDS(1, 1).
The TRS R consists of the following rules:
g(X) → u(h(X), h(X), X)
u(d, c(Y), X) → k(Y)
h(d) → c(a)
h(d) → c(b)
f(k(a), k(b), X) → f(X, X, X)
Rewrite Strategy: INNERMOST
(1) CpxTrsToCdtProof (BOTH BOUNDS(ID, ID) transformation)
Converted Cpx (relative) TRS to CDT
(2) Obligation:
Complexity Dependency Tuples Problem
Rules:
g(z0) → u(h(z0), h(z0), z0)
u(d, c(z0), z1) → k(z0)
h(d) → c(a)
h(d) → c(b)
f(k(a), k(b), z0) → f(z0, z0, z0)
Tuples:
G(z0) → c1(U(h(z0), h(z0), z0), H(z0), H(z0))
U(d, c(z0), z1) → c2
H(d) → c3
H(d) → c4
F(k(a), k(b), z0) → c5(F(z0, z0, z0))
S tuples:
G(z0) → c1(U(h(z0), h(z0), z0), H(z0), H(z0))
U(d, c(z0), z1) → c2
H(d) → c3
H(d) → c4
F(k(a), k(b), z0) → c5(F(z0, z0, z0))
K tuples:none
Defined Rule Symbols:
g, u, h, f
Defined Pair Symbols:
G, U, H, F
Compound Symbols:
c1, c2, c3, c4, c5
(3) CdtLeafRemovalProof (BOTH BOUNDS(ID, ID) transformation)
Removed 5 trailing nodes:
G(z0) → c1(U(h(z0), h(z0), z0), H(z0), H(z0))
U(d, c(z0), z1) → c2
H(d) → c3
F(k(a), k(b), z0) → c5(F(z0, z0, z0))
H(d) → c4
(4) Obligation:
Complexity Dependency Tuples Problem
Rules:
g(z0) → u(h(z0), h(z0), z0)
u(d, c(z0), z1) → k(z0)
h(d) → c(a)
h(d) → c(b)
f(k(a), k(b), z0) → f(z0, z0, z0)
Tuples:none
S tuples:none
K tuples:none
Defined Rule Symbols:
g, u, h, f
Defined Pair Symbols:none
Compound Symbols:none
(5) SIsEmptyProof (BOTH BOUNDS(ID, ID) transformation)
The set S is empty
(6) BOUNDS(1, 1)