Cellular String Generators - Cellular Automata and Discrete Complex Systems
Conference Papers Year : 2020

Cellular String Generators

Martin Kutrib
  • Function : Author
  • PersonId : 884118
Andreas Malcher
  • Function : Author
  • PersonId : 1038035

Abstract

In contrast to many investigations of cellular automata with regard to their ability to accept inputs under certain time constraints, we are studying here cellular automata towards their ability to generate strings in real time. Structural properties such as speed-up results and closure properties are investigated. On the one hand, constructions for the closure under intersection, reversal, and length-preserving homomorphism are presented, whereas on the other hand the non-closure under union, complementation, and arbitrary homomorphism is obtained. Finally, decidability questions such as emptiness, finiteness, equivalence, inclusion, regularity, and context-freeness are addressed.
Fichier principal
Vignette du fichier
496967_1_En_5_Chapter.pdf (416.84 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03659467 , version 1 (05-05-2022)

Licence

Identifiers

Cite

Martin Kutrib, Andreas Malcher. Cellular String Generators. 26th International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA), Aug 2020, Stockholm, Sweden. pp.59-70, ⟨10.1007/978-3-030-61588-8_5⟩. ⟨hal-03659467⟩
62 View
43 Download

Altmetric

Share

More