Incremental DFA Minimisation

• Type: Article in International Conference Proceedings Book
• Date: 2011

Authors

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

Conference proceedings International

Title: Implementation and Application of Automata, 17th International Conference (CIAA 2012)

Pages: 39-48

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

Porto, 17-20, Julho, 2012

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 7 Citations

Scientific classification

FOS: Natural sciences > Computer and information sciences

Other information

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

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 10