Skip to Main content Skip to Navigation
New interface
Conference papers

Construction of Some Nonautomatic Sequences by Cellular Automata

Irène Marcovici 1, 2 Thomas Stoll 1 Pierre-Adrien Tahay 1 
2 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Hal Ifip Connect in order to contact the contributor
Submitted on : Wednesday, June 27, 2018 - 4:37:58 PM
Last modification on : Friday, February 4, 2022 - 3:32:51 AM
Long-term archiving on: : Thursday, September 27, 2018 - 3:08:34 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License



Irène Marcovici, Thomas Stoll, Pierre-Adrien Tahay. Construction of Some Nonautomatic Sequences by Cellular Automata. AUTOMATA 2018 - 24th International Workshop on Cellular Automata and Discrete Complex Systems, Jun 2018, Ghent, Belgium. pp.113-126, ⟨10.1007/978-3-319-92675-9_9⟩. ⟨hal-01824876⟩



Record views


Files downloads