×
Gastin, Paul; Petit, Antoine; Zielonka, Wiesław

An extension of Kleene’s and Ochmański’s theorems to infinite traces. (English) Zbl 0795.68116

Theor. Comput. Sci. 125, No. 2, 167-204 (1994).
Summary: As was noted by Mazurkiewicz, traces constitute a convenient tool for describing finite behaviour of concurrent systems. Extending in a natural way Mazurkiewicz’s original definition, infinite traces have recently been introduced enabling one to deal with infinite behaviour of nonterminating concurrent systems. In this paper we examine the basic families of recognizable sets and of rational sets of infinite traces. The seminal Kleene characterization of recognizable subsets of the free monoid and its subsequent extensions to infinite words due to Büchi and to finite traces due to Ochmański are the cornerstones of the corresponding theories. The main result of our paper is an extension of these characterizations to the domain of infinite traces. Using recognizing and weakly recognizing morphisms, as well as a generalization of the Schützenberger product of monoids, we prove various closure properties of recognizable trace languages. Moreover, we establish normal-form representations for recognizable and rational sets of infinite traces.

Cited in 4 Documents

MSC:

68Q45 Formal languages and automata
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
20M35 Semigroups in automata theory, linguistics, etc.
68Q55 Semantics in the theory of computing

Keywords:

finite behaviour of concurrent systems; infinite traces; infinite behaviour of nonterminating concurrent systems; Schützenberger product of monoids; closure properties; recognizable trace languages; normal-form representations; rational sets of infinite traces
Cite Review PDF
Full Text: DOI

References:

[1] Aalbersberg, I. J.; Rozenberg, G., Theory of traces, Theoret. Comput. Sci., 60, 1-82 (1988) · Zbl 0652.68017
[2] Arnold, A., A syntactic congruence for rational ω-languages, Theoret. Comput. Sci., 39, 333-335 (1985) · Zbl 0578.68057
[3] Best, E.; Devillers, R., Sequential and concurrent behaviour in Petri net theory, Theoret. Comput. Sci., 55, 87-136 (1987) · Zbl 0669.68043
[4] Bonizzoni, P.; Mauri, G.; Pighizzini, G., About infinite traces, (Proc. ASMICS workshop on Free Partially Commutative Monoids. Proc. ASMICS workshop on Free Partially Commutative Monoids, Tech. Report, TUM-I9002 (1990), Technical University of Munich: Technical University of Munich Germany), 1-10
[5] Büchi, R., On a decision method in restricted second order arithmetic, (Proc. Internat. Congr. on Logic, Methodology and Philosophy (1962), Stanford University Press: Stanford University Press Stanford), 1-11 · Zbl 0147.25103
[6] Cartier, P.; Foata, D., Problèmes combinatoires de commutation et réarrangements, (Lecture Notes in Mathematics, Vol. 85 (1969), Springer: Springer Berlin) · Zbl 0186.30101
[7] Clerbout, M.; Latteux, M., Semi-commutations, Inform. and Comput., 73, 59-74 (1987) · Zbl 0629.68078
[8] Cori, R.; Métivier, Y.; Zielonka, W., Asynchronous mappings and asynchronous cellular automata, (Tech. Report LaBRI 89-97 (1990), Université Bordeaux I: Université Bordeaux I France), Inform. and Comput., to appear · Zbl 0785.68068
[9] Cori, R.; Perrin, D., Automates et commutations partielles, RAIRO — Inform. Théorique Appl., 19, 21-32 (1985) · Zbl 0601.68055
[10] Diekert, V., Combinatorics on Traces, (Lecture Notes in Computer Science, Vol. 454 (1990), Springer: Springer Berlin) · Zbl 0717.68002
[11] Diekert, V., On the concatenation of infinite traces, (Proc. 8th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’91). Proc. 8th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’91), Lecture Notes in Computer Science, Vol. 480 (1991), Springer: Springer Berlin), 105-117 · Zbl 0773.68057
[12] Diekert, V.; Gastin, P.; Petit, A., Recognizable complex trace languages, (Proc. 16th Symp. on Mathematical Foundations of Computer Science (MFCS’91). Proc. 16th Symp. on Mathematical Foundations of Computer Science (MFCS’91), Lecture Notes in Computer Science, Vol. 520 (1991), Springer: Springer Berlin), 131-140 · Zbl 0777.68057
[13] Diekert, V.; Muscholl, A., Deterministic asynchronous automata for infinite traces, (Proc. 10th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’93). Proc. 10th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’93), Lecture Notes in Computer Science, Vol. 665 (1992), Springer: Springer Berlin), 617-628 · Zbl 0799.68140
[14] Ebinger, W., On logical definability of ω-trace languages, (Proc. ASMICS Workshop on Infinite Traces (1992), Univ. of Stuttgart: Univ. of Stuttgart Germany), Tech. Report
[15] Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045
[16] Flé, M. P.; Roucairol, G., Maximal serializability of iterated transactions, Theoret. Comput. Sci., 38, 1-16 (1985) · Zbl 0572.68082
[17] Fliess, M., Matrices de Hankel, J. Math. Pures Appl., 53, 197-224 (1974) · Zbl 0315.94051
[18] Gastin, P., Un modèle distribué, (Ph.D. Thesis (1987), Université Paris 7: Université Paris 7 France), LITP
[19] Gastin, P., Infinite traces, (Proc. Spring School of Theoretical Computer Science on Semantics of Systems of Concurrent Processes. Proc. Spring School of Theoretical Computer Science on Semantics of Systems of Concurrent Processes, Lecture Notes in Computer Science, Vol. 469 (1990), Springer: Springer Berlin), 277-308
[20] Gastin, P., Recognizable and rational languages of finite and infinite traces, (Proc. 8th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’91). Proc. 8th Ann. Symp. on Theoretical Aspects of Computer Science (STACS’91), Lecture Notes in Computer Science, Vol. 480 (1991), Springer: Springer Berlin), 89-104 · Zbl 0773.68046
[21] Gastin, P.; Petit, A., Asynchronous cellular automata for infinite traces, (Proc. 19th Internat. Coll. on Automata, Languages and Programming (ICALP ’92). Proc. 19th Internat. Coll. on Automata, Languages and Programming (ICALP ’92), Lecture Notes in Computer Science, Vol. 623 (1992), Springer: Springer Berlin), 583-594 · Zbl 1425.68281
[22] Gastin, P.; Petit, A.; Zielonka, W., A Kleene theorem for infinite trace languages, (Proc. 18th Internat. Coll. on Automata, Languages and Programming (ICALP ’91). Proc. 18th Internat. Coll. on Automata, Languages and Programming (ICALP ’91), Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlin), 254-266 · Zbl 0766.68076
[23] Gastin, P.; Rozoy, B., The poset of infinitary traces, Theoret. Comput. Sci., 120, 101-121 (1993) · Zbl 0787.68056
[24] Graham, R. L.; Rothschild, B. L.; Spencer, J. H., Ramsey Theory (1980), Wiley: Wiley New York · Zbl 0455.05002
[25] Hashigushi, K., Recognizable closures and submonoids of free partially commutative monoids, Theoret. Comput. Sci., 86, 233-241 (1991) · Zbl 0737.68051
[26] Kwiatkowska, M., Fairness for non-interleaving concurrency, (Ph.D. Thesis (1989), University of Leicester: University of Leicester England) · Zbl 0744.68048
[27] Kwiatkowska, M., On the domain of traces and sequential composition, (Proc. 16th Coll. on Trees in Algebra and Programming (CAAP ’91). Proc. 16th Coll. on Trees in Algebra and Programming (CAAP ’91), Lecture Notes in Computer Science, Vol. 493 (1991), Springer: Springer Berlin), 42-56 · Zbl 0967.68527
[28] Mazurkiewicz, A., Concurrent program schemes and their interpretations, (Tech. Report DAIMI PB 78 (1977), Aarhus University)
[29] Mazurkiewicz, A., Traces, histories, graphs: instances of a process monoid, (Proc. 11th Symp. on Mathematical Foundations of Computer Science (MFCS ’84). Proc. 11th Symp. on Mathematical Foundations of Computer Science (MFCS ’84), Lecture Notes in Computer Science, Vol. 176 (1984), Springer: Springer Berlin), 115-133 · Zbl 0577.68061
[30] Mazurkiewicz, A., Trace theory, (Advances in Petri Nets ’86. Advances in Petri Nets ’86, Lecture Notes in Computer Science, Vol. 255 (1987), Springer: Springer Berlin), 279-324 · Zbl 0633.68051
[31] Métivier, Y., On recognizable subsets of free partially commutative monoids, Theoret. Comput. Sci., 58, 201-208 (1988) · Zbl 0658.20031
[32] Métivier, Y.; Rozoy, B., On the star operation in free partially commutative monoids, Internat. J. Foundations Comput. Sci., 2, 3, 257-265 (1991) · Zbl 0801.20041
[33] Ochmański, E., Regular behaviour of concurrent systems, Bull. European Assoc. Theoret. Comput. Sci. (EATCS), 27, 56-67 (1985)
[34] Ochmański, E., Notes on a star mystery, Bull. European Assoc. Theoret. Comput. Sci. (EATCS), 40, 252-257 (1990) · Zbl 0744.68080
[35] Perrin, D., An introduction to finite automata on infinite words, (Proc. Spring School of Theoretical Computer Science on Automata on Infinite Words. Proc. Spring School of Theoretical Computer Science on Automata on Infinite Words, Lecture Notes in Computer Science, Vol. 192 (1984), Springer: Springer Berlin), 2-17 · Zbl 0604.68091
[36] Perrin, D., Partial commutations, (Proc. 16th Internat. Coll. on Automata, Languages and Programming (ICALP ’89). Proc. 16th Internat. Coll. on Automata, Languages and Programming (ICALP ’89), Lecture Notes in Computer Science, Vol. 372 (1989), Springer: Springer Berlin), 637-651
[37] Perrin, D.; Pin, J. E., Mots infinis, (Tech. Report, LITP 91.06 (1991), Université Paris 7: Université Paris 7 France) · Zbl 0542.68068
[38] Schützenberger, M. P., A propos des relations rationnelles fonctionnelles, (Automata, Languages and Programming (1972), North-Holland: North-Holland Amsterdam), 103-114 · Zbl 0283.94018
[39] Zielonka, W., Notes on finite asynchronous automata, RAIRO Inform. Théorique Appl., 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.