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.
Mots-clés : regular languages, finite automata, minimisation algorithms
@article{ITA_2014__48_2_173_0, author = {Almeida, Marco and Moreira, Nelma and Reis, Rog\'erio}, title = {Incremental {DFA} minimisation}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {173--186}, publisher = {EDP-Sciences}, volume = {48}, number = {2}, year = {2014}, doi = {10.1051/ita/2013045}, mrnumber = {3302483}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2013045/} }
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 SP - 173 EP - 186 VL - 48 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2013045/ DO - 10.1051/ita/2013045 LA - en ID - ITA_2014__48_2_173_0 ER -
%0 Journal Article %A Almeida, Marco %A Moreira, Nelma %A Reis, Rogério %T Incremental DFA minimisation %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 173-186 %V 48 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2013045/ %R 10.1051/ita/2013045 %G en %F ITA_2014__48_2_173_0
Almeida, Marco; Moreira, Nelma; Reis, Rogério. Incremental DFA minimisation. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 2, pp. 173-186. doi : 10.1051/ita/2013045. http://archive.numdam.org/articles/10.1051/ita/2013045/
[1] 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.
, , , and ,[2] Enumeration and generation with a string automata representation, Special issue Selected papers of DCFS (2006). Theoret. Comput. Sci. 387 (2007) 93-102. | MR | Zbl
, and ,[3] 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. | MR | Zbl
, and ,[4] Equivalence of regular languages: an algorithmic approach and complexity analysis, Ph.D. thesis. University of Porto (2011).
,[5] 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. | MR | Zbl
,[6] Introduction to Algorithms. The MIT Press, 2nd edition (2003). | MR | Zbl
, , and ,[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] 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. | MR | Zbl
,[9] Introduction to Automata Theory, Languages and Computation. Addison Wesley (2000). | MR | Zbl
, and ,[10] The synthesis of sequential switching circuits. J. Symbolic Logic 20 (1955) 69-70. | Zbl
,[11] Gedanken-experiments on sequential machines. J. Symbolic Logic 23 (1958) 60.
,[12] Efficiency of a good but not linear set union algorithm. J. ACM 22 (1975) 215-225. | MR | Zbl
,[13] Taxonomies and toolkit of regular languages algortihms, Ph.D. thesis. Eindhoven University of Tec. (1995). | MR | Zbl
,[14] An incremental DFA minimization algorithm, in International Workshop on Finite-State Methods in Natural Language Processing. Helsinki, Finland (2001).
,[15] An efficient DFA minimization algorithm. Natur. Lang. Engrg. (2003) 49-64.
and ,Cité par Sources :