Holzer, Markus; König, Barbara:

Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other

In: Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), Jg. 83 (2004), S. 139-155
ISSN: 0252-9742
Zeitschriftenaufsatz / Fach: Informatik
Abstract:
We invite the reader to join our quest for the largest subsemigroup of a transformation monoid on~$n$ elements generated by two transformations. Some of the presented results were independently obtained by the authors [HoKo,HoKo02b,HoKo03] and Krawetz, Lawrence, and Shallit [Kr03,KLS03]. In particular, we will see how a surprising connection to graph colouring and chromatic polynomials is very helpful to count the elements of the investigated subsemigroup of transformations. At the end of our search, we will present some applications of these results to state complexity problems for one- and two-way finite automata.
Appeared in The Formal Language Theory Column