Published in Volume XXVIII, Issue 2, 2018, pages 237-267, doi: 10.7561/SACS.2018.2.237

Authors: R. Janicki, J. Kleijn, L. Mikulski


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.

Full Text (PDF)


[1] V. Diekert and G. Rozenberg (eds.). The Book of Traces. World Scienti c, Singapore, 1995. doi:10.1142/9789814261456.

[2] R. Janicki, J. Kleijn, M. Koutny, and Ł. Mikulski. Causal Structures for General Concurrent Behaviours. CEUR Workshop Proceedings, 1032, pages 193-205, 2013.

[3] R. Janicki, J. Kleijn, M. Koutny, and Ł. Mikulski. Characterising Concurrent Histories. Fundamenta Informaticae, 139(1), pages 21-42, 2015. doi:10.3233/FI-2015-1224.

[4] R. Janicki, J. Kleijn, M. Koutny, and Ł. Mikulski. Step Traces. Acta Informatica, 53(1), pages 35-65, 2016. doi:10.1007/s00236-015-0244-z.

[5] R. Janicki, J. Kleijn, M. Koutny, and Ł. Mikulski. Alphabets of Acyclic Invariant Structures. Fundamenta Informaticae, 154(1-4), pages 207-224, 2017. doi:10.3233/FI-2017-1562.

[6] R. Janicki, J. Kleijn, M. Koutny, and Ł. Mikulski. Invariant Structures and Dependence Relations. Fundamenta Informaticae, 155(1-2), pages 1-29, 2017. doi:10.3233/FI-2017-1574.

[7] R. Janicki, J. Kleijn, M. Koutny, and Ł. Mikulski. Classifying Invariant Structures of Step Traces. Journal of Computer and System Sciences, In Press, available online 2017. doi:10.1016/j.jcss.2017.05.002.

[8] R. Janicki and M. Koutny. Structure of Concurrency. Theoretical Computer Science 112(1), pages 5-52, 1993. doi:10.1016/0304-3975(93)90238-O.

[9] R. Janicki and M. Koutny. Semantics of Inhibitor Nets. Inf. Comput. 123(1), pages 1-16, 1995. doi:10.1006/inco.1995.1153.

[10] A. Laarman. Stubborn Transaction Reduction. In: A. Dutle, C.A. Muñoz, and A. Narkawicz, editors, NASA Formal Methods Symposium, Lecture Notes in Computer Science, vol. 10811, pages 290-298. Springer, Berlin, 2018. doi:10.1007/978-3-319-77935-5_20.

[11] D.T.M. Le. On Three Alternative Characterizations of Combined Traces. Fundamenta Informaticae 113(3), pages 265-293, 2011. doi:10.3233/FI-2011-609.

[12] A. W. Mazurkiewicz. Concurrent Program Schemes and Their Interpretations. DAIMI Rep. PB 78, Aarhus University (1977). doi: 10.7146/dpb.v6i78.7691.

[13] A. W. Mazurkiewicz. Trace Theory. In: W. Brauer, W. Reisig, and G. Rozenberg, editors, Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Lecture Notes in Computer Science, vol. 255, pages 278-324. Springer, Berlin, 1987. doi:10.1007/3-540-17906-2_30.

[14] A.W. Mazurkiewicz. Basic Notions of Trace Theory. In: J.W. de Bakker, W.P. de Roever, and G. Rozenberg, editors, REX Workshop Lecture Notes in Computer Science, vol. 354, pages 285-363. Springer, Berlin, 1988. doi:10.1007/BFb0013025.

[15] Ł. Mikulski. Algebraic Structure of Combined Traces. Logical Methods in Computer Science 9(3:8), 2013. doi:10.2168/LMCS-9(3:8)2013.

[16] A. Muscholl. Automated Synthesis of Distributed Controllers. In: Automata, Languages, and Programming – 42nd International Colloquium, ICALP, Lecture Notes in Computer Science 9135, pages 11-27, Springer, 2015. doi:10.1007/978-3-662-47666-6_2.

[17] A. Nagy and A. Arif. Trajectories and Traces on Non-Traditional Regular Tessellations of the Plane. In: Combinatorial Image Analysis, Lecture Notes in Computer Science 10256, pages 16-29, Springer, 2017. doi:10.1007/978-3-319-59108-7_2.

[18] L. Paulevé. Goal-Oriented Reduction of Automata Networks. In: International Conference on Computational Methods in Systems Biology, pages 252-272, 2016. doi:10.1007/978-3-319-45177-0_16.

[19] V.R. Pratt. Modeling Concurrency With Partial Orders. Int. J. Parallel Program 15(1), pages 33-71, 1986. doi:10.1007/BF01379149.

[20] E. Szpilrajn. Sur l’extension de l’ordre partiel. Fundam. Math. 16, 386-389, 1930. doi:10.4064/fm-16-1-386-389.


  title={A Precise Characterisation of Step Traces and Their Concurrent Histories},
  author={R. Janicki, J. Kleijn,  L. Mikulski},
  journal={Scientific Annals of Computer Science},
  organization={``A.I. Cuza'' University, Ia\c si, Rom\^ania},
  publisher={``A.I. Cuza'' University Press, Ia\c si}