Home
Scholarly Works
Modelling concurrency with comtraces and...
Journal article

Modelling concurrency with comtraces and generalized comtraces

Abstract

Comtraces (combined traces) are extensions of Mazurkiewicz traces that can model the “not later than” relationship. In this paper, we first introduce the novel notion of generalized comtraces, extensions of comtraces that can additionally model the “non-simultaneously” relationship. Then we study some basic algebraic properties and canonical representations of comtraces and generalized comtraces. Finally we analyze the relationship between generalized comtraces and generalized stratified order structures. The major technical contribution of this paper is a proof showing that generalized comtraces can be represented by generalized stratified order structures.

Authors

Janicki R; Lê DTM

Journal

Information and Computation, Vol. 209, No. 11, pp. 1355–1389

Publisher

Elsevier

Publication Date

November 1, 2011

DOI

10.1016/j.ic.2011.08.001

ISSN

0890-5401

Labels

Contact the Experts team