×
Aalbersberg, Ijsbrand Jan; Rozenberg, Grzegorz

Theory of traces. (English) Zbl 0652.68017

Theor. Comput. Sci. 60, No. 1, 1-82 (1988).
The paper gives a good self contained introduction to the theory of traces, a theory which provides a mathematical description of the behaviour of concurrent systems. Its aim is to reconcile the sequential nature of observations of the system behaviour on the one hand and the nonsequential nature of causality between the actions of the system on the other hand.
The paper presents a major portion of the theory of traces in a uniform way, holding a good balance between two possible sights of the subject (as partial commutative monoids resp. as labelled partial orders/\(labelled\) acyclic graphs). Furthermore a second part presents applications to Petri nets (condition/\(event\) systems).
Reviewer: H.Müller

Cited in 2 Reviews
Cited in 71 Documents

MSC:

68Q60 Specification and verification (program logics, model checking, etc.)
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
68Q65 Abstract data types; algebraic specification

Keywords:

dependency graph; synchronization; traces; concurrent systems; Petri nets; condition/event systems
Cite Review PDF
Full Text: DOI

References:

[1] Aalbersberg, IJ. J.; Rozenberg, G., Traces, dependency graphs and DNLC grammars, Discr. Appl. Math., 11, 299-306 (1985) · Zbl 0601.68045
[2] Aalbersberg, IJ. J.; Rozenberg, G., Trace languages defined by context-free string languages (1985), Dept. of Computer Science, Univ. of Leiden, Manuscript
[3] Aalbersberg, IJ. J.; Welzl, E., Trace languages defined by regular string languages, RAIRO Inform. Théor. et Applic., 20, 103-119 (1986) · Zbl 0612.68071
[4] Bertoni, A.; Brambilla, M.; Mauri, G.; Sabadini, N., An application of the theory of free partially commutative monoids: asymptotic densities of trace languages, (Lecture Notes in Computer Science, 118 (1981), Springer: Springer Berlin), 205-215 · Zbl 0468.68081
[5] Bertoni, A.; Mauri, G.; Sabadini, N., Proc. 2nd World Conf. on Mathematics at the Service of Men, Las Palmas. Proc. 2nd World Conf. on Mathematics at the Service of Men, Las Palmas, A hierarchy of regular trace languages and some combinatorial applications, 146-153 (1982) · Zbl 0512.68056
[6] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular and context-free trace languages, (Intern. Rept. (1982), Inst. Cibern., Univ. of Milan) · Zbl 0682.68040
[7] Bertoni, A.; Mauri, G.; Sabadini, N., Concurrency and commutativity, (Intern. Rept.. Intern. Rept., presented at 3rd European Workshop on Applications and Theory of Petri Nets, Varenna, 1982 (1982), Inst. Cibern., Univ. of Milan) · Zbl 0566.68043
[8] Bertoni, A.; Mauri, G.; Sabadini, N., Unambiguous regular trace languages, (Colloquia Mathematica Societatis János Bolyai, 42 (1985), North-Holland: North-Holland Amsterdam), 113-123 · Zbl 0627.68060
[9] Bertoni, A.; Mauri, G.; Sabadini, N., Representations of prefixes of a trace and membership problem for context-free trace languages, (Intern. Rept. (1985), Inst. Cibern., Univ. of Milan) · Zbl 0682.68040
[10] Best, E.; Fernandez, C.; Plünnecke, H., Concurrent systems and processes, (GMD Studien 104 (1985), Gesellschaft für Mathematik und Datenverarbeitung: Gesellschaft für Mathematik und Datenverarbeitung Sankt Augustin)
[11] Bogart, K. P., Decomposing partial orderings into chains, J. Combin. Theor., 9, 97-99 (1970) · Zbl 0204.33002
[12] Cartier, P.; Foata, D., Problèmes Combinatories de Commutation et Rearrangements, (Lecture Notes in Mathematics, 85 (1969), Springer: Springer Berlin) · Zbl 0186.30101
[13] Cori, R.; Perrin, D., Automates et commutations partielles, RAIRO Inform. Théor., 19, 21-32 (1985) · Zbl 0601.68055
[14] Flé, M. P.; Roucairol, G., Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, Ottawa. Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, Ottawa, On serializability of iterated transactions, 194-200 (1982) · Zbl 0492.68019
[15] Flé, M. P.; Roucairol, G., Multiserialization of iterated transactions, Inform. Process. Lett., 18, 243-247 (1984) · Zbl 0544.68069
[16] Flé, M. P.; Roucairol, G., Fair serializability of iterated transactions using FIFO-nets, (Lecture Notes in Computer Science, 188 (1985), Springer: Springer Berlin), 154-168 · Zbl 0562.68018
[17] Fliess, M., Matrices de Hankel, J. Math. Pures et Appl., 53, 197-224 (1974) · Zbl 0315.94051
[18] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), Freeman: Freeman San Francisco, CA · Zbl 0411.68039
[19] Ginsburg, S., The Mathematical Theory of Context-Free Languages (1966), McGraw-Hill: McGraw-Hill New York · Zbl 0184.28401
[20] Györy, G.; Knuth, E.; Romai, L., Grammatical projections, (Working paper of Comput. and Autom. Institute (1979), Hungarian Academy of Sciences)
[21] Hack, M., Petri net languages, (Comput. Struct. Group Memo 124, Project MAC (1975), MIT: MIT Cambridge, MA)
[22] Harary, F., Graph Theory (1969), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0797.05064
[23] Hoare, C. A.R., Communicating sequential processes, Comm. ACM, 21, 666-677 (1978) · Zbl 0383.68028
[24] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[25] Janssens, D.; Rozenberg, G., A characterization of context-free string languages by directed node-label controlled graph grammars, Acta Inform., 16, 63-85 (1981) · Zbl 0464.68077
[26] Keller, R. M., Proc. 5th. Ann. Princeton Conf. on Information Sciences and Systems, Princeton, NJ. Proc. 5th. Ann. Princeton Conf. on Information Sciences and Systems, Princeton, NJ, A solvable program-schema equivalence problem, 301-306 (1971)
[27] Lallement, G., Semigroups and Combinatorial Applications (1979), Wiley: Wiley New York · Zbl 0421.20025
[28] Lauer, P. E.; Shields, M. W.; Best, E., Design and analysis of highly parallel and distributed systems, (Lecture Notes in Computer Science, 86 (1979), Springer: Springer Berlin), 451-503 · Zbl 0452.68037
[29] Levi, F. W., On semigroups, Bull. Calcutta Math. Soc., 36, 141-146 (1944) · Zbl 0061.02405
[30] Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[31] Mazurkiewicz, A., Concurrent program schemes and their interpretation, (DAIMI Rept. PB-78 (1977), Aarhus Univ.,: Aarhus Univ., Aarhus)
[32] Mazurkiewicz, A., A calculus of execution traces for concurrent systems (1983), Inst. of Computer Science, Polish Acad of Science: Inst. of Computer Science, Polish Acad of Science Warsaw, Manuscript
[33] Mazurkiewicz, A., Traces, histories, graphs: instances of a process monoid, (Lecture Notes in Computer Science, 176 (1984), Springer: Springer Berlin), 115-133 · Zbl 0577.68061
[34] Mazurkiewicz, A., Semantics of concurrent systems: a modular fixed-point trace approach, (Lecture Notes in Computer Science, 188 (1985), Springer: Springer Berlin), 353-375 · Zbl 0576.68044
[35] Mehlhorn, K., Data Structures and Algorithms, 2 (1984), Springer: Springer Berlin · Zbl 0556.68002
[36] Metivier, Y., On recognizable subsets of free partially commutative monoids, (Lecture Notes in Computer Science, 226 (1986), Springer: Springer Berlin), 254-264 · Zbl 0594.68061
[37] Ochmanski, E., Regular trace languages, (Ph.D. Thesis (1985), Inst. of Computer Science, Polish Acad. of Science: Inst. of Computer Science, Polish Acad. of Science Warsaw)
[38] Pawlak, Z., Rough sets, Internat. J. Comput. Inform. Sci., 11, 341-356 (1982) · Zbl 0501.68053
[39] Perrin, D., Words over a partially commutative alphabet, NATO ASI Series F12, 329-340 (1985) · Zbl 0602.68070
[40] Petri, C. A., Kommunikation mit Automaten, (Schrift Nr. 2 (1962), Institut fur Instrumentelle Mathematik)
[41] Reisig, W., Petri Nets, an Introduction (1985), Springer: Springer Berlin · Zbl 0555.68033
[42] Sakarovitch, J., On regular trace languages, Theoret. Comput. Sci., 52, 59-75 (1987) · Zbl 0634.68076
[43] Salomaa, A., Theory of Automata (1969), Pergamon: Pergamon New York · Zbl 0193.32901
[44] Salomaa, A., Formal Languages (1973), Academic Press: Academic Press New York · Zbl 0262.68025
[45] Szijarto, M., Trace languages and closure operations, (Tech. Rept. (1979), Dept. of Numerical and Computational Mathematics, L. Eötvos Univ.,: Dept. of Numerical and Computational Mathematics, L. Eötvos Univ., Budapest) · Zbl 0472.68033
[46] Szijarto, M., A classification and closure properties of languages for describing concurrent system behaviours, Fund. Inform., 4, 531-549 (1981) · Zbl 0486.68074
[47] Tarlecki, A., Notes on the implementability of formal languages by concurrent systems, (ICS PAS Rept. 481 (1982), Institute of Computer Science, Polish Academy of Sciences: Institute of Computer Science, Polish Academy of Sciences Warsaw)
[48] Tarski, A., A lattice-theoretical fixpoint theorem and its applications, Pacific. J. Math., 5, 285-309 (1955) · Zbl 0064.26004
[49] Aalbersberg, IJ. J.; Rozenberg, G., Traces, dependency graphs and DNLC grammars, Discr. Appl. Math., 11, 299-306 (1985) · Zbl 0601.68045
[50] Aalbersberg, IJ. J.; Rozenberg, G., Trace languages defined by context-free string languages (1985), Dept. of Computer Science, University of Leiden, Manuscript
[51] Aalbersberg, IJ. J.; Welzl, E., Trace languages defined by regular string languages, RAIRO Inform. Théor. Applic., 20, 103-119 (1986) · Zbl 0612.68071
[52] Bertoni, A.; Brambilla, M.; Mauri, G.; Sabadini, N., An application of the theory of free partially commutative monoids: asymptotic densities of trace languages, Lecture Notes in Computer Science, 118, 205-215 (1981) · Zbl 0468.68081
[53] Bertoni, A.; Goldwurm, M., Average analysis of an algorithm for a membership problem on trace languages, (Intern. Rept. (1986), Dept. of Information Science, Univ. of Milan) · Zbl 0780.68082
[54] Bertoni, A.; Mauri, G.; Sabadini, N., Proc. 2nd. World Conf. on Mathematics at the Service of Men, Las Palmas. Proc. 2nd. World Conf. on Mathematics at the Service of Men, Las Palmas, A hierarchy of regular trace languages and some combinatorial applications, 146-153 (1982) · Zbl 0512.68056
[55] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular trace languages, Lecture Notes in Computer Science, 140, 61-71 (1982) · Zbl 0486.68079
[56] Bertoni, A.; Mauri, G.; Sabadini, N., Proc. 7th. CAAP, Lille. Proc. 7th. CAAP, Lille, Context-free trace languages, 32-42 (1982) · Zbl 0548.68072
[57] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular and context-free trace languages, (Intern. Rept. (1982), Institute Cibernetica, Univ. of Milan) · Zbl 0682.68040
[58] Bertoni, A.; Mauri, G.; Sabadini, N., Concurrency and commutativity, (Intern. Rept.. Intern. Rept., presented at 3rd European Workshop on Applications and Theory of Petri Nets, Varenna, 1982 (1982), Institute Cibernetica, Univ. of Milan) · Zbl 0566.68043
[59] Bertoni, A.; Mauri, G.; Sabadini, N., Unambiguous regular trace languages, (Colloquia Mathematica Societas Janos Bolyai, 42 (1985), North-Holland: North-Holland Amsterdam), 113-123 · Zbl 0627.68060
[60] Bertoni, A.; Mauri, G.; Sabadini, N., Representations of prefixes of a trace and membership problem for context-free trace languages, (Intern. Rept. (1985), Institute Cibernetica, Univ. of Milan) · Zbl 0682.68040
[61] Best, E.; Fernandez, C.; Plünnecke, H., Concurrent systems and processes, (GMD Studien 104 (1985), Gesellschaft für Mathematik und Datenverarbeitung: Gesellschaft für Mathematik und Datenverarbeitung Sankt Augustin)
[62] Carpi, A.; De Luca, A., Square-free words on partially commutative free monoids, Inform. Process. Lett., 22, 125-132 (1986) · Zbl 0593.20065
[63] Cartier, P.; Foata, D., Problèmes Combinatoires de Commutation et Réarrangements, Lecture Notes in Mathematics, 85 (1969) · Zbl 0186.30101
[64] Clerbout, M.; Latteux, M., Partial commutations and faithful rational transductions, Theoret. Comput. Sci., 34, 241-254 (1984) · Zbl 0548.68073
[65] Clerbout, M.; Latteux, M., Semi-commutations, (Tech. Rept. IT-63-84 (1984), Equipe Lilloise d’Informatique Théorique, Univ. de Lille I: Equipe Lilloise d’Informatique Théorique, Univ. de Lille I Villeneuve d’Ascq) · Zbl 0629.68078
[66] Cori, R.; Metivier, Y., Recognizable subsets of some partially abelian monoids, Theoret. Comput. Sci., 35, 179-189 (1985) · Zbl 0559.20040
[67] Cori, R.; Perrin, D., Automates et commutations partielles, RAIRO Inform. Théor., 19, 21-32 (1985) · Zbl 0601.68055
[68] Duboo, C., Some properties of commutation in free partially commutative monoids, Inform. Process. Lett., 20, 1-4 (1985) · Zbl 0582.20035
[69] Duboc, C., Equations in free partially commutative monoids, Lecture Notes in Computer Science, 210, 192-202 (1986) · Zbl 0605.68069
[70] Flé, M. P.; Roucairol, G., Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, Ottawa. Proc. ACM SIGACT-SIGOPS Symp. on Principles of Distributed Computing, Ottawa, On serializability of iterated transactions, 194-200 (1982) · Zbl 0492.68019
[71] Flé, M. P.; Roucairol, G., Multiserialization of iterated transactions, Inform. Process. Lett., 18, 243-247 (1984) · Zbl 0544.68069
[72] Flé, M. P.; Roucairol, G., Fair serializability of iterated transactions using FIFO-nets, Lecture Notes in Computer Science, 188, 154-168 (1985) · Zbl 0562.68018
[73] Flé, M. P.; Roucairol, G., Maximal serializability of iterated transactions, Theoret. Comput. Sci., 38, 1-16 (1985) · Zbl 0572.68082
[74] Foata, D., Rearrangements of words, (Lothaire, M., Combinatorics on Words (1983), Addison Wesley: Addison Wesley Reading, MA), Chapter 10. · Zbl 0186.30101
[75] Grabowski, J., On partial languages, Fund. Inform., 4, 427-498 (1981) · Zbl 0468.68088
[76] Janicki, R., Synthesis of concurrent schemes, Lecture Notes in Computer Science, 64, 298-307 (1978) · Zbl 0382.68023
[77] Janicki, R., Proc. 2nd Internat. Conf. on Distributed Computing Systems, Paris. Proc. 2nd Internat. Conf. on Distributed Computing Systems, Paris, On the design of concurrent systems, 455-466 (1981)
[78] Janicki, R., Trace semantics for communicating sequential processes, (Tech. Rept. R-85-12 (1985), Institute for Elektr. Syst., Univ. Aalborg: Institute for Elektr. Syst., Univ. Aalborg Aalborg)
[79] Keller, R. M., Proc. 5th. Ann. Princeton Conf. on Information Sciences and Systems, Princeton. Proc. 5th. Ann. Princeton Conf. on Information Sciences and Systems, Princeton, A solvable program-schema equivalence problem, 301-306 (1971)
[80] Knuth, E., Petri nets and regular trace languages, (Tech. Rept. ASM/47 (1978), Computing Laboratory, Univ. Newcastle upon Tyne)
[81] Knuth, E., Proc. 1st. Europ. Conf. on Parallel and Distributed Processing, Toulouse. Proc. 1st. Europ. Conf. on Parallel and Distributed Processing, Toulouse, Petri nets and trace languages, 51-56 (1979)
[82] Knuth, E.; Györy, G., Paths and traces, Comput. Linguis. Comput. Languages, 13, 31-42 (1979) · Zbl 0435.68048
[83] Mazurkiewicz, A., Concurrent program schemes and their interpretations, (DAIMI Rept. PB-78 (1977), Aarhus Univ.,: Aarhus Univ., Aarhus)
[84] Mazurkiewicz, A., A calculus of execution traces for concurrent systems (1983), Institute of Computer Science, Polish Academy of Sciences: Institute of Computer Science, Polish Academy of Sciences Warsaw, Manuscript
[85] Mazurkiewicz, A., Traces, histories, graphs: instances of a process monoid, Lecture Notes in Computer Science, 176, 115-133 (1984) · Zbl 0577.68061
[86] Mazurkiewicz, A., Semantics of concurrent systems: a modular fixed-point trace approach, Lecture Notes in Computer Science, 188, 353-375 (1985) · Zbl 0576.68044
[87] Metivier, Y., Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif, RAIRO Inform. Théor. et Applic., 20, 121-127 (1986) · Zbl 0599.20107
[88] Metivier, Y., On recognizable subsets of free partially commutative monoids, (Lecture Notes in Computer Science, 226 (1986), Springer: Springer Berlin), 254-264 · Zbl 0594.68061
[89] Ochmanski, E., Regular trace languages, (Ph.D. Thesis (1985), Institute of Computer Science, Polish Academy of Sciences: Institute of Computer Science, Polish Academy of Sciences Warsaw)
[90] Perrin, D., Words over a partially commutative alphabet, NATO ASI Series F12, 329-340 (1985) · Zbl 0602.68070
[91] Rytter, W., Some properties of trace languages, Fund. Inform., 7, 117-127 (1984) · Zbl 0546.68064
[92] Sakarovitch, J., On regular trace languages, Theoret. Comput. Sci., 52, 59-75 (1987) · Zbl 0634.68076
[93] Starke, P. H., Traces and semiwords, Lecture Notes in Computer Science, 208, 332-349 (1985) · Zbl 0605.68048
[94] Szijarto, M., Trace languages and closure operations, (Tech. Rept. (1979), Dept. of Numerical and Computational Mathematics, L. Eötvos Univ.,: Dept. of Numerical and Computational Mathematics, L. Eötvos Univ., Budapest) · Zbl 0472.68033
[95] Szijarto, M., A classification and closure properties of languages for describing concurrent system behaviors, Fund. Inform., 4, 531-549 (1981) · Zbl 0486.68074
[96] Tarlecki, A., Notes on the implementability of formal languages by concurrent systems, (ICS PAS Rept. 481 (1982), Institute of Computer Science, Polish Academy of Sciences: Institute of Computer Science, Polish Academy of Sciences Warsawa)
[97] Viennot, G. X., Heaps of pieces 1: basic definitions and combinatorial lemmas, (Tech. Rept. I-8614 (1986), U.E.R. de Mathématiques et d’Informatique, Univ. de Bordeaux 1: U.E.R. de Mathématiques et d’Informatique, Univ. de Bordeaux 1 Bordeaux) · Zbl 0792.05012
[98] Zielonka, W., Proving assertions about parallel programs by means of traces, (ICS PAS Rept. 424 (1980), Institute of Computer Science, Polish Academy of Sciences: Institute of Computer Science, Polish Academy of Sciences Warsawa) · Zbl 0506.68021
[99] Zielonka, W., Notes on finite asynchronous automata and trace languages, RAIRO Inform. Théor. et Applic., 21, 99-135 (1987) · Zbl 0623.68055
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.