Holzer, Markus; König, Barbara:

On Deterministic Finite Automata and Syntactic Monoid Size

In: Proceedings of the 6th International Conference on Developments in Language Theory, DLT 2002. - (Lecture Notes in Computer Science ; 2450)
Berlin [u.a.]: Springer (2003), S. 429-444
ISBN: 3-540-40431-7
Buchaufsatz / Kapitel / Fach: Informatik
Abstract:
We investigate the relationship between regular languages and syntactic monoid size. In particular, we consider the transformation monoids of n-state (minimal) deterministic finite automata. We show tight upper bounds on the syntactic monoid size, proving that an n- state deterministic finite automaton with singleton input alphabet (input alphabet with at least three letters, respectively) induces a linear (n n , respectively) size syntactic monoid. In the case of two letter input alphabet, we can show a lower bound of n n -( ℓ n )ℓ!n k - ( ℓ n )k kℓℓ for some natural numbers k and ℓ close to n/2, for the size of the syntactic monoid of a language accepted by an n-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 n n tends to 1 as n goes to infinity.