Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420315 | Discrete Applied Mathematics | 2006 | 15 Pages |
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
Valery A. Liskovets,