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
Buchaufsatz/Kapitel in Sammelwerk / Fach: Informatik
Titel:
On Deterministic Finite Automata and Syntactic Monoid Size
Autor(in):
Holzer, Markus; König, Barbara im Online-Personal- und -Vorlesungsverzeichnis LSF anzeigen
Erscheinungsjahr
2003
Erschienen 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
WWW URL

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.