An Evaluation of Massively Parallel Algorithms for DFA Minimization

Onderzoeksoutput: Bijdrage aan tijdschriftCongresartikelpeer review

2 Downloads (Pure)

Samenvatting

We study parallel algorithms for the minimization of Deterministic Finite Automata (DFAs). In particular, we implement four different massively parallel algorithms for DFA minimization 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.

Originele taal-2Engels
Pagina's (van-tot)138-153
Aantal pagina's16
TijdschriftElectronic Proceedings in Theoretical Computer Science, EPTCS
Volume409
DOI's
StatusGepubliceerd - 30 okt. 2024
Evenement15th International Symposium on Games, Automata, Logics, and Formal Verification, G and ALF 2024 - Reykjavik, IJsland
Duur: 19 jun. 202421 jun. 2024

Bibliografische nota

Publisher Copyright:
© J.J.M. Martens & A.J. Wijs.

Vingerafdruk

Duik in de onderzoeksthema's van 'An Evaluation of Massively Parallel Algorithms for DFA Minimization'. Samen vormen ze een unieke vingerafdruk.

Citeer dit