Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State ...


Markus Holzer and Barbara König. Regular languages, sizes of syntactic monoids, graph colouring, state complexity results, and how these topics are related to each other. EATCS Bulletin, 83:139–155, June 2004. Appeared in The Formal Language Theory Column.


We invite the reader to join our quest for the largest subsemigroup of a transformation monoid on 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.

Suggested BibTeX entry:

    author = {Markus Holzer and Barbara K{\"o}nig},
    journal = {EATCS Bulletin},
    month = {June},
    note = {Appeared in The Formal Language Theory Column},
    pages = {139--155},
    title = {Regular Languages, Sizes of Syntactic Monoids, Graph Colouring, State Complexity Results, and How These Topics are Related to Each Other},
    volume = {83},
    year = {2004}

GZipped PostScript (74 kB)PDF (140 kB)
© University of Duisburg-Essen, Theoretical Computer Science group