Exact generation of minimal acyclic deterministic finite automata

• Tipo: Artigo em Revista Científica Internacional
• Data: 2008

Autores

Marco Almeida (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogerio Reis (Autor) FCUP

Revista

Título: International Journal of Foundations of Computer Science

Vol. 19

Páginas: 751-765

ISSN: 0129-0541

Editora: World Scientific

Indexação

ISI Web of Knowledge - 3 Citações

Scopus - 1 Citação

Classificação Científica

FOS: Ciências exactas e naturais > Ciências da computação e da informação

Outras Informações

ID Authenticus: 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.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 15