Finite state automata are fundamental objects in Theoretical Computer Science and find their application in Text Processing, Compilers Design, Artificial Intelligence and many other areas. The problem of minimizing such objects can be traced back to the '50s and since then it has been the arena for developing new algorithmic ideas. There are two main paradigms to tackle the problem: top down - which builds a descending chain of equivalences by subsequent refinements - and bottom up - which builds an ascending chain of equivalences by aggregation of classes. The former approach leads to a fast O(n log n) algorithm, whereas the latter is currently quadratic for any practical application. Nevertheless, the bottom up algorithm enjoys the property of being incremental, i.e. the minimization process can be stopped at any time obtaining a language-equivalent partially minimized automaton. In this work we correct a small mistake in the algorithm given by Almeida et al. in 2014 and we propose a simple, DFS-like and truly quadratic incremental algorithm for minimizing deterministic automata. Furthermore, we adapt the idea to the nondeterministic case obtaining an incremental algorithm which computes the maximum bisimulation relation in time O(n2r∣Σ∣), where n is the number of states, Σ is the alphabet and r is the degree of nondeterminism, improving by a factor of r the running time of the fastest known aggregation based algorithm for this problem.

Bianchini, C., Policriti, A., Riccardi, B., Romanello, R. (2022). Incremental NFA Minimization. In Proceedings of the 23rd Italian Conference on Theoretical Computer Science Rome, Italy, September 7-9, 2022 (pp.161-173). CEUR-WS.

Incremental NFA Minimization

Riccardi B.
;
2022

Abstract

Finite state automata are fundamental objects in Theoretical Computer Science and find their application in Text Processing, Compilers Design, Artificial Intelligence and many other areas. The problem of minimizing such objects can be traced back to the '50s and since then it has been the arena for developing new algorithmic ideas. There are two main paradigms to tackle the problem: top down - which builds a descending chain of equivalences by subsequent refinements - and bottom up - which builds an ascending chain of equivalences by aggregation of classes. The former approach leads to a fast O(n log n) algorithm, whereas the latter is currently quadratic for any practical application. Nevertheless, the bottom up algorithm enjoys the property of being incremental, i.e. the minimization process can be stopped at any time obtaining a language-equivalent partially minimized automaton. In this work we correct a small mistake in the algorithm given by Almeida et al. in 2014 and we propose a simple, DFS-like and truly quadratic incremental algorithm for minimizing deterministic automata. Furthermore, we adapt the idea to the nondeterministic case obtaining an incremental algorithm which computes the maximum bisimulation relation in time O(n2r∣Σ∣), where n is the number of states, Σ is the alphabet and r is the degree of nondeterminism, improving by a factor of r the running time of the fastest known aggregation based algorithm for this problem.
paper
Automata; Bisimulation; Incremental; Minimization;
English
23rd Italian Conference on Theoretical Computer Science, ICTCS 2022 - 7 September 2022through 9 September 2022
2022
Dal Lago, U; Gorla, D
Proceedings of the 23rd Italian Conference on Theoretical Computer Science Rome, Italy, September 7-9, 2022
2022
3284
161
173
https://ceur-ws.org/Vol-3284/
open
Bianchini, C., Policriti, A., Riccardi, B., Romanello, R. (2022). Incremental NFA Minimization. In Proceedings of the 23rd Italian Conference on Theoretical Computer Science Rome, Italy, September 7-9, 2022 (pp.161-173). CEUR-WS.
File in questo prodotto:
File Dimensione Formato  
Bianchini-2022-CEUR WS Proceedings-VoR.pdf

accesso aperto

Tipologia di allegato: Publisher’s Version (Version of Record, VoR)
Licenza: Creative Commons
Dimensione 1.41 MB
Formato Adobe PDF
1.41 MB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/10281/447041
Citazioni
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
Social impact