An Evaluation of Massively Parallel Algorithms for DFA Minimization

Jan Martens
Anton Wijs

We study parallel algorithms for the minimization of Deterministic Finite Automata (DFAs). In particular, we implement four different massively parallel algorithms on Graphics Processing Units (GPUs). Our results confirm the expectations that the algorithm with the theoretically best time complexity is not practically suitable to run on GPUs due to the large amount of resources needed. We empirically verify that parallel partition refinement algorithms from the literature perform better in practice, even though their time complexity is worse. Lastly, we introduce a novel algorithm based on partition refinement with an extra parallel partial transitive closure step and show that on specific benchmarks it has better run-time complexity and performs better in practice.

In Antonis Achilleos and Adrian Francalanza: Proceedings Fifteenth International Symposium on Games, Automata, Logics, and Formal Verification (GandALF 2024), Reykjavik, Iceland, 19-21 June 2024, Electronic Proceedings in Theoretical Computer Science 409, pp. 138–153.
Published: 30th October 2024.

ArXived at: https://dx.doi.org/10.4204/EPTCS.409.13 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org