Maximal root-state-complexity conjecture for binary languages
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.
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.