The poset of infinitary traces. (English) Zbl 0787.68056
The concept of partially commutative monoid (or trace monoid) has been extended to include infinite traces. It is shown that, similarly to the finite case, infinite trace monoids are strongly related to partially ordered sets, domain and event structures. It is proven that the set of finite and infinite traces with the prefix order is a Scott domain and coherently completely prime algebraic.
Reviewer: R.Janicki (Hamilton / Ontario)
MSC:
| 68W35 | Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) |
| 06B35 | Continuous lattices and posets, applications |
Keywords:
partially commutative monoid; infinite traces; partially ordered sets; domain and event structures; Scott domainReferences:
| [1] | Aalbersberg, I. J.; Rozenberg, G., Theory of traces, Theoret. Comput. Sci., 60, 1-82 (1988) · Zbl 0652.68017 |
| [2] | Boasson, L.; Nivat, M., Adherence of languages, J. Comput. System Sci., 20, 285-309 (1980) · Zbl 0471.68052 |
| [3] | Bonizzoni, P.; Mauri, G.; Pighizzini, G., About infinite traces, (ASMICS Workshop on Partially Commutative Monoids (1989), Technische Universität München), Tech. Report TUM-I9002 · Zbl 0802.68085 |
| [4] | Boudol, G.; Castellani, I., Semantics of concurrency: partial orders and transition systems, (Tech. Report 550. Tech. Report 550, Proc. TAPSOFT’87, Vol. 249 (1987), INRIA, Sophia Antipolis: INRIA, Sophia Antipolis France), 123-137, Lecture Notes in Computer Science · Zbl 0614.68023 |
| [5] | Boudol, G.; Castellani, I., Permutation of transitions: an event structure semantics for CCS and SCCS, REX Workshop on Concurrency. REX Workshop on Concurrency, Lecture Notes in Computer Science, Vol. 354, 411-427 (1988) · Zbl 0683.68029 |
| [6] | Cartier, P.; Foata, D., Problèmes combinatoires de commutation et Lecture Notes in Mathematics, Vol. 85 (1969) · Zbl 0186.30101 |
| [7] | Castellani, I.; Franceschi, P.; Montanari, U., Labelled event structures: a model for observable concurrency, (Bjorner, D., Proc. I.F.I.P. TC2, Formal Description of Programming Concepts II. Proc. I.F.I.P. TC2, Formal Description of Programming Concepts II, Garmisch-Partenkirchen (1982), North-Holland: North-Holland Amsterdam), 383-400 · Zbl 0512.68025 |
| [8] | Diekert, V., Combinatorics on traces, Lecture Notes in Computer Science, 454 (1990) · Zbl 0717.68002 |
| [9] | V. Diekert, On the concatenation of infinite traces, in: Proc. STACS, 1991; V. Diekert, On the concatenation of infinite traces, in: Proc. STACS, 1991 · Zbl 0773.68057 |
| [10] | M. Droste, Concurrency, automata and domains, Tech. Report 1989, Univ. of Essen; to appear in ICALP ’90; M. Droste, Concurrency, automata and domains, Tech. Report 1989, Univ. of Essen; to appear in ICALP ’90 |
| [11] | Doboc, C., Commutations dans les monoïdes libres: un cadre théorique pour l’étude du parallélisme (1986), Thése Rouen Univ. France |
| [12] | Eilenberg, S., Automata, Languages, and Machines (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |
| [13] | Gastin, P., Un modèle asynchrone pour les systèmes distribués, Theoret. Comput. Sci., 74, 121-162 (1990) · Zbl 0701.68023 |
| [14] | Gastin, P., Infite traces, Proc. Spring School of Theoretical Computer Science on Semantics of Concurrency, 469, 277-308 (1990), Lecture Notes in Computer Science |
| [15] | Gastin, P., Recognizable and rational languages of finite and infinite traces, Proc. STACS ’91, 480, 89-104 (1991), Lecture Notes in Computer Science · Zbl 0773.68046 |
| [16] | Gastin, P.; Petit, A.; Zielonka, W., A Kleene theorem for infinite trace languages, (Proc. ICALP ’91 (1990), Université Paris 6: Université Paris 6 France), to appear in Lecture Notes in Computer Science, Tech. Report 90.93, LITP · Zbl 0766.68076 |
| [17] | P. Gastin and B. Rozoy, Infinitary partially commutative monoids, Tech. Report 89-24, 1989, LITP, Univ. of Paris 7, France.; P. Gastin and B. Rozoy, Infinitary partially commutative monoids, Tech. Report 89-24, 1989, LITP, Univ. of Paris 7, France. |
| [18] | P. Gastin and B. Rozoy, The PoSet of infinitary traces, Tech. Report 90-559, 1990, LRI, Univ. of Paris 11, France.; P. Gastin and B. Rozoy, The PoSet of infinitary traces, Tech. Report 90-559, 1990, LRI, Univ. of Paris 11, France. · Zbl 0787.68056 |
| [19] | Hoogeboom, H. J.; Rozenberg, G., Infinitary languages: basic theory and applications to concurrent systems, Lecture Notes in Computer Science, 224, 266-342 (1986) · Zbl 0607.68059 |
| [20] | M.Z. Kwiatkowska, On infinitary trace languages, Tech. Report 31, 1989, Univ. of Leicester, England.; M.Z. Kwiatkowska, On infinitary trace languages, Tech. Report 31, 1989, Univ. of Leicester, England. |
| [21] | Kwiatkowska, M. Z., A metric for traces, Inform. Process. Lett., 35, 129-135 (1990) · Zbl 0697.68071 |
| [22] | Lamport, L., Time, clocks and the ordering of events in a distributed system, Comm. ACM, 21, 558-565 (1978) · Zbl 0378.68027 |
| [23] | Mazurkiewicz, A., Concurrent program schemes and their interpretations, (DAIMI Report PB, 78 (1977), Aarhus Univ) |
| [24] | Mazurkiewicz, A., Trace theory, Paper no. 16, (Advanced Course on Petri Nets (1986), Bad Honnef) |
| [25] | Nielsen, M.; Plotkin, G.; Winskel, G., Petri nets, event structures and domains, Theoret. Comput. Sci., 13, 85-108 (1981) · Zbl 0452.68067 |
| [26] | Perrin, D., Recent results on automata and infinite words, Lecture Notes in Computer Science, 176, 134-148 (1984) · Zbl 0577.68076 |
| [27] | Perrin, D., Partial commutations, Proc. ICALP ’89. Proc. ICALP ’89, Lecture Notes in Computer Science, 372, 637-651 (1989) |
| [28] | Perrin, D.; Pin, J. E., Mots infinis, (Tech. Report (1990), LITP Paris 7 Univ. France) · Zbl 0542.68068 |
| [29] | Rozoy, B., Un Modèle du Paralléllisme: le Monoïde Distribué, Thèse d’état LIUC Caen Univ, France (1987) |
| [30] | Rozoy, B., On distributed languages and models for distributed computations, Proc. Spring School of Theoretical Computer Science on Semantics of Concurrency. Proc. Spring School of Theoretical Computer Science on Semantics of Concurrency, Lecture Notes in Computer Science, 469, 434-456 (1990) |
| [31] | Rozoy, B.; Thiagarajan, P. S., Trace monoids and event structures, Theoret. Comput. Sci., 91, 285-313 (1991) · Zbl 0756.68036 |
| [32] | Shields, M. W., Concurrent machines, Comput. J., 28, 449-465 (1985) · Zbl 0573.68026 |
| [33] | Starke, P. H., Traces and semi-words, Lecture Notes in Computer Science, 208, 332-349 (1985) · Zbl 0605.68048 |
| [34] | Viennot, G., Heaps of pieces, Montréal, Canada. Montréal, Canada, Proc. Col. de Combinatorie Énumérative, Combinatorial Theory and Applications (1985) |
| [35] | Winskel, G., Events in computation, (Ph.D. Thesis (1980), Edinburgh Univ. England) |
| [36] | Winskel, G., Categories of models for concurrency, Lecture Notes in Computer Science, 197 (1984) · Zbl 0567.68017 |
| [37] | Winskel, G., Event structures, Lecture Notes in Computer Science, 255, 325-392 (1987) · Zbl 0626.68022 |
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.
