Abstract
We propose the notions of “density” and “connectivity” of infinite process graphs and investigate them in the context of the well-known process algebras BPA and BPP. For a process graph G, the density function in a state s maps a natural number n to the number of states of G with distance less or equal to n from s. The connectivity of a process graph G in a state s is a measure for how many different ways “of going from s to infinity” exist in G.
For BPA-graphs we discuss some tentative findings about the notions density and connectivity, and indicate how they can be used to establish some non-definability results, stating that certain process graphs are not BPA-graphs, and stronger, not even BPA-definable. For BPP-graphs, which are associated with processes from the class of Basic Parallel Processes (BPP), we prove that their densities are at most polynomial. And we use this fact for showing that the paradigmatic process Queue is not expressible in BPP.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Baeten, J.C.M., Bergstra, J.A.: Global renaming operators in concrete process algebra. Information and Computation, 205–245 (1988)
Baeten, J.C.M., Bergstra, J.A., Klop, J.W.: Decidability of bisimulation equivalence for process generating context-free languages. Journal of the ACM 40(3), 653–682 (1993)
Baeten, J.C.M., Weijland, W.P.: Process Algebra. In: Cambridge Tracts in Theoretical Computer Science, vol. 18. Cambridge University Press, Cambridge (1990)
Bergstra, J.A., Klop, J.W.: The algebra of recursively defined processes and the algebra of regular processes. In: Paredaens, J. (ed.) ICALP 1984. LNCS, vol. 172, pp. 82–95. Springer, Heidelberg (1984)
Bergstra, J.A., Klop, J.W.: Process algebra for synchronous communication. Information and Control 60(1–3), 109–137 (1984)
Bergstra, J.A., Klop, J.W.: Process algebra: specification and verification in bisimulation semantics. In: Hazewinkel, M., Lenstra, J.K., Meertens, L.G.L.T. (eds.) CWI Monograph 4, Proceedings of the CWI Symposium Mathematics and Computer Science II, pp. 61–94. North-Holland, Amsterdam (1986)
Bergstra, J.A., Tiuryn, J.: Process algebra semantics for queues. Fundamenta Informaticae X, 213–224 (1987)
Burkart, O., Caucal, D., Steffen, B.: Bisimulation collapse and the process taxonomy. In: Proceedings of CONCUR 1996 (1996)
Caucal, D., Montfort, R.: On the transition graphs of automata and grammars. In: Möhring, R.H. (ed.) WG 1990. LNCS, vol. 484, pp. 61–86. Springer, Heidelberg (1991)
Caucal, D.: Graphes canoniques de graphes algébriques. Theoret. Inform. and Appl. 24(4), 339–352 (1990)
Caucal, D.: On the regular structure of prefix rewriting. Theoretical Computer Science (1992)
Christensen, S.: Decidability and Decompostion in Process Algebras. PhD thesis, University of Edinburgh (1993)
Christensen, S., Hirshfeld, Y., Moller, F.: Bisimulation equivalence is decidable for basic parallel processes. In: CONCUR, pp. 143–157 (1993)
Freudenthal, H.: Über die Enden topologischer Räume und Gruppen. Mathematische Zeitschrift 33, 692–713 (1931)
Groote, J.F., van Ham, F.J.J.: Interactive visualization of large state spaces. International Journal on Software Tools for Technology Transfer (2005)
Mayr, R.: Process rewrite systems. Information and Computation 156(1), 264–286 (2000)
Muller, D.E., Schupp, P.E.: Groups, the theory of ends, and context-free languages. Journal of Computer and System Sciences 26, 295–310 (1983)
Muller, D.E., Schupp, P.E.: The theory of ends, pushdown automata, and second-order logic. Theoretical Computer Science 37, 51–75 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Grabmayer, C., Klop, J.W., Luttik, B. (2006). Some Remarks on Definability of Process Graphs. In: Baier, C., Hermanns, H. (eds) CONCUR 2006 – Concurrency Theory. CONCUR 2006. Lecture Notes in Computer Science, vol 4137. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11817949_2
Download citation
DOI: https://doi.org/10.1007/11817949_2
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-37376-6
Online ISBN: 978-3-540-37377-3
eBook Packages: Computer ScienceComputer Science (R0)