On Three Alternative Characterizations of Combined Traces

• Autorzy: Le D.T.M.
• Języki publikacji: EN

Abstrakty

EN

The combined trace (i.e., comtrace) notion was introduced by Janicki and Koutny in 1995 as a generalization of the Mazurkiewicz trace notion. Comtraces are congruence classes of step sequences, where the congruence relation is defined from two relations simultaneity and serializability on events. They also showed that comtraces correspond to some class of labeled stratified order structures, but left open the question of what class of labeled stratified orders represents comtraces. In this work, we proposed a class of labeled stratified order structures that captures exactly the comtrace notion. Our main technical contributions are representation theorems showing that comtrace quotient monoid, combined dependency graph (Kleijn and Koutny 2008) and our labeled stratified order structure characterization are three different and yet equivalent ways to represent comtraces. This paper is a revised and expanded version of L�e (in Proceedings of PETRI NETS 2010, LNCS 6128, pp. 104-124).

Słowa kluczowe

EN

causality theory of concurrency; generalized trace theory; combined trace; step sequences; stratified order structure

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2011
• Tom: Vol. 113, nr 3/4
• Strony: 265--293
• Opis fizyczny: Bibliogr. 29 poz., wykr.

Twórcy

autor

Le D.T.M.

• Department of Computer Science University of Toronto Toronto, ON, M5S 3G4 Canada,

Bibliografia

• [1] Clarke, E., Grumberg, O., Peled, D.: Model Checking, MIT press, 2000.
• [2] Cormen, T., Leiserson, C., Rivest, R.: Introduction to Algorithms, MIT Press, 2001.
• [3] Diekert, V.: On the concatenation of infinite traces, Theoretical computer science, 113(1), 1993, 35-54.
• [4] Diekert, V., Gastin, P.: From local to global temporal logics overMazurkiewicz traces, Theoretical computer science, 356(1-2), 2006, 126-135.
• [5] Diekert, V., Gastin, P.: Pure future local temporal logics are expressively complete for Mazurkiewicz traces, Information and Computation, 204(11), 2006, 1597-1619.
• [6] Diekert, V., Horsch, M., Kufleitner, M.: On first-order fragments for Mazurkiewicz traces, Fundamenta Informaticae, 80(1), 2007, 1-29.
• [7] Diekert, V., Métivier, Y.: Partial commutation and traces, in: Handbook of formal languages: Beyond words (G. Rozenberg, A. Salomaa, Eds.), vol. 3, Springer Verlag, 1997, 457-533.
• [8] Diekert, V., Rozenberg, G.: The Book of Traces, World Scientific Publishing Co., Inc., River Edge, NJ, USA, 1995, ISBN 9810220588.
• [9] Esparza, J., Heljanko, K.: Unfoldings: a partial-order approach to model checking, Springer-Verlag New York Inc, 2008.
• [10] Gaifman, H., Pratt, V.: Partial ordermodels of concurrency and the computation of functions, in: Proceedings of Symposium on Logic in Computer Science, IEEE Computer Society, 1987, 72-85.
• [11] Gastin, P.: Infinite traces, in: Semantics of Systems of Concurrent Processes (I. Guessarian, Ed.), vol. 469 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 1990, 277-308.
• [12] Gastin, P., Kuske, D.: Uniform satisfiability in PSPACE for local temporal logics over Mazurkiewicz traces, Fundamenta Informaticae, 80(1), 2007, 169-197.
• [13] Janicki, R., Koutny, M.: Invariants and paradigms of concurrency theory, Future Generation Computer Systems, 8(4), 1992, 423-435.
• [14] Janicki, R., Koutny,M.: Structure of concurrency, Theoretical Computer Science, 112(1), 1993, 5-52.
• [15] Janicki, R., Koutny,M.: Semantics of inhibitor nets, Information and Computation, 123(1), 1995, 1-16.
• [16] Janicki, R., Koutny, M.: Fundamentals of modelling concurrency using discrete relational structures, Acta Informatica, 34, 1997, 367-388.
• [17] Janicki, R., Koutny, M.: On causality semantics of nets with priorities, Fundamenta Informaticae, 38(3), 1999, 223-255.
• [18] Janicki, R., Lê, D. T. M.: Modelling concurrency with comtraces and generalized comtraces, Information and Computation, 209(11), 2011, 1355 - 1389.
• [19] Juhás, G., Lorenz, R., Mauser, S.: Causal semantics of algebraic Petri nets distinguishing concurrency and synchronicity, Fundamenta Informaticae, 86(3), 2008, 255-298.
• [20] Juhás, G., Lorenz, R., Mauser, S.: Complete Process Semantics of Petri Nets, Fundamenta Informaticae, 87(3), 2008, 331-365.
• [21] Kleijn, H., Koutny, M.: Process semantics of general inhibitor nets, Information and Computation, 190(1), 2004, 18-69.
• [22] Kleijn, J., Koutny, M.: Formal Languages and Concurrent Behaviours, in: New Developments in Formal Languages and Applications (G. Bel-Enguix, M. Jimnez-Lpez, C. Martn-Vide, Eds.), vol. 113 of Studies in Computational Intelligence, Springer Berlin / Heidelberg, 2008, 125-182.
• [23] Lê, D. T. M.: Studies in Comtrace Monoids, Master Thesis, McMaster University, Hamilton, Canada, 2008.
• [24] Lê, D. T. M.: A Characterization of Combined Traces Using Labeled Stratified Order Structures, in: Applications and Theory of Petri Nets (J. Lilius, W. Penczek, Eds.), vol. 6128 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, 2010, 104-124.
• [25] Mazurkiewicz, A.: Concurrent program schemes and their interpretation, Technical Report DAIMI PB-78, Aarhus University - Computer Science Department, 1977.
• [26] Pratt, V.: Modeling concurrency with partial orders, International Journal of Parallel Programming, 15, 1986, 33-71.
• [27] Szpilrajn, E.: Sur l'extension de l'ordre partiel, Fundamenta Mathematica, 16, 1930, 386-389.
• [28] Thiagarajan, P., Walukiewicz, I.: An Expressively Complete Linear Time Temporal Logic for Mazurkiewicz Traces, Information and Computation, 179(2), 2002, 230-249.
• [29] Walukiewicz, I.: Local logics for traces, Journal of Automata, Languages and Combinatorics, 7, November 2001, 259-290.