×

Folded Hasse diagrams of combined traces. (English) Zbl 1371.68195

Summary: To represent concurrent behaviours one can use concepts originating from language theory, including traces and comtraces. Traces can express notions such as concurrency and causality, whereas comtraces can also capture weak causality and simultaneity. This paper is concerned with the development of efficient data structures and algorithms for manipulating comtraces. We introduce and investigate folded Hasse diagrams of comtraces which generalise Hasse diagrams defined for partial orders and traces. We also develop an efficient on-line algorithm for deriving Hasse diagrams from language theoretic representations of comtraces. Finally, we briefly discuss how folded Hasse diagrams could be used to implement efficiently some basic operations on comtraces.

MSC:

68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)

Software:

LatDraw
PDFBibTeX XMLCite
Full Text: DOI Link

References:

[1] Cartier, Pierre; Foata, Dominique, Problèmes Combinatoires de Commutation et Réarrangements, Lect. Notes Math., vol. 85 (1969), Springer: Springer Berlin · Zbl 0186.30101
[2] Volker, Diekert; Métivier, Yves, Partial Commutation and Traces, Handbook of Formal Languages, vol. 3, 457-533 (1997), Springer
[3] Freese, Ralph, Automated lattice drawing, (Eklund, Peter W., ICFCA. ICFCA, Lect. Notes Comput. Sci., vol. 2961 (2004), Springer), 112-127 · Zbl 1198.06001
[4] Godefroid, Patrice, Partial-Order Methods for the Verification of Concurrent Systems - An Approach to the State-Explosion Problem, Lect. Notes Comput. Sci., vol. 1032 (1996), Springer · Zbl 1293.68005
[5] Janicki, Ryszard, Relational structures model of concurrency, Acta Inform., 45, 4, 279-320 (2008) · Zbl 1147.68054
[6] Janicki, Ryszard; Klein, Jetty; Koutny, Maciej, Quotient monoids and concurrent behaviours, (Martín-Vide, Carlos, Scientific Applications of Language Methods (2011), Imperial College Press: Imperial College Press London), 313-386, (Chapter 6) · Zbl 1236.68193
[7] Janicki, Ryszard; Koutny, Maciej, Semantics of inhibitor nets, Inf. Comput., 123, 1, 1-16 (1995) · Zbl 1096.68678
[8] Kahlon, Vineet; Wang, Chao; Gupta, Aarti, Monotonic partial order reduction: An optimal symbolic partial order reduction technique, (Bouajjani, Ahmed; Maler, Oded, CAV. CAV, Lect. Notes Comput. Sci., vol. 5643 (2009), Springer), 398-413 · Zbl 1242.68166
[9] Mazurkiewicz, Antoni, Concurrent program schemes and their interpretations (1977), Aarhus University, Daimi report pb-78
[10] Mikulski, Łukasz, Algebraic structure of combined traces, Log. Methods Comput. Sci., 9, 3:8, 1-26 (2013) · Zbl 1272.68316
[11] Mikulski, Lukasz; Koutny, Maciej, Hasse diagrams of combined traces, (Brandt, Jens; Heljanko, Keijo, ACSD (2012), IEEE), 92-101 · Zbl 1371.68195
[12] Vogler, Walter, A generalization of traces, ITA, 25, 147-156 (1991) · Zbl 0731.68083
[13] Vogt, Henri, Leçons sur la résolution algébrique des équations, Cornell University Library Historical Math. Monogr. (1895), Nony · JFM 26.0104.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.