Asynchronous automata versus asynchronous cellular automata. (English) Zbl 0826.68081
The investigations of A. Mazurkiewicz [Concurrent program schemes and their interpretations, DAIMI-PB-78, Aarhus University (1977)] and W. Zielonka [RAIRO Inf. Theor. Appl. 21, 99-135 (1987; Zbl 0623.68055); Lect. Notes Comput. Sci. 38, 278-289 (1989; Zbl 0678.68077)] are continued. It is proved that an asynchronous cellular automaton can be constructed (in polynomial time) accepting the same trace language as a given asynchronous automaton. (The converse construction is obvious.) The question of unicity of minimum asynchronous automata and/or asynchronous cellular automata recognizing a given trace language is studied; both positive and negative results are obtained in this field, depending on which version of the problem is considered. To any (finite or infinite) string \(\gamma\) over \(\{0, 1\}\) an asynchronous automaton \({\mathcal A}\) is associated, the minimality of \({\mathcal A}\) is shown to be equivalent to the non-periodicity (in another terminology, primitivity) of \(\gamma\). It follows from the results that the class of concurrent alphabets for which every recognizable trace language admits a minimum finite state asynchronous automaton becomes narrower when “asynchronous automaton” is replaced by “asynchronous cellular automaton”.
Reviewer: A.Ádám (Budapest)
MSC:
| 68Q45 | Formal languages and automata |
| 68Q80 | Cellular automata (computational aspects) |
| 68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |
References:
| [1] | Aalbersberg, I. J.J.; Rozenberg, G., Theory of traces, Theoret. Comput. Sci., 60, 1-82 (1988) · Zbl 0652.68017 |
| [2] | Arnold, A., An extension of the notions of traces and of asynchronous automata, RAIRO Inform. Theor. Appl., 25, 355-393 (1991) · Zbl 0765.68153 |
| [3] | Bertoni, A.; Brambilla, M.; Mauri, G.; Sabadini, N., An application of the theory of free partially commutative monoids: asymptotic densities of trace languages, (Proc. 10th MFCS. Proc. 10th MFCS, Lecture Notes in Computer Science, Vol. 118 (1981), Springer: Springer Berlin), 205-215 · Zbl 0468.68081 |
| [4] | Bertoni, A.; Mauri, G.; Sabadini, N., Concurrency and commutativity, (Tech. Report (1982), University of Milan). (Tech. Report (1982), University of Milan), 3rd European Workshop on Applications and Theory of Petri Nets (1982), Varenna · Zbl 0512.68056 |
| [5] | Bertoni, A.; Mauri, G.; Sabadini, N., Membership problem for regular and context-free trace languages, Inform. and Comput., 82, 135-150 (1989) · Zbl 0682.68040 |
| [6] | Bruschi, D.; Pighizzini, G.; Sabadini, N., On the existence of the minimum asynchronous automaton and on decision problems for unambiguous regular trace languages, (Proc. 5th STACS. Proc. 5th STACS, Lecture Note in Computer Science, Vol. 294 (1988), Springer: Springer Berlin), 334-346, A revised version will appear in Inform. and Comput. · Zbl 0644.68099 |
| [7] | Cartier, P.; Foata, M., Problèmes combinatories de commutation et réarrangements, (Lecture Notes in Mathematics, Vol. 85 (1969), Springer: Springer Berlin) · Zbl 0186.30101 |
| [8] | Cori, R.; Latteux, M.; Roos, Y.; Sopena, E., 2-asynchronous automata, Theoret. Comput. Sci., 61, 93-102 (1988) · Zbl 0655.68069 |
| [9] | Cori, R.; Métivier, Y., Recognizable subsets of some partially abelian monoids, Theoret. Comput. Sci., 35, 179-189 (1985) · Zbl 0559.20040 |
| [10] | Cori, R.; Métivier, Y., Approximation of a trace, asynchronous automata and the ordering of events in a distributed system, (Proc. 15th ICALP. Proc. 15th ICALP, Lecture Notes in Computer Science, Vol. 317 (1988), Springer: Springer Berlin), 147-161 · Zbl 0656.68060 |
| [11] | Cori, R.; Métivier, Y.; Zielonka, W., Asynchronous mappings and asynchronous cellular automata, (Tech. Report 89-97 (1989), Universitéde Bordeaux I), LaBRI · Zbl 0785.68068 |
| [12] | Diekert, V., Combinatorial rewriting on traces, (Proc. 7th STACS. Proc. 7th STACS, Lecture Notes in Computer Science, Vol. 415 (1990), Springer: Springer Berlin), 138-151 · Zbl 0729.68034 |
| [13] | Diekert, V., Combinatorics on traces, (Lecture Notes in Computer Science, Vol. 454 (1990), Springer: Springer Berlin) · Zbl 0717.68002 |
| [14] | Duboc, C., Commutations dans les monoïdes libres: Un cadre théorique pour l’étude du parallélism, (Ph.D. Thesis (1986), Universitéde Rouen) |
| [15] | Duboc, C., Mixed product and asynchronous automata, Theoret. Comput. Sci., 48, 183-199 (1986) · Zbl 0638.68095 |
| [16] | Ehrig, H.; Kiermeier, K.; Kreowski, H.; Kühnel, W., Universal Theory of Automata (1974), Teubner: Teubner Stuttgart · Zbl 0289.94023 |
| [17] | Eilenberg, S., Automata, Languages and Machines, Vol. A (1974), Academic Press: Academic Press New York · Zbl 0317.94045 |
| [18] | Gastin, P.; Petit, A., Asynchronous automata for infinite traces, (Proc. 19th ICALP. Proc. 19th ICALP, Lecture Notes in Computer Science, Vol. 623 (1992), Springer: Springer Berlin), 583-594 · Zbl 1425.68281 |
| [19] | Hopcroft, J.; Ullman, J., Introduction to Automata Theory, Languages and Computations (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0426.68001 |
| [20] | Jesi, S.; Pighizzini, G.; Sabadini, N., Probabilistic asynchronous automata, (Proc. Workshop: Free Partially Commutative Monoids (1990), Institüt für Informatik - Technische Universität München - TUM-I9002), 99-114, A revised version will appear in Math. Systems Theory · Zbl 0840.68079 |
| [21] | Mazurkiewicz, A., Concurrent program schemes and their interpretations, (Tech. Report DAIMI Rep. PB-78 (1977), Aarhus University) |
| [22] | Mazurkiewicz, A., Trace theory, (Advances in Petri Nets 1986. Advances in Petri Nets 1986, Lecture Notes in Computer Science, Vol. 255 (1986), Springer: Springer Berlin), 279-324 · Zbl 0633.68051 |
| [23] | Métivier, Y., On recognizable subsets of free partially commutative monoids, Theoret. Comput. Sci., 58, 201-208 (1988) · Zbl 0658.20031 |
| [24] | Nerode, A., Linear automaton transformations, Proc. Amer. Math. Soc., 9, 541-544 (1958) · Zbl 0089.33403 |
| [25] | Von Neumann, J., Theory of Self-reproducing Automata (1966), Univ. of Illinois Press: Univ. of Illinois Press Champaign, IL., Revised by A.W. Burks |
| [26] | Ochmański, E., Regular behaviour of concurrent systems, EATCS Bull., 27, 56-67 (1985) |
| [27] | Roos, Y., Automates virtuellement asynchrones, (Tech. Report IT-93 (1987), Laboratoire d’Informatique fondamentale de Lille, Univ. Lille Flandres Artois) |
| [28] | Zielonka, W., Notes on finite asynchronous automata, RAIRO Inform Theor. Appl., 21, 99-135 (1987) · Zbl 0623.68055 |
| [29] | Zielonka, W., Safe executions of recognizable trace languages by asynchronous automata, (Proc. Logic at Botik ’89. Proc. Logic at Botik ’89, Lecture Notes in Computer Science, Vol. 363 (1989), Springer: Springer Berlin), 278-289 · Zbl 0678.68077 |
| [30] | Zielonka, W., Asynchronous automata, (Proc. Workshop: Free Partially Commutative Monoids (1990), Institüt für Informatik - Technische Universität München - TUM-I9002), 183-197 |
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.
