On the Expressiveness of Higher Dimensional Automata: (Extended Abstract)

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

In this paper I compare the expressive power of several models of concurrency based on their ability to represent causal dependence. To this end, I translate these models, in behaviour preserving ways, into the model of higher dimensional automata, which is the most expressive model under investigation. In particular, I propose four different translations of Petri nets, corresponding to the four different computational interpretations of nets found in the literature. I also extend various equivalence relations for concurrent systems to higher dimensional automata. These include the history preserving bisimulation, which is the coarsest equivalence that fully respects branching time, causality and their interplay, as well as the ST-bisimulation, a branching time respecting equivalence that takes causality into account to the extent that it is expressible by actions overlapping in time. Through their embeddings in higher dimensional automata, it is now well-defined whether members of different models of concurrency are equivalent.
Original languageEnglish
Pages (from-to)5-34
Number of pages30
JournalElectronic Notes in Theoretical Computer Science
Volume128
Issue number2
Early online date4 Apr 2005
DOIs
Publication statusPublished - 14 Apr 2005
EventThe 11th International Workshop on Expressiveness in Concurrency, 2004 - London, United Kingdom
Duration: 30 Aug 200430 Aug 2004
Conference number: 11

Keywords / Materials (for Non-textual outputs)

  • Concurrency
  • expressiveness
  • causality
  • higher dimensional automata
  • Petri nets
  • event structures
  • history preserving bisimulation
  • ST-bisimulation

Fingerprint

Dive into the research topics of 'On the Expressiveness of Higher Dimensional Automata: (Extended Abstract)'. Together they form a unique fingerprint.

Cite this