INCREMENTAL DFA MINIMISATION

• Type: Article in International Scientific Journal
• Date: 2014

Authors

Marco Almeida (Author) Other; Nelma Moreira (Author) FCUP; Rogerio Reis (Author) FCUP

Journal

Title: RAIRO - Theoretical Informatics and Applications

Vol. 48

Pages: 173-186

ISSN: 0988-3754

Publisher: EDP Sciences

Indexing

ISI Web of Knowledge - 4 Citations

Scopus - 6 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 14