An evaluation of massively parallel algorithms for DFA minimization

DOI10.4204/EPTCS.409.13MaRDI QIDQ6940512zbMATH OpenFDO

Authors Jan Martens, Anton Wijs

Publication date 19 August 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4204/EPTCS.409.13

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Parallel algorithms in computer science (68W10)

Cites work

• Deciding bisimilarity is P-complete
• Hopcroft’s Algorithm and Cyclic Automata
• scientific article; zbMATH DE number 3427224 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 3460178 (Why is no real title available?)
• scientific article; zbMATH DE number 1955813 (Why is no real title available?)
• scientific article; zbMATH DE number 7354705 (Why is no real title available?)
• Lowerbounds for Bisimulation by Partition Refinement
• Nearly work-efficient parallel algorithm for digraph reachability
• On the parallel complexity of digraph reachability
• Parallel reachability in almost linear work and square root depth
• Simulation of Parallel Random Access Machines by Circuits
• The parallel complexity of coarsest set partition problems
• Three Partition Refinement Algorithms

This page was built for publication: An evaluation of massively parallel algorithms for DFA minimization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6940512)