Tool CaT
stdout:
MAYBE
Problem:
g(x,0()) -> 0()
g(d(),s(x)) -> s(s(g(d(),x)))
g(h(),s(0())) -> 0()
g(h(),s(s(x))) -> s(g(h(),x))
double(x) -> g(d(),x)
half(x) -> g(h(),x)
f(s(x),y) -> f(half(s(x)),double(y))
f(s(0()),y) -> y
id(x) -> f(x,s(0()))
Proof:
Complexity Transformation Processor:
strict:
g(x,0()) -> 0()
g(d(),s(x)) -> s(s(g(d(),x)))
g(h(),s(0())) -> 0()
g(h(),s(s(x))) -> s(g(h(),x))
double(x) -> g(d(),x)
half(x) -> g(h(),x)
f(s(x),y) -> f(half(s(x)),double(y))
f(s(0()),y) -> y
id(x) -> f(x,s(0()))
weak:
Matrix Interpretation Processor:
dimension: 1
max_matrix:
1
interpretation:
[id](x0) = x0 + 55,
[f](x0, x1) = x0 + x1 + 14,
[half](x0) = x0 + 62,
[double](x0) = x0 + 32,
[h] = 35,
[s](x0) = x0 + 4,
[d] = 44,
[g](x0, x1) = x0 + x1 + 29,
[0] = 36
orientation:
g(x,0()) = x + 65 >= 36 = 0()
g(d(),s(x)) = x + 77 >= x + 81 = s(s(g(d(),x)))
g(h(),s(0())) = 104 >= 36 = 0()
g(h(),s(s(x))) = x + 72 >= x + 68 = s(g(h(),x))
double(x) = x + 32 >= x + 73 = g(d(),x)
half(x) = x + 62 >= x + 64 = g(h(),x)
f(s(x),y) = x + y + 18 >= x + y + 112 = f(half(s(x)),double(y))
f(s(0()),y) = y + 54 >= y = y
id(x) = x + 55 >= x + 54 = f(x,s(0()))
problem:
strict:
g(d(),s(x)) -> s(s(g(d(),x)))
double(x) -> g(d(),x)
half(x) -> g(h(),x)
f(s(x),y) -> f(half(s(x)),double(y))
weak:
g(x,0()) -> 0()
g(h(),s(0())) -> 0()
g(h(),s(s(x))) -> s(g(h(),x))
f(s(0()),y) -> y
id(x) -> f(x,s(0()))
Matrix Interpretation Processor:
dimension: 1
max_matrix:
1
interpretation:
[id](x0) = x0 + 26,
[f](x0, x1) = x0 + x1 + 17,
[half](x0) = x0 + 50,
[double](x0) = x0 + 16,
[h] = 0,
[s](x0) = x0,
[d] = 4,
[g](x0, x1) = x0 + x1,
[0] = 8
orientation:
g(d(),s(x)) = x + 4 >= x + 4 = s(s(g(d(),x)))
double(x) = x + 16 >= x + 4 = g(d(),x)
half(x) = x + 50 >= x = g(h(),x)
f(s(x),y) = x + y + 17 >= x + y + 83 = f(half(s(x)),double(y))
g(x,0()) = x + 8 >= 8 = 0()
g(h(),s(0())) = 8 >= 8 = 0()
g(h(),s(s(x))) = x >= x = s(g(h(),x))
f(s(0()),y) = y + 25 >= y = y
id(x) = x + 26 >= x + 25 = f(x,s(0()))
problem:
strict:
g(d(),s(x)) -> s(s(g(d(),x)))
f(s(x),y) -> f(half(s(x)),double(y))
weak:
double(x) -> g(d(),x)
half(x) -> g(h(),x)
g(x,0()) -> 0()
g(h(),s(0())) -> 0()
g(h(),s(s(x))) -> s(g(h(),x))
f(s(0()),y) -> y
id(x) -> f(x,s(0()))
Open
Tool IRC1
stdout:
MAYBE
Tool IRC2
stdout:
TIMEOUT
'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer: TIMEOUT
Input Problem: innermost runtime-complexity with respect to
Rules:
{ g(x, 0()) -> 0()
, g(d(), s(x)) -> s(s(g(d(), x)))
, g(h(), s(0())) -> 0()
, g(h(), s(s(x))) -> s(g(h(), x))
, double(x) -> g(d(), x)
, half(x) -> g(h(), x)
, f(s(x), y) -> f(half(s(x)), double(y))
, f(s(0()), y) -> y
, id(x) -> f(x, s(0()))}
Proof Output:
Computation stopped due to timeout after 60.0 secondsTool RC1
stdout:
MAYBE
Tool RC2
stdout:
TIMEOUT
'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer: TIMEOUT
Input Problem: runtime-complexity with respect to
Rules:
{ g(x, 0()) -> 0()
, g(d(), s(x)) -> s(s(g(d(), x)))
, g(h(), s(0())) -> 0()
, g(h(), s(s(x))) -> s(g(h(), x))
, double(x) -> g(d(), x)
, half(x) -> g(h(), x)
, f(s(x), y) -> f(half(s(x)), double(y))
, f(s(0()), y) -> y
, id(x) -> f(x, s(0()))}
Proof Output:
Computation stopped due to timeout after 60.0 seconds