Maximal root-state-complexity conjecture for binary languages

About 23 years old · traced to

Let TnT_n be the full transformation monoid on an nn-element set, and let Uk,lU_{k,l} be the monoid defined above. For a language LL over an alphabet of size 22, write sc⁡(L)\operatorname{sc}(L) for its state complexity and root⁡(L)\operatorname{root}(L) for its root language. Maximal root-state-complexity conjecture. For every integer n≥7n\geq 7, there exist positive coprime integers k≥2k\geq 2 and l≥3l\geq 3 with k+l=nk+l=n such that, whenever sc⁡(L)≤n\operatorname{sc}(L)\leq n,

sc⁡(root⁡(L))≤∣Uk,l∣−(n2).\operatorname{sc}(\operatorname{root}(L))\leq |U_{k,l}|-\binom{n}{2}.

This bound is tight. The conjecture concerns the maximum blow-up of state complexity under the root operation; the supplied text says the construction is conjectured to achieve the maximum but gives no resolution.

References

Primary source

Bryan Krawetz, John Lawrence and Jeffery Shallit, “State Complexity and the Monoid of Transformations of a Finite Set”, arXiv:math/0306416 (2003).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.