On the expressiveness of higher dimensional automata

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 (HDA), 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 HDA. 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 HDA, it is now well-defined whether members of different models of concurrency are equivalent.
Original languageEnglish
Pages (from-to)265-290
Number of pages26
JournalTheoretical Computer Science
Volume356
Issue number3
Early online date6 Mar 2006
DOIs
Publication statusPublished - 30 May 2006

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'. Together they form a unique fingerprint.

Cite this