Asynchronous automata versus asynchronous cellular automata
The investigations of \textit{A. Mazurkiewicz} [Concurrent program schemes and their interpretations, DAIMI-PB-78, Aarhus University (1977)] and \textit{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.
- 2-asynchronous automata
- An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
- An extension of the notions of traces and of asynchronous automata
- Asynchronous cellular automata for infinite traces
- Asynchronous mappings and asynchronous cellular automata
- Combinatorial problems of commutation and rearrangements
- Combinatorics on traces
- scientific article; zbMATH DE number 4205990 (Why is no real title available?)
- scientific article; zbMATH DE number 3808972 (Why is no real title available?)
- scientific article; zbMATH DE number 4030996 (Why is no real title available?)
- scientific article; zbMATH DE number 4051029 (Why is no real title available?)
- scientific article; zbMATH DE number 4072393 (Why is no real title available?)
- scientific article; zbMATH DE number 4112050 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3455154 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- Linear Automaton Transformations
- Membership problems for regular and context-free trace languages
- Mixed product and asynchronous automata
- Notes on finite asynchronous automata
- On recognizable subsets of free partially commutative monoids
- Probabilistic asynchronous automata
- Recognizable subsets of some partially Abelian monoids
- Theory of traces
- On the existence of minimum asynchronous automata and on the equivalence problem for unambiguous regular trace languages
- On the complementation of asynchronous cellular Büchi automata
- Reachability problems for sequential dynamical systems with threshold functions.
- ON ASYNCHRONOUS CELLULAR AUTOMATA
- scientific article; zbMATH DE number 4051029 (Why is no real title available?)
- scientific article; zbMATH DE number 1305000 (Why is no real title available?)
- scientific article; zbMATH DE number 1759634 (Why is no real title available?)
- On the complementation of Büchi asynchronous cellular automata
- Asynchronous cellular automata for infinite traces
- A survey of cellular automata: types, dynamics, non-uniformity and applications
- Asynchronous mappings and asynchronous cellular automata
- Complexity of reachability problems for finite discrete dynamical systems
This page was built for publication: Asynchronous automata versus asynchronous cellular automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1334661)
