Incremental DFA Minimisation

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

Autores

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

Ata de Conferência Internacional

Título: Implementation and Application of Automata, 17th International Conference (CIAA 2012)

Páginas: 39-48

17th International Conference on Implementation and Application of Automata (CIAA)

Porto, 17-20, Julho, 2012

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 7 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-002-XJT

DOI: 10.1007/978-3-642-18098-9_5

Abstract (EN): We present a new incremental algorithm for minimising deterministic finite automata. It runs in quadratic time for any practical application and may be halted at any point, returning a partially minimised automaton. Hence, the algorithm may be applied to a given automaton at the same time as it is processing a string for acceptance. We also include some experimental comparative results.

Idioma: Inglês

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

Nº de páginas: 10