Toggle Main Menu Toggle Search


Folded Hasse Diagrams of Combined Traces

Lookup NU author(s): Dr Lukasz Mikulski, Professor Maciej Koutny



To represent concurrent behaviours one can useconcepts originating from language theory, includingtraces and comtraces. Traces can expressnotions such as concurrency and causality, whereas comtracescan also capture weak causality and simultaneity.This paper is concerned with the development of efficient data structures and algorithmsfor manipulating comtraces. We introduce and investigate folded Hasse diagrams of comtraceswhich generalise Hasse diagrams defined for partial ordersand traces.We also develop an efficient on-linealgorithm for deriving Hasse diagrams from language theoretic representations ofcomtraces. Finally, we briefly discuss how folded Hasse diagramscould be used to implement efficiently some basic operations on comtraces.

Publication metadata

Author(s): Mikulski L, Koutny M

Publication type: Report

Series Title: School of Computing Science Technical Report Series

Year: 2012

Pages: 20

Source Publication Date: November 2012

Report Number: 1357

Institution: Newcastle University

Place Published: Newcastle upon Tyne