HP Labs Technical Reports

Click here for full text: PDF

A Generalized Event Structure for the Muller Unfolding of a Safe Net

Gunawardena, Jeremy



Abstract: In 1959 Muller and Bartky published a celebrated paper on "A Theory of Asynchronous Circuits". Among many novel techniques in that paper was the use of lattices resembling the domains of configurations of event structures. In the light of this we present a generalization of Muller's construction to safe nets. We find, however, that this "Muller unfolding" cannot be generated as the domain of configurations of any known event structure, not even a General Event Structure. (In particular, this unfolding differs from that of Nielsen, Plotkin and Winskel.) This paper attempts to fill that gap. We make use of the logical approach to causality, developed in previous work, in which a General Event Structure is interpreted as a logical automation arising from a particular logic of causality. We introduce a new causal logic and associate a corresponding logical automation to any finite safe Petri net. Our main result is that the domain of configurations of this generalized event structure is isomorphic to the Muller unfolding of the net. The work described here was done as part of pro- ject STETSON, a joint project between HP Labs and Stanford University on asynchronous hardware design.

Back to Index

[Research] [News] [Tech Reports] [Palo Alto] [Bristol] [Japan] [Israel] [Site Map][Home] [Hewlett-Packard]