Exact generation of minimal acyclic deterministic finite automata

• Type: Article in International Scientific Journal
• Date: 2008

Authors

Marco Almeida (Author) Other; Nelma Moreira (Author) FCUP; Rogerio Reis (Author) FCUP

Journal

Title: International Journal of Foundations of Computer Science

Vol. 19

Pages: 751-765

ISSN: 0129-0541

Publisher: World Scientific

Indexing

ISI Web of Knowledge - 3 Citations

Scopus - 1 Citation

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: P-003-XB5

DOI: 10.1142/s0129054108005930

Abstract (EN): We give a canonical representation for minimal acyclic deterministic finite automata (MADFA) with n states over an alphabet of k symbols. Using this normal form, we present a method for the exact generation of MADFAs. This method avoids a rejection phase that would be needed if a generation algorithm for a larger class of objects that contains the MADFAs were used. We give upper and lower bounds for MADFAs enumeration and some exact formulas for small values of n.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 15