Tool CaT
stdout:
MAYBE
Problem:
f(g(a())) -> f(s(g(b())))
f(f(x)) -> b()
g(x) -> f(g(x))
Proof:
Complexity Transformation Processor:
strict:
f(g(a())) -> f(s(g(b())))
f(f(x)) -> b()
g(x) -> f(g(x))
weak:
Bounds Processor:
bound: 1
enrichment: match
automaton:
final states: {5,4}
transitions:
f1(55) -> 56*
f1(18) -> 19*
g1(42) -> 43*
g1(44) -> 45*
g1(31) -> 32*
g1(16) -> 17*
b1() -> 16*
s1(17) -> 18*
f0(2) -> 4*
f0(6) -> 7*
f0(1) -> 4*
f0(3) -> 4*
g0(2) -> 5*
g0(1) -> 5*
g0(3) -> 5*
a0() -> 1*
s0(2) -> 2*
s0(1) -> 2*
s0(3) -> 2*
b0() -> 3*
1 -> 42*
2 -> 44*
3 -> 31,7
5 -> 6*
7 -> 5*
16 -> 19,56,7
17 -> 55*
19 -> 43,32,45,7
32 -> 18*
43 -> 18*
45 -> 18*
56 -> 17*
problem:
strict:
f(f(x)) -> b()
g(x) -> f(g(x))
weak:
f(g(a())) -> f(s(g(b())))
Matrix Interpretation Processor:
dimension: 1
max_matrix:
1
interpretation:
[s](x0) = x0 + 39,
[b] = 165,
[f](x0) = x0 + 128,
[g](x0) = x0 + 4,
[a] = 244
orientation:
f(f(x)) = x + 256 >= 165 = b()
g(x) = x + 4 >= x + 132 = f(g(x))
f(g(a())) = 376 >= 336 = f(s(g(b())))
problem:
strict:
g(x) -> f(g(x))
weak:
f(f(x)) -> b()
f(g(a())) -> f(s(g(b())))
Open
Tool IRC1
stdout:
MAYBE
Warning when parsing problem:
Unsupported strategy 'OUTERMOST'Tool IRC2
stdout:
TIMEOUT
'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer: TIMEOUT
Input Problem: innermost runtime-complexity with respect to
Rules:
{ f(g(a())) -> f(s(g(b())))
, f(f(x)) -> b()
, g(x) -> f(g(x))}
Proof Output:
Computation stopped due to timeout after 60.0 secondsTool RC1
stdout:
MAYBE
Warning when parsing problem:
Unsupported strategy 'OUTERMOST'Tool RC2
stdout:
TIMEOUT
'Fastest (timeout of 60.0 seconds)'
-----------------------------------
Answer: TIMEOUT
Input Problem: runtime-complexity with respect to
Rules:
{ f(g(a())) -> f(s(g(b())))
, f(f(x)) -> b()
, g(x) -> f(g(x))}
Proof Output:
Computation stopped due to timeout after 60.0 seconds