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
Zeitschriftenaufsatz / Fach: Informatik
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
Dieser Eintrag ist freigegeben.