A Precise Characterisation of Step Traces and Their Concurrent Histories

Scientific Annals of Computer Science

article

R. Janicki¹  J. Kleijn²  L. Mikulski³ 

[1] Department of Computing and Software, McMaster University;Leiden University;Faculty of Mathematics and Computer Science, Nicolaus Copernicus University

关键词: step alphabet;    trace of step sequences;    simultaneity;    serialisability;    interleaving;    classification;    invariant structure;   

DOI  :  10.7561/SACS.2018.2.237

来源: Alexandru Ioan Cuza University of Iasi

【 摘 要 】

Step traces are an extension of Mazurkiewicz traces where each equivalence class (trace) consists of sequences of steps instead of sequences of atomic actions. Relations between the actions of the system are defined statically, as parameters of a concurrent step alphabet. By allowing only some of the possible relationships between actions, subclasses of step alphabets can be derived in a natural way. Properties of these classes can then be investigated in terms of invariant structures, i.e., the relational structures that represent the causal invariants that underlie the corresponding step traces. In this paper, we refine an earlier classification of subclasses of step alphabets and add eight new subclasses to this hierarchy. We divide these eight classes into three families on basis of the absence of a specific behavioural relation and then characterise the corresponding invariant structures.

【 授权许可】

CC BY-ND