Aspects of enumeration and generation with a string automata representation

• Tipo: Artigo em Livro de Atas de Conferência Internacional
• Data: 2006

Autores

Almeida, M (Autor) Outra; Moreira, N (Autor) FCUP; Reis, R (Autor) FCUP

Ata de Conferência Internacional

Título: 8th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2006 - Proceedings

Páginas: 58-69

8th International Workshop on Descriptional Complexity of Formal Systems, DCFS 2006

Las Cruces, NM, 21 June 2006 through 23 June 2006

Indexação

ISI Web of Knowledge

Scopus - 4 Citações

Outras Informações

ID Authenticus: P-008-KZP

Abstract (EN): In general, the representation of combinatorial objects is decisive for the feasibility of several enuineratiye tasks. In this work, we show how a (unique) string representation for (complete) initially-connected deterministic automata (ICDFA's) with n states over an alphabet of k symbols can be used for counting, exact enumeration, sampling and optimal coding, not only the set of ICDFA's but, to some extent, the set of regular languages. An exact generation algorithm can be used to partition the set of ICDFA's in order to parallelize the counting of minimal automata (and thus of regular languages). We present also a uniform random generator for ICDFA's that uses a table of pre-calculated values. Based on the same table it is also possible to obtain an optimal coding for ICDFA's.

Idioma: Inglês

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

Nº de páginas: 12