Forward Injective Finite Automata: Exact and Random Generation of Nonisomorphic NFAs

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

Autores

Ferreira, M (Autor) Outra; Nelma Moreira (Autor) FCUP; Rogério Reis (Autor) FCUP

Ata de Conferência Internacional

Título: DESCRIPTIONAL COMPLEXITY OF FORMAL SYSTEMS, DCFS 2018

Páginas: 88-100

20th IFIP WG 1.02 International Conference on Descriptional Complexity of Formal Systems (DCFS)

Saint Mary's Univ, Halifax, CANADA, JUL 25-27, 2018

Indexação

ISI Web of Knowledge - 0 Citações

Scopus - 1 Citação

Classificação Científica

CORDIS: Ciências Físicas > Ciência de computadores

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

Outras Informações

ID Authenticus: P-00P-262

DOI: 10.1007/978-3-319-94631-3_8

Abstract (EN): We define the class of forward injective finite automata (FIFA) and study some of their properties. Each FIFA has a unique canonical representation up to isomorphism. Using this representation an enumeration is given and an efficient uniform random generator is presented. We provide a conversion algorithm from a nondeterministic finite automaton or regular expression into an equivalent FIFA. Finally, we present some experimental results comparing the size of FIFA with other automata.

Idioma: Inglês

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

Nº de páginas: 13