Incremental DFA minimisation

Marco Almeida; Nelma Moreira; Rogério Reis

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 2, page 173-186
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Almeida, Marco, Moreira, Nelma, and Reis, Rogério. "Incremental DFA minimisation." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.2 (2014): 173-186. <http://eudml.org/doc/273041>.

@article{Almeida2014,
abstract = {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.},
author = {Almeida, Marco, Moreira, Nelma, Reis, Rogério},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {regular languages; finite automata; minimisation algorithms},
language = {eng},
number = {2},
pages = {173-186},
publisher = {EDP-Sciences},
title = {Incremental DFA minimisation},
url = {http://eudml.org/doc/273041},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Almeida, Marco
AU - Moreira, Nelma
AU - Reis, Rogério
TI - Incremental DFA minimisation
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 2
SP - 173
EP - 186
AB - 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.
LA - eng
KW - regular languages; finite automata; minimisation algorithms
UR - http://eudml.org/doc/273041
ER -

References

top
  1. [1] A. Almeida, M. Almeida, J. Alves, N. Moreira and R. Reis, FAdo and GUItar: tools for automata manipulation and visualization, in vol. 5642 14th CIAA’09, edited by S. Maneth. Lect. Notes Comput. Sci. Springer (2009) 65–74. 
  2. [2] M. Almeida, N. Moreira and R. Reis, Enumeration and generation with a string automata representation, Special issue Selected papers of DCFS (2006). Theoret. Comput. Sci. 387 (2007) 93–102. Zbl1143.68031MR2362181
  3. [3] M. Almeida, N. Moreira and R. Reis, Incremental DFA minimisation, in Proc. of the 15th International Conference on Implementation and Application of Automata (CIAA 2010) Winnipeg, MA, Canada, vol. 6482 of Lect. Notes Comput. Sci., edited by M. Domaratzki and K. Salomaa. Springer-Verlag (2010) 39–48. Zbl1297.68103MR2776275
  4. [4] M. Almeida, Equivalence of regular languages: an algorithmic approach and complexity analysis, Ph.D. thesis. University of Porto (2011). 
  5. [5] J.A. Brzozowski, Canonical regular expressions and minimal state graphs for definite events, in vol. 12 of Proc. of the Sym. on Math. Theory of Automata, edited by J. Fox. MRI Symposia Series, New York (1963) 529–561. Zbl0116.33605MR175719
  6. [6] T.H. Cormen, C.E. Leiserson, R.L. Rivest and C. Stein, Introduction to Algorithms. The MIT Press, 2nd edition (2003). Zbl1158.68538MR1848805
  7. [7] Project FAdo, FAdo: tools for formal languages manipulation. , Access date:1.11.2011 http://fado.dcc.fc.up.pt/, Access date:1.11.2011. 
  8. [8] J. Hopcroft, An nlog n algorithm for minimizing states in a finite automaton, in Proc. Inter. Symp. on the Theory of Machines and Computations, Haifa, Israel. Academic Press (1971) 189–196. Zbl0293.94022MR403320
  9. [9] J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to Automata Theory, Languages and Computation. Addison Wesley (2000). Zbl0980.68066MR645539
  10. [10] D.A. Huffman, The synthesis of sequential switching circuits. J. Symbolic Logic20 (1955) 69–70. Zbl0166.27201
  11. [11] E.F. Moore, Gedanken-experiments on sequential machines. J. Symbolic Logic 23 (1958) 60. 
  12. [12] R.E. Tarjan, Efficiency of a good but not linear set union algorithm. J. ACM22 (1975) 215–225. Zbl0307.68029MR458996
  13. [13] B.W. Watson, Taxonomies and toolkit of regular languages algortihms, Ph.D. thesis. Eindhoven University of Tec. (1995). Zbl0832.68064MR1349341
  14. [14] B.W. Watson, An incremental DFA minimization algorithm, in International Workshop on Finite-State Methods in Natural Language Processing. Helsinki, Finland (2001). 
  15. [15] B.W. Watson and J. Daciuk, An efficient DFA minimization algorithm. Natur. Lang. Engrg. (2003) 49–64. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.