Abstract
History preserving bisimulation takes full account of the interplay between causality and branching, and it induces a congruence w.r.t. action refinement; but even for finite safe Petri nets it is based on a possibly infinite transition system. We introduce ordered markings of nets and the corresponding OM-bisimulation. It is shown that OM-bisimilarity coincides with history preserving bisimilarity, and that it can be decided for finite safe nets.
This work was partially supported by the ESPRIT Basic Research Action No. 3148 DEMON and by the Deutsche Forschungsgemeinschaft, SFB 342: Methoden und Werkzeuge zur Nutzung paralleler Rechnerarchitekturen, TU München
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Aceto and M. Hennessy. Adding action refinement to a finite process algebra. Technical Report 6/90, Dept. Comp. Sci. Univ. of Sussex, Brigthon, 1990.
G. Boudol and I. Castellani. On the semantics of concurrency: Partial orders and transition systems. In H. Ehrig et al., editors, TAPSOFT 87, Vol. I, Lect. Notes Comp. Sci. 249, 123–137, 1987.
E. Best and R. Devillers. Sequential and concurrent behaviour in Petri net theory. Theoret. Comput. Sci., 55:87–136, 1987.
E. Best, R. Devillers, A. Kiehn, and L. Pomello. Fully concurrent bisimulation. Technical Report LIT-202, Univ. Bruxelles, 1989. To appear in Acta Informatica.
P. Darondeau and P. Degano. Event structures, causal trees, and refinements. In B. Rovan, editor, MFCS 90, Lect. Notes Comp. Sci. 452, 239–245, 1990.
P. Degano, R. De Nicola, and U. Montanari. Partial orderings descriptions and observations of nondeterministic concurrent processes. In J.W. de Bakker et al., editors, Proc. REX School / Workshop Linear Time, Branching Time and Partial Order in Logic and Models of Concurrency. Noordwijkerhout, 1988, Lect. Notes Comp. Sci. 354, 438–466, 1989.
R. Devillers. Maximality preserving bisimulation. Technical Report LIT-214, Univ. Bruxelles, 1990.
P. Degano and U. Montanari. Concurrent histories: A basis for observing distributed systems. J. Comp. Sys. Sci., 34:422–461, 1987.
R.J. v. Glabbeek and U. Goltz. Equivalence notions for concurrent systems and refinement of actions. In A. Kreczmar and G. Mirkowska, editors, MFCS 89, Lect. Notes Comp. Sci. 379, 237–248, 1989.
R.J. v. Glabbeek. The refinement theorem for ST-bisimulation semantics. In M. Broy and C.B. Jones, editors, Proc. IFIP Working Conference on Programming Concepts and Methods, Sea of Galilee, Israel, 1990. To appear.
U. Goltz and W. Reisig. The non-sequential behaviour of Petri nets. Information and Control, 57:125–147, 1983.
J. Grabowski. On partial languages. Fundamenta Informaticae, IV.2:428–498, 1981.
R.J. v. Glabbeek and W.P. Weijland. Refinement in branching time semantics. In Proc. AMAST Conf., pages 197–201, 1989.
R. Milner. Calculi for synchrony and asynchrony. Theor. Comput. Sci., 25:267–310, 1983.
M. Nielsen, U. Engberg, and K. Larsen. Partial order semantics for concurrency. In J.W. de Bakker et al., editors, Proc. REX School / Workshop Linear Time, Branching Time and Partial Order in Logic and Models of Concurrency. Noordwijkerhout, 1988, Lect. Notes Comp. Sci. 354, 523–548, 1989.
M. Nielsen, G.D. Plotkin, and G. Winskel. Petri nets, event structures and domains I. Theor. Comput. Sci., 13:85–108, 1981.
D. Park. Concurrency and automata on infinite sequences. In P. Deussen, editor, Proc. 5th GI Conf. on Theoretical Comp. Sci., Lect. Notes Comp. Sci. 104, 167–183, 1981.
V. Pratt. On the composition of processes. In Proc. 9th ACM Symp. on Principles of Programming Languages, pages 213–223, 1982.
A. Rabinovich and B.A. Trakhtenbrot. Behaviour structures and nets. Fundamenta Informaticae, 11:357–404, 1988.
W. Vogler. Failures semantics based on interval semiwords is a congruence for refinement. Distributed Computing, 4, 1991. To appear. An extended abstract has appeared in C. Choffrut and T. Lengauer, editors, STACS 90, Lect. Notes Comp. Sci. 415, 285–297, 1990.
W. Vogler. Bisimulation and action refinement. In C. Choffrut and M. Jantzen, editors, STACS 91, Lect. Notes Comp. Sci. 480, 309–321, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1991 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Vogler, W. (1991). Deciding history preserving bisimilarity. In: Albert, J.L., Monien, B., Artalejo, M.R. (eds) Automata, Languages and Programming. ICALP 1991. Lecture Notes in Computer Science, vol 510. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-54233-7_158
Download citation
DOI: https://doi.org/10.1007/3-540-54233-7_158
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-54233-9
Online ISBN: 978-3-540-47516-3
eBook Packages: Springer Book Archive