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
2004
In: Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), Band 83 (2004), S. 139 - 155
Artikel/Aufsatz in Zeitschrift / Fach: Informatik
Titel:
Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other
Autor(in):
Holzer, Markus; König, Barbara im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen
Erscheinungsjahr
2004
Erschienen in:
Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin), Band 83 (2004), S. 139 - 155
ISSN
WWW URL
WWW URL

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