Abstract
Relational Coarsest Partition Problems (RCPPs) play a vital role in verifying concurrent systems. It is known that RCPPs are P-complete and hence it may not be possible to design polylog time parallel algorithms for these problems.
In this paper, we present a parallel algorithm for RCPP, in which its associated label transition system is assumed to have m transitions and n states. This algorithm runs in O(n1+ε) time using m/n ε EREW PRAM processors, for any fixed ε<1. This algorithm is analogous and optimal with respect to the sequential algorithm of Kanellakis and Smolka. The same algorithm runs in time O(n log n) using m/log n log log n CRCW PRAM processors. We also describe implementation and experimental results on performance of our algorithm.
This research was supported in part by NSF CCR93-11622 and DARPA/NSF CCR90-14621.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
C. Alvarez, J.L. Balcazar, J. Gabarro, and M. Santha. Parallel Complexity in the Design and Analysis of Concurrent Systems. In PARLE '91. Parallel Architectures and Languages Europe, Vol 1. Springer-Verlag LNCS 505, 1991.
P.C.P. Bhatt, K. Diks, T. Hagerup, V.C. Prasad, T. Radzik, and S. Saxena. Improved Deterministic Parallel Integer Sorting. Information and Computation, pages 29–47, 1991.
R.P. Brent. The Parallel Evaluation of General Arithmetic Expressions. Journal of the ACM, 21(2):201–208, 1974.
R. Cole. Parallel Merge Sort. SIAM Journal on Computing, 17:770–785, 1988.
J. Já Já. Parallel Algorithms: Design and Analysis. Addison-Wesley Publishers, 1992.
P.C. Kanellakis and S.A. Smolka. CCS Expressions, Finite State Processes, and Three Problems of Equivalence. Information and Computation, 86:43–68, 1990.
I. Lee and S. Rajasekaran. Parallel Algorithms for Relational Coarsest Partition Problems. Technical Report MS-CIS-93-71, Dept. of CIS, Univ. of Pennsylvania, July 1993.
R. Paige and R.E. Tarjan. Three Partition Refinement Algorithms. SIAM Journal on Computing, 16(6):973–989, 1987.
S. Zhang and S.A. Smolka. Towards efficient parallelization of equivalence checking algorithms. Unpublished Manuscript, 1993.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1994 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Lee, I., Rajasekaran, S. (1994). A parallel algorithm for relational coarsest partition problems and its implementation. In: Dill, D.L. (eds) Computer Aided Verification. CAV 1994. Lecture Notes in Computer Science, vol 818. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-58179-0_71
Download citation
DOI: https://doi.org/10.1007/3-540-58179-0_71
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-58179-6
Online ISBN: 978-3-540-48469-1
eBook Packages: Springer Book Archive