@article(balcazar1992, author = {J. Balc{\'a}zar and J. Gabarro and M. Santha}, year = {1992}, title = {Deciding bisimilarity is {P}-complete}, journal = {Formal aspects of computing}, volume = {4}, number = {1}, pages = {638--648}, doi = {10.1007/BF03180566}, ) @incollection(thrust, author = {N. Bell and J. Hoberock}, year = {2012}, title = {{Thrust: A Productivity-Oriented Library for CUDA}}, booktitle = {{GPU Computing Gems Jade Edition}}, chapter = {26}, publisher = {Morgan Kaufmann Publishers Inc.}, pages = {359--371}, doi = {10.1016/C2010-0-68654-8}, ) @inproceedings(castiglione2008hopcroft, author = {G. Castiglione and A. Restivo and M. Sciortino}, year = {2008}, title = {Hopcroft's Algorithm and Cyclic Automata}, editor = {Mart{\'{\i}}n-Vide, C. and F. Otto and H. Fernau}, booktitle = {Proc.\ of LATA 2008}, series = {LNCS}, volume = {5196}, publisher = {Springer}, pages = {172--183}, doi = {10.1007/978-3-540-88282-4_17}, ) @article(cho1992parallelcoarsestset, author = {S. Cho and D.T. Huynh}, year = {1992}, title = {The parallel complexity of coarsest set partition problems}, journal = {Information Processing Letters}, volume = {42}, number = {2}, pages = {89--94}, doi = {10.1016/0020-0190(92)90095-D}, ) @inproceedings(fimeman2018nearwork, author = {J.T. Fineman}, year = {2018}, title = {Nearly Work-Efficient Parallel Algorithm for Digraph Reachability}, booktitle = {Proc.\ of STOC 2018}, publisher = {ACM}, pages = {457–470}, doi = {10.1145/3188745.3188926}, ) @article(groote2023lowerbounds, author = {J.F. Groote and J.J.M. Martens and E.P. de Vink}, year = {2023}, title = {{Lowerbounds for bisimulation by partition refinement}}, journal = {{Logical Methods in Computer Science}}, volume = {{Volume 19, Issue 2}}, doi = {10.46298/lmcs-19(2:10)2023}, ) @article(Hillis86, author = {W.D. Hillis and G.L. Steele Jr.}, year = {1986}, title = {Data Parallel Algorithms}, journal = {Communications of the {ACM}}, volume = {29}, number = {12}, pages = {1170--1183}, doi = {10.1145/7902.7903}, ) @incollection(hopcroft1971DFAmin, author = {J. Hopcroft}, year = {1971}, title = {An $n \log n$ algorithm for minimizing states in a finite automaton}, editor = {Z. Kohavi and A. Paz}, booktitle = {Theory of Machines and Computations}, publisher = {Academic Press}, pages = {189--196}, doi = {10.1016/b978-0-12-417750-5.50022-1}, ) @book(jaja1992introduction, author = {J. J\'{a}J\'{a}}, year = {1992}, title = {An introduction to parallel algorithms}, publisher = {Addison Wesley Longman Publishing Co., Inc.}, address = {USA}, ) @inproceedings(jambulapati2019parallel, author = {A. Jambulapati and Y.P. Liu and A. Sidford}, year = {2019}, title = {Parallel reachability in almost linear work and square root depth}, booktitle = {Proc.\ of FOCS 2019}, organization = {IEEE}, pages = {1664--1686}, doi = {10.1109/FOCS.2019.00098}, ) @article(khuller1994parallel, author = {S. Khuller and U. Vishkin}, year = {1994}, title = {On the parallel complexity of digraph reachability}, journal = {Information Processing Letters}, volume = {52}, number = {5}, pages = {239--241}, doi = {10.1016/0020-0190(94)00153-7}, ) @article(martens2022linear, author = {J.J.M. Martens and J.F. Groote and L.B. Haak and P. Hijma and A.J. Wijs}, year = {2022}, title = {Linear parallel algorithms to compute strong and branching bisimilarity}, journal = {Software and Systems Modeling}, pages = {1--25}, doi = {10.1007/s10270-022-01060-7}, ) @incollection(moore1956gedanken, author = {E.F. Moore}, year = {1956}, title = {Gedanken-Experiments on Sequential Machines}, editor = {Claude Shannon and John McCarthy}, booktitle = {Automata Studies}, publisher = {Princeton University Press}, address = {Princeton, NJ}, pages = {129--153}, doi = {10.1515/9781400882618-006}, ) @article(paige1987three, author = {R. Paige and R. E. Tarjan}, year = {1987}, title = {Three partition refinement algorithms}, journal = {SIAM Journal on Computing}, volume = {16}, number = {6}, pages = {973--989}, doi = {10.1137/0216062}, ) @article(powerset, author = {M.O. Rabin and D. Scott}, year = {1959}, title = {Finite automata and their decision problems}, journal = {IBM Journal of Research and Development}, volume = {3}, number = {2}, pages = {114--125}, doi = {10.1147/rd.32.0114}, ) @inproceedings(ravikumar1996paralleldfa, author = {B. Ravikumar and X. Xiong}, year = {1996}, title = {A Parallel Algorithm for Minimization of Finite Automata}, booktitle = {Proceedings of the 10th International Parallel Processing Symposium}, series = {IPPS '96}, publisher = {IEEE Computer Society}, address = {USA}, pages = {187--191}, doi = {10.1109/IPPS.1996.508056}, ) @article(stockmeyer1984simulation, author = {L. Stockmeyer and U. Vishkin}, year = {1984}, title = {Simulation of parallel random access machines by circuits}, journal = {SIAM Journal on Computing}, volume = {13}, number = {2}, pages = {409--422}, doi = {10.1137/0213027}, ) @inproceedings(tewari2002paralleldfa, author = {A. Tewari and U. Srivastava and P. Gupta}, year = {2002}, title = {A Parallel {DFA} Minimization Algorithm}, booktitle = {Proc.\ of HiPC}, series = {LNCS}, volume = {2552}, publisher = {Springer}, pages = {34--40}, doi = {10.1007/3-540-36265-7_4}, ) @book(trachtenbrot1973finite, author = {B.A. Trakhtenbrot and J.M. Barzdin}, year = {1973}, title = {Finite automata: behavior and synthesis}, publisher = {North-Holland Publishing}, ) @inproceedings(ullman1990high, author = {J. Ullman and M. Yannakakis}, year = {1990}, title = {High-Probability Parallel Transitive Closure Algorithms}, booktitle = {Proc.\ of SPAA 1990}, pages = {200--209}, doi = {10.1145/97444.97686}, ) @incollection(wijs2015, author = {A.J. Wijs}, year = {2015}, title = {{GPU} Accelerated Strong and Branching Bisimilarity Checking}, editor = {C. Baier and C. Tinelli}, booktitle = {Proc.\ of TACAS}, series = {LNCS}, volume = {9035}, publisher = {Springer}, pages = {368--383}, doi = {10.1007/978-3-662-46681-0_29}, )