Abstract
Decidability of bisimilarity for Process Algebra (PA) processes, arising by mixing sequential and parallel composition, is a long-standing open problem. The known results for subclasses contain the decidability of bisimilarity between basic sequential (i.e. BPA) processes and basic parallel processes (BPP). Here we revisit this subcase and derive an exponential-time upper bound. Moreover, we show that the problem if a given basic parallel process is inherently sequential, i.e. bisimilar with an unspecified BPA process, is PSPACE-complete. We also introduce a model of one-counter automata, with no zero tests but with counter resets, that capture the behaviour of processes in the intersection of BPA and BPP.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Benedikt, M., Göller, S., Kiefer, S., Murawski, A.: Bisimilarity of pushdown systems is nonelementary. In: Proc. 28th LiCS. IEEE Computer Society (to appear, 2013)
Burkart, O., Caucal, D., Moller, F., Steffen, B.: Verification on infinite structures. In: Handbook of Process Algebra, pp. 545–623. Elsevier (2001)
Burkart, O., Caucal, D., Steffen, B.: An elementary decision procedure for arbitrary context-free processes. In: Hájek, P., Wiedermann, J. (eds.) MFCS 1995. LNCS, vol. 969, pp. 423–433. Springer, Heidelberg (1995)
Černá, I., Křetínský, M., Kučera, A.: Comparing expressibility of normed BPA and normed BPP processes. Acta Informatica 36, 233–256 (1999)
Czerwinski, W., Fröschle, S.B., Lasota, S.: Partially-commutative context-free processes: Expressibility and tractability. Information and Computation 209(5), 782–798 (2011)
Esparza, J.: Petri nets, commutative context-free grammars, and basic parallel processes. Fundamenta Informaticae 31(1), 13–25 (1997)
Hirshfeld, Y., Jerrum, M.: Bisimulation equivalence is decidable for normed process algebra. In: Wiedermann, J., Van Emde Boas, P., Nielsen, M. (eds.) ICALP 1999. LNCS, vol. 1644, pp. 412–421. Springer, Heidelberg (1999)
Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial-time algorithm for deciding bisimulation equivalence of normed basic parallel processes. Mathematical Structures in Computer Science 6, 251–259 (1996)
Hirshfeld, Y., Jerrum, M., Moller, F.: A polynomial algorithm for deciding bisimilarity of normed context-free processes. Theor. Comput. Sci. 158, 143–159 (1996)
Jančar, P.: Bisimilarity on basic process algebra is in 2-ExpTime (an explicit proof). Logical Methods in Computer Science 9(1) (2013)
Jančar, P., Kot, M., Sawa, Z.: Complexity of deciding bisimilarity between normed BPA and normed BPP. Information and Computation 208(10), 1193–1205 (2010)
Jančar, P.: Strong bisimilarity on basic parallel processes is PSPACE-complete. In: Proc. 18th LiCS, pp. 218–227. IEEE Computer Society (2003)
Jančar, P., Kučera, A., Moller, F.: Deciding bisimilarity between BPA and BPP processes. In: Amadio, R.M., Lugiez, D. (eds.) CONCUR 2003. LNCS, vol. 2761, pp. 159–173. Springer, Heidelberg (2003)
Kiefer, S.: BPA bisimilarity is EXPTIME-hard. Information Processing Letters 113(4), 101–106 (2013)
Sénizergues, G.: The bisimulation problem for equational graphs of finite out-degree. SIAM J. Comput. 34(5), 1025–1106 (2005)
Srba, J.: Strong bisimilarity of simple process algebras: Complexity lower bounds. Acta Informatica 39, 469–499 (2003)
Srba, J.: Roadmap of infinite results. In: Current Trends In Theoretical Computer Science, The Challenge of the New Century, vol. 2, pp. 337–350. World Scientific Publishing Co. (2004), for an updated version see http://users-cs.au.dk/srba/roadmap/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Czerwiński, W., Jančar, P., Kot, M., Sawa, Z. (2013). Complexity of Checking Bisimilarity between Sequential and Parallel Processes. In: Chatterjee, K., Sgall, J. (eds) Mathematical Foundations of Computer Science 2013. MFCS 2013. Lecture Notes in Computer Science, vol 8087. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-40313-2_28
Download citation
DOI: https://doi.org/10.1007/978-3-642-40313-2_28
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-40312-5
Online ISBN: 978-3-642-40313-2
eBook Packages: Computer ScienceComputer Science (R0)