Algebraic Structure of Step Traces and Interval Traces

• Autorzy: Janicki, Ryszard , Mikulski, Łukasz
• Języki publikacji: EN

Abstrakty

EN

Traces and their extensions as comtraces, step traces and interval traces are quotient monoids over sequences or step sequences that play an important role in the formal analysis and verification of concurrent systems. Step traces are generalizations of comtraces and classical traces while interval traces are specialized traces that can deal with interval order semantics. The algebraic structures and their properties as projections, hidings, canonical forms and other invariants are very well established for traces and fairly well established for comtraces. For step traces and interval traces they are the main subject of this paper.

Słowa kluczowe

EN

interval traces; partially commutative monoids; step traces; traces

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2020
• Tom: Vol. 175, nr 1-4
• Strony: 253--280
• Opis fizyczny: Bibliogr. 31 poz., rys.

Twórcy

autor

Janicki, Ryszard

• Department of Computing and Software, McMaster University, Hamilton, ON, L8S 4K1, Canada,

autor

Mikulski, Łukasz

• Faculty of Mathematics and Computer Science, Nicolaus Copernicus University, Toruń, Chopina 12/18, Poland,
• Faculty of Mathematics, Informatics and Mechanics, University of Warsaw, Warszawa, Banacha 2, Poland

Bibliografia

• [1] Cartier P, Foata D. Problèmes Combinatoires de Commutation et Réarrangements, volume 85 of LNM. Springer, Berlin, 1969.
• [2] Mazurkiewicz A. Concurrent Program Schemes and Their Interpretations. Daimi report pb-78, Aarhus University, 1977. doi:https://doi.org/10.7146/dpb.v6i78.7691.
• [3] Diekert V, Métivier Y. Partial Commutation and Traces. In: Handbook of Formal Languages, volume 3, Springer, 1997 pp. 457-533. doi:doi.org/10.1007/978-3-642-59126-6_8.
• [4] Diekert V, Rozenberg G (eds.). The Book of Traces. World Scientific, Singapore, 1995. ISBN:9814501263, 9789814501262.
• [5] Janicki R, Koutny M. Structure of Concurrency. Theoretical Computer Science, 1993. 112(1):5-52. doi:10.1016/0304-3975(93)90238-O.
• [6] Janicki R, Koutny M. Semantics of Inhibitor Nets. Information and Computation, 1995. 123(1):1-16. doi:10.1006/inco.1995.1153.
• [7] Janicki R, Le DTM. Modelling concurrency with comtraces and generalized comtraces. Information and Computation, 2011. 209(11):1355-1389. doi:10.1016/j.ic.2011.08.001.
• [8] Janicki R, Kleijn J, Koutny M, Mikulski L. Step traces. Acta Informatica, 2016. 53(1):35-65. doi:10.1007/s00236-015-0244-z.
• [9] Paulevé L. Goal-oriented reduction of automata networks. In: International Conference on Computational Methods in Systems Biology. 2016 pp. 252-272. doi:10.1007/978-3-319-45177-0_16.
• [10] Nagy B, Akkeleş A. Trajectories and Traces on Non-traditional Regular Tessellations of the Plane. In: International Workshop on Combinatorial Image Analysis. 2017 pp. 16-29. doi:10.1007/978-3-319-59108-7_2.
• [11] Laarman A. Stubborn Transaction Reduction. In: NASA Formal Methods Symposium. 2018 pp. 280-298. doi:10.1007/978-3-319-77935-5_20.
• [12] Janicki R, Yin X. Modeling Concurrency with Interval Orders. Information and Computation, 2017. 253:78-108. doi:10.1016/j.ic.2016.12.009.
• [13] Mikulski Ł. Projection Representation of Mazurkiewicz Traces. Fundamenta Informaticae, 2008. 85:399-408.
• [14] Mikulski L. Algebraic Structure of Combined Traces. Logical Methods in Computer Science, 2013. 9(3):1-26. doi:10.2168/LMCS-9(3:8)2013.
• [15] Anisimov AV, Knuth DE. Inhomogeneous sorting. International Journal of Computer and Information Sciences, 1979. 8:255-260. doi:10.1007/BF00993053.
• [16] Fishburn PC. Interval Orders and Interval Graphs. John Wiley, New York, 1985. ISBN:0471812846 9780471812845.
• [17] Fishburn PC. Intransitive indifference with unequal indifference intervals. Journal of Mathematical Psychology, 1970. 7:144-109. doi:10.1016/0022-2496(70)90062-3.
• [18] Wiener N. A contribution to the theory of relative position. Proc. Camb. Philos. Soc., 1914. 17:441-449.
• [19] Nielsen M, Rozenberg G, Thiagarajan PS. Behavioural notions for elementary net systems. Distributed Computing, 1990. 4:45-57.
• [20] Rozenberg G, Engelfriet J. Elementary Net Systems. In: Petri Nets. 1996 pp. 12-121. doi:10.1007/3-540-65306-6_14.
• [21] Shields MW. Concurrent Machines. The Computer Journal, 1985. 28(5):449-465.
• [22] Janicki R, Lauer PE, Koutny M, Devillers R. Concurrent and Maximally Concurrent Evolution of Non-Sequential Systems. Theoretical Computer Science, 1986. 43:213-238.
• [23] Mikulski Ł, Piątkowski M, Smyczyński S. Algorithmics of Posets Generated by Words over Partially Commutative Alphabets. In: Holub J, Žd’árek J (eds.), Proceedings of the Prague Stringology Conference 2011. Czech Technical University in Prague, Czech Republic, 2011 pp. 209-219.
• [24] Vogler W. A generalization of traces. RAIRO Inform. Théor. Appl., 1991. 25(2):147-156. URL http://www.numdam.org/item/ITA_1991_25_2_147_0.
• [25] Janicki R, Kleijn J, Koutny M, Mikulski L. Classifying invariant structures of step traces. Journal of Computer and System Sciences, 2019. 104:297-322. doi:10.1016/j.jcss.2017.05.002.
• [26] Kleijn J, Koutny M. Mutex causality in processes and traces of general elementary nets. Fundamenta Informaticae, 2013. 122(1-2):119-146. doi:10.3233/FI-2013-785.
• [27] Mikulski L, Koutny M. Folded Hasse diagrams of combined traces. Inf. Process. Lett., 2014. 114(4):208-216. doi:10.1016/j.ipl.2013.11.009.
• [28] Janicki R, Yin X, Zubkova N. Modeling Interval Order Structures with Partially Commutative Monoids. In: Proc. 23rd Int. Conf. on Concurrency (CONCUR’2012), volume 7454 of Lecture Notes on Computer Science. Springer, 2012 pp. 425-39.
• [29] Glabbeek RJV, Vaandrager F. Petri net models for algebraic theories of concurrency. In: Proc. PARLE 1987, volume 259 of Lecture Notes on Computer Science. Springer, 1987 pp. 224-241. doi:10.1007/3-540-17945-3_13.
• [30] Vogler W. Partial order semantics and read arcs. Theoretical Computer Science, 2002. 286(1):33-63. doi:10.1016/S0304-3975(01)00234-1.
• [31] Janicki R, Koutny M. Operational Semantics, Interval Orders and Sequences of Antichains. Fundamenta Informaticae, 2019. 169:31-55. doi:10.3233/FI-2019-1838.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu
"Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja
sportu (2020).

Identyfikatory

DOI

10.3233/FI-2020-1956