The parallel complexity of coarsest set partition problems. (English) Zbl 0780.68056

Summary: We investigate two different versions of coarsest set partition problems. They are (1) single-function coarsest set partition, and (2) multi- function coarsest set partition. We classify the parallel complexity of these two problems and present for them several parallel algorithms. We also note that the single-relation and multi-relation coarsest set partition problems are both \(P\)-complete.


68Q25 Analysis of algorithms and problem complexity
68W15 Distributed algorithms
Full Text: DOI


[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Alvarez, C.; Balcazar, J.L.; Gabarro, J.; Santha, M., Parallel complexity in the design and analysis of concurrent systems, Proc. PARLE’91, 505, (1991), Springer Berlin, Lecture Notes in Computer Science
[3] Cho, S.; Huynh, D.T., The parallel complexity of finite state automate problems, Inform. and comput., (1992), to appear
[4] Cook, S., A taxonomy of problems with fast parallel algorithms, Inform. and comput., 64, 2-22, (1985) · Zbl 0575.68045
[5] Gibbons, A.; Rytter, W., Efficient parallel algorithms, (1988), Cambridge University Press Cambridge · Zbl 0771.68015
[6] Hopcroft, J.; Ullman, J., Introduction to automata theory, languages and computation, (1979), Addison-Wesley Reading, MA · Zbl 0426.68001
[7] Hopcroft, J.E., An n log n algorithm for minimizing the states in a finite automaton, (), 189-196
[8] Immerman, N., Nondeterministic space is closed under complement, SIAM J. comput., 17, 935-938, (1988) · Zbl 0668.68056
[9] Jackson, A.; Ramanan, P., An efficient algorithm for a special case of the set partition problem, Proc. 27th ann. allerton conf. on communication, control and computing, (1989)
[10] Kanellakis, P.C.; Smolka, S.A., CCS expressions, finite state processes and three problems of equivalence, Inform. and comput., 86, 43-68, (1990) · Zbl 0705.68063
[11] Page, R.; Tarjan, R.E.; Bonic, R., A linear time solution to the single function coarsest set partition problem, Theoret. comput. sci., 40, 67-84, (1985) · Zbl 0574.68060
[12] Page, R.; Tarjan, R.E., Three partition refinement algorithms, SIAM J. comput., 16, 973-989, (1987) · Zbl 0654.68072
[13] Srikant, Y.N., A parallel algorithm for the minimization of finite state automata, Internat. J. comput. math., 32, 1-11, (1990) · Zbl 0825.68461
[14] Szelepcsenyi, R., The method of forced enumeration for nondeterministic automata, Acta inform., 29, 279-284, (1988) · Zbl 0638.68046
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.