Asynchronous automata versus asynchronous cellular automata

DOI10.1016/0304-3975(94)90232-1zbMath0826.68081OpenAlexW2014604507WikidataQ61677538 ScholiaQ61677538MaRDI QIDQ1334661

Giovanni Pighizzini

Publication date: 25 September 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90232-1

zbMATH Keywords

trace languageasynchronous automatonasynchronous cellular automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80)

Related Items

Complexity of reachability problems for finite discrete dynamical systems ⋮ Reachability problems for sequential dynamical systems with threshold functions. ⋮ A survey of cellular automata: types, dynamics, non-uniformity and applications

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Asynchronous mappings and asynchronous cellular automata
• Mixed product and asynchronous automata
• Theory of traces
• 2-asynchronous automata
• On recognizable subsets of free partially commutative monoids
• Combinatorics on traces
• Membership problems for regular and context-free trace languages
• Recognizable subsets of some partially Abelian monoids
• Combinatorial problems of commutation and rearrangements
• Linear Automaton Transformations
• Notes on finite 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
• Probabilistic asynchronous automata
• Asynchronous cellular automata for infinite traces