×

zbMATH — the first resource for mathematics

Theory of traces. (English) Zbl 0652.68017
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

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
PDF BibTeX XML Cite
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, (), 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, 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, () · Zbl 0682.68040
[7] Bertoni, A.; Mauri, G.; Sabadini, N., Concurrency and commutativity, () · Zbl 0566.68043
[8] Bertoni, A.; Mauri, G.; Sabadini, N., Unambiguous regular trace languages, (), 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, () · Zbl 0682.68040
[10] Best, E.; Fernandez, C.; Plünnecke, H., Concurrent systems and processes, ()
[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, () · 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, 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, (), 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 San Francisco, CA · Zbl 0411.68039
[19] Ginsburg, S., The mathematical theory of context-free languages, (1966), McGraw-Hill New York · Zbl 0184.28401
[20] Györy, G.; Knuth, E.; Romai, L., Grammatical projections, ()
[21] Hack, M., Petri net languages, ()
[22] Harary, F., Graph theory, (1969), 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 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, A solvable program-schema equivalence problem, 301-306, (1971)
[27] Lallement, G., Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[28] Lauer, P.E.; Shields, M.W.; Best, E., Design and analysis of highly parallel and distributed systems, (), 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 Reading, MA · Zbl 0514.20045
[31] Mazurkiewicz, A., Concurrent program schemes and their interpretation, ()
[32] Mazurkiewicz, A., A calculus of execution traces for concurrent systems, (1983), Inst. of Computer Science, Polish Acad of Science Warsaw, Manuscript
[33] Mazurkiewicz, A., Traces, histories, graphs: instances of a process monoid, (), 115-133
[34] Mazurkiewicz, A., Semantics of concurrent systems: a modular fixed-point trace approach, (), 353-375 · Zbl 0576.68044
[35] Mehlhorn, K., Data structures and algorithms, 2, (1984), Springer Berlin
[36] Metivier, Y., On recognizable subsets of free partially commutative monoids, (), 254-264 · Zbl 0594.68061
[37] Ochmanski, E., Regular trace languages, ()
[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)
[40] Petri, C.A., Kommunikation mit automaten, ()
[41] Reisig, W., Petri nets, an introduction, (1985), 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 New York · Zbl 0193.32901
[44] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
[45] Szijarto, M., Trace languages and closure operations, () · 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, ()
[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, () · Zbl 0780.68082
[54] Bertoni, A.; Mauri, G.; Sabadini, N., 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, Context-free trace languages, 32-42, (1982)
[57] Bertoni, A.; Mauri, G.; Sabadini, N., Equivalence and membership problems for regular and context-free trace languages, () · Zbl 0682.68040
[58] Bertoni, A.; Mauri, G.; Sabadini, N., Concurrency and commutativity, () · Zbl 0566.68043
[59] Bertoni, A.; Mauri, G.; Sabadini, N., Unambiguous regular trace languages, (), 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, () · Zbl 0682.68040
[61] Best, E.; Fernandez, C.; Plünnecke, H., Concurrent systems and processes, ()
[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, () · 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)
[69] Duboc, C., Equations in free partially commutative monoids, Lecture notes in computer science, 210, 192-202, (1986)
[70] Flé, M.P.; Roucairol, G., 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, (), 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)
[77] Janicki, R., 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, ()
[79] Keller, R.M., 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, ()
[81] Knuth, E., 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, ()
[84] Mazurkiewicz, A., A calculus of execution traces for concurrent systems, (1983), 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, (), 254-264 · Zbl 0594.68061
[89] Ochmanski, E., Regular trace languages, ()
[90] Perrin, D., Words over a partially commutative alphabet, NATO ASI series F12, 329-340, (1985)
[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, () · 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, ()
[97] Viennot, G.X., Heaps of pieces 1: basic definitions and combinatorial lemmas, () · Zbl 0792.05012
[98] Zielonka, W., Proving assertions about parallel programs by means of traces, () · 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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.