Paper Info
Title
One-dimensional pattern generation by cellular automata
Abstract
To determine the computational capacity of cellular automata they are often investigated towards their ability to accept formal languages within certain time constraints. In this paper, we take up an opposite position and look at cellular automata towards their ability to generate patterns, within certain time constraints. As an example we describe a construction of a cellular automaton that generates prefixes of the Oldenburger–Kolakoski sequence within real time. Furthermore, we study the real-time generation of unary and non-unary patterns in depth. In the unary case, we obtain a characterization by time-constructible functions and their corresponding unary formal languages. In the non-unary case, we provide constructions that generate any arbitrary given properly thin context-free language as well as all prefixes of any given automatic sequence.
Year
DOI
Venue
2022
10.1007/s11047-022-09887-1
Natural Computing
Keywords
DocType
Volume
Cellular automata, Pattern generation, Thin languages, Automatic sequences
Journal
21
Issue
ISSN
Citations 
3
1567-7818
0
PageRank 
References 
Authors
0.34
11
2
Name
Order
Citations
PageRank
Martin Kutrib177889.77
Andreas Malcher200.34