Maximal root-state-complexity conjecture for binary languages

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 n7n\geq 7, there exist positive coprime integers k2k\geq 2 and l3l\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.

Sources & referencesView supporting material

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.