On Deterministic Finite Automata and Syntactic Monoid Size

Reference

Markus Holzer and Barbara König. On deterministic finite automata and syntactic monoid size. In Proc. of DLT '02 (Developments in Language Theory), pages 258–269. Springer-Verlag, 2003. LNCS 2450.

Abstract

We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of -state (minimal) deterministic finite automata. We show tight upper bounds on the syntactic monoid size, proving that an -state deterministic finite automaton with singleton input alphabet (input alphabet with at least three letters, esp) induces a linear (, esp) size syntactic monoid. In the case of two letter input alphabet, we can show a lower bound of , for some natural numbers and close to , for the size of the syntactic monoid of a language accepted by an -state deterministic finite automaton. This induces a family of deterministic finite automata such that the fraction of the size of the induced syntactic monoid and tends to as goes to infinity.

Suggested BibTeX entry:

@inproceedings{HK02,
    author = {Markus Holzer and Barbara K{\"o}nig},
    booktitle = {Proc. of DLT '02 (Developments in Language Theory)},
    note = {{LNCS} 2450},
    pages = {258--269},
    publisher = {Springer-Verlag},
    title = {On Deterministic Finite Automata and Syntactic Monoid Size},
    year = {2003}
}

GZipped PostScript (76 kB)PDF (141 kB)Journal version