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), Band 83 (2004), S. 139 - 155
2004Artikel/Aufsatz in Zeitschrift
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, BarbaraUDE
- GND
- 1050396502
- LSF ID
- 15982
- ORCID
-
0000-0002-4193-2889
- Sonstiges
- der Hochschule zugeordnete*r Autor*in
Erscheinungsjahr:
2004
Erschienen in
Bulletin of the European Association for Theoretical Computer Science (EATCS Bulletin)
in:
Band 83 (2004), S. 139 - 155
ISSN
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