Asynchronous automata versus asynchronous cellular automata
type: Item
instance of: scholarly article
title: Asynchronous automata versus asynchronous cellular automata
zbMATH Open document ID: 0826.68081
DOI: 10.1016/0304-3975(94)90232-1
author: Giovanni Pighizzini
published in: Theoretical Computer Science
publication date: 1994-09-25T00:00:00Z
review text: 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''.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 68Q80
Mathematics Subject Classification ID: 68Q10
zbMATH DE Number: 643673
zbMATH Keywords: asynchronous automaton
zbMATH Keywords: asynchronous cellular automaton
zbMATH Keywords: trace language
Wikidata QID: Q61677538
reviewed by: A. Ádám
MaRDI profile type: Publication
full work available at URL: 0304-3975(94)90232-1
OpenAlex ID: W2014604507
cites work: Theory of traces
cites work: An extension of the notions of traces and of asynchronous automata
cites work: An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
cites work: Q3657452
cites work: Membership problems for regular and context-free trace languages
cites work: Q3787509
cites work: Combinatorial problems of commutation and rearrangements
cites work: 2-asynchronous automata
cites work: Recognizable subsets of some partially Abelian monoids
cites work: Q3804201
cites work: Asynchronous mappings and asynchronous cellular automata
cites work: Q3355239
cites work: Combinatorics on traces
cites work: Mixed product and asynchronous automata
cites work: Q4041460
cites work: Q4079524
cites work: Asynchronous cellular automata for infinite traces
cites work: Q3862379
cites work: Probabilistic asynchronous automata
cites work: Q3771629
cites work: On recognizable subsets of free partially commutative monoids
cites work: Linear Automaton Transformations
cites work: Notes on finite asynchronous automata
cites work: Q3835040
description: scientific article; zbMATH DE number 643673