Maximal root-state-complexity conjecture for binary languages
Let be the full transformation monoid on an -element set, and let be the monoid defined above. For a language over an alphabet of size , write for its state complexity and for its root language. Maximal root-state-complexity conjecture. For every integer , there exist positive coprime integers and with such that, whenever ,
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
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.