Article ID Journal Published Year Pages File Type
420315 Discrete Applied Mathematics 2006 15 Pages PDF
Abstract

A linear recurrence relation is derived for the number of unlabelled initially connected acyclic automata. The coefficients of this relation are determined by another, alternating, recurrence relation. The latter determines, in particular, the number of acyclic automata with labelled states. Certain simple enumerative techniques developed by the author for counting initially connected automata and acyclic digraphs are combined and applied. Calculations show that the results obtained in this paper improve recent upper bounds for the number of minimal deterministic automata (with accepting states) recognizing finite languages. Various related questions are also discussed.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,