INCREMENTAL DFA MINIMISATION

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

Autores

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

Revista

Título: RAIRO - Theoretical Informatics and Applications

Vol. 48

Páginas: 173-186

ISSN: 0988-3754

Editora: EDP Sciences

Indexação

ISI Web of Knowledge - 4 Citações

Scopus - 6 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-009-HRF

DOI: 10.1051/ita/2013045

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: 14