Modelling concurrency with comtraces and generalized comtraces |
| |
Authors: | Ryszard Janicki Dai Tri Man Lê |
| |
Affiliation: | aDepartment of Computing and Software, McMaster University, Hamilton, ON, L8S 4K1 Canada;bDepartment of Computer Science, University of Toronto, Toronto, ON, M5S 3G4 Canada |
| |
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. |
| |
Keywords: | Generalized trace theory Trace monoid Step sequence Stratified partial order Stratified order structure Canonical representation |
本文献已被 ScienceDirect 等数据库收录! |
|