 |
Cellular Automata and Discrete Complex Systems 24th IFIP WG 1.5 International Workshop, AUTOMATA 2018 Ghent, Belgium, June 20-22, 2018 |
 |
Conference papers
Construction of Some Nonautomatic Sequences by Cellular Automata
Abstract : It is known that if p is a prime number, the columns of linear CA are p-automatic sequences and all p-automatic sequences can be realized by some linear CA with memory. We give some constructions of (nonlinear) CA that realize certain nonautomatic sequences. First, we show through a recoding that from a construction with additional symbols, we can construct a CA using only the symbols occurring in the sequence. This answers a question posed by Rowland and Yassawi. Then, we propose a construction for the characteristic sequence of the integer polynomials, which are nonautomatic sequences by the Minsky–Papert criterion. We also provide a construction based on the indicator of Fibonacci numbers for the Fibonacci word, which is an emblematic nonautomatic sequence.
Cited literature [15 references]
https://hal.inria.fr/hal-01824876
Contributor : Hal Ifip <>
Submitted on : Wednesday, June 27, 2018 - 4:37:58 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:25 PM
Document(s) archivé(s) le : Thursday, September 27, 2018 - 3:08:34 AM
Contributor : Hal Ifip <>
Submitted on : Wednesday, June 27, 2018 - 4:37:58 PM
Last modification on : Tuesday, December 18, 2018 - 4:38:25 PM
Document(s) archivé(s) le : Thursday, September 27, 2018 - 3:08:34 AM
Licence
Distributed under a Creative Commons Attribution 4.0 International License
