Abstract
We present a method for decomposing modal formulas for processes with the internal action τ. To decide whether a process algebra term satisfies a modal formula, one can check whether its subterms satisfy formulas that are obtained by decomposing the original formula. The decomposition uses the structural operational semantics that underlies the process algebra. We use this decomposition method to derive congruence formats for branching and rooted branching bisimulation equivalence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bergstra, J.A., Klop, J.W.: Process algebra for synchronous communication. Information and Control 60(1/3), 109–137 (1984)
Bloom, B.: Structural operational semantics for weak bisimulations. Theoretical Computer Science 146(1/2), 25–68 (1995)
Bloom, B., Fokkink, W.J., van Glabbeek, R.J.: Precongruence formats for decorated trace semantics. ACM Transactions on Computational Logic 5(1), 26–78 (2004)
Bloom, B., Istrail, S., Meyer, A.R.: Bisimulation can’t be traced. Journal of the ACM 42(1), 232–268 (1995)
Bol, R.N., Groote, J.F.: The meaning of negative premises in transition system specifications. Journal of the ACM 43(5), 863–914 (1996)
De Nicola, R., Vaandrager, F.W.: Three logics for branching bisimulation. Journal of the ACM 42(2), 458–487 (1995)
Fokkink, W.J.: Rooted branching bisimulation as a congruence. Journal of Computer and System Sciences 60(1), 13–37 (2000)
Fokkink, W.J., van Glabbeek, R.J.: Ntyft/ntyxt rules reduce to ntree rules. Information and Computation 126(1), 1–10 (1996)
Fokkink, W.J., van Glabbeek, R.J., de Wind, P.: Compositionality of Hennessy-Milner logic by structural operational semantics. Theoretical Computer Science 354(3), 421–440 (2006)
Fokkink, W.J., van Glabbeek, R.J., de Wind, P.: Divide and congruence applied to η-bisimulation. In: Proc. SOS 2005. ENTCS. Elsevier, Amsterdam (to appear, 2005)
van Glabbeek, R.J.: The linear time-branching time spectrum II: The semantics of sequential systems with silent moves. In: Best, E. (ed.) CONCUR 1993. LNCS, vol. 715, pp. 66–81. Springer, Heidelberg (1993)
van Glabbeek, R.J.: The meaning of negative premises in transition system specifications II. Journal of Logic and Algebraic Programming 60/61, 229–258 (2004)
van Glabbeek, R.J.: On cool congruence formats for weak bisimulations (extended abstract). In: Van Hung, D., Wirsing, M. (eds.) ICTAC 2005. LNCS, vol. 3722, pp. 331–346. Springer, Heidelberg (2005)
van Glabbeek, R.J., Weijland, W.P.: Branching time and abstraction in bisimulation semantics. Journal of the ACM 43(3), 555–600 (1996)
Groote, J.F.: Transition system specifications with negative premises. Theoretical Computer Science 118(2), 263–299 (1993)
Groote, J.F., Vaandrager, F.W.: Structured operational semantics and bisimulation as a congruence. Information and Computation 100(2), 202–260 (1992)
Hennessy, M.C.B., Milner, R.: Algebraic laws for non-determinism and concurrency. Journal of the ACM 32(1), 137–161 (1985)
Kleene, S.C.: Representation of events in nerve nets and finite automata. In: Shannon, C., McCarthy, J. (eds.) Automata Studies, pp. 3–41. Princeton University Press, Princeton (1956)
Larsen, K.G., Liu, X.: Compositionality through an operational semantics of contexts. Journal of Logic and Computation 1(6), 761–795 (1991)
Plotkin, G.D.: A structural approach to operational semantics. Journal of Logic and Algebraic Programming 60/61, 17–139 (2004); Originally appeared in 1981
de Simone, R.: Higher-level synchronising devices in Meije–SCCS. Theoretical Computer Science 37(3), 245–267 (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
Fokkink, W., van Glabbeek, R., de Wind, P. (2006). Divide and Congruence: From Decomposition of Modalities to Preservation of Branching Bisimulation. In: de Boer, F.S., Bonsangue, M.M., Graf, S., de Roever, WP. (eds) Formal Methods for Components and Objects. FMCO 2005. Lecture Notes in Computer Science, vol 4111. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11804192_10
Download citation
DOI: https://doi.org/10.1007/11804192_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-36749-9
Online ISBN: 978-3-540-36750-5
eBook Packages: Computer ScienceComputer Science (R0)