Elsevier

Theoretical Computer Science

Volume 327, Issue 3, 2 November 2004, Pages 319-347
Theoretical Computer Science

On deterministic finite automata and syntactic monoid size

https://doi.org/10.1016/j.tcs.2004.04.010Get rights and content
Under an Elsevier user license
open archive

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 and lower bounds on the syntactic monoid size depending on the number of generators (input alphabet size) used. It turns out, that the two generator case is the most involved one. There we show a lower bound of nn1-2n for the size of the syntactic monoid of a language accepted by an n-state deterministic finite automaton with binary input alphabet. Moreover, we prove that for every prime n7, the maximal size semigroup w.r.t. its size among all (transformation) semigroups which can be generated with two generators, is generated by a permutation with two cycles (of appropriate lengths) and a non-bijective mapping merging elements from these two cycles. As a by-product of our investigations we determine the maximal size among all semigroups generated by two transformations, where one is a permutation with a single cycle and the other is a non-bijective mapping.

Keywords

Automata theory
Deterministic finite automata
Syntactic monoids

Cited by (0)

This paper is a completely revised and expanded version of two papers presented at the 6th and 7th Conference on Developments in Language Theory (DLT) held in Kyoto, Japan, September 18–21, 2002 and in Szeged, Hungary, July 7–11, 2003, respectively.

1

Part of the work was done while the author was at Institut für Informatik, Technische Universität München, Boltzmannstraße 3, D-85748 Garching bei München, Germany.