Enumeration and generation with a string automata representation

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

Autores

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

Revista

Título: Theoretical Computer Science

Vol. 387

Páginas: 93-102

ISSN: 0304-3975

Editora: Elsevier

Indexação

ISI Web of Knowledge - 24 Citações

Scopus - 35 Citações

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-004-6AQ

DOI: 10.1016/j.tcs.2007.07.029

Abstract (EN): The representation of combinatorial objects is decisive for the feasibility of several enumerative tasks. In this work, we present a unique string representation for complete initially-connected deterministic automata (ICDFAs) with n states over an alphabet of k symbols. For these strings we give a regular expression and show how they are adequate for exact and random generation, allow an alternative way for enumeration and lead to an upper bound for the number of ICDFAs. The exact generation algorithm can be used to partition the set of ICDFAs in order to parallelize the counting of minimal automata, and thus of regular languages. A uniform random generator for ICDFAs is presented that uses a table of pre-calculated values. Based on the same table, an optimal coding for ICDFAs is obtained.

Idioma: Inglês

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

Nº de páginas: 10