%0 Conference Proceedings
%T Construction of Some Nonautomatic Sequences by Cellular Automata
%+ Institut Élie Cartan de Lorraine (IECL)
%+ Designing the Future of Computational Models (MOCQUA)
%A Marcovici, Irène
%A Stoll, Thomas
%A Tahay, Pierre-Adrien
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B AUTOMATA 2018 - 24th International Workshop on Cellular Automata and Discrete Complex Systems
%C Ghent, Belgium
%Y Jan M. Baetens
%Y Martin Kutrib
%I Springer International Publishing
%3 Cellular Automata and Discrete Complex Systems
%V LNCS-10875
%P 113-126
%8 2018-06-20
%D 2018
%R 10.1007/978-3-319-92675-9_9
%K Automatic sequences
%K Nonautomatic sequences
%K Computability
%K Polynomials
%K Fibonacci word
%K Cellular automata
%Z Computer Science [cs]Conference papers
%X 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.
%G English
%Z TC 1
%Z WG 1.5
%2 https://inria.hal.science/hal-01824876/document
%2 https://inria.hal.science/hal-01824876/file/469010_1_En_9_Chapter.pdf
%L hal-01824876
%U https://inria.hal.science/hal-01824876
%~ CNRS
%~ INRIA
%~ IECN
%~ INSMI
%~ INRIA_TEST
%~ INRIA-LORRAINE
%~ LORIA2
%~ INRIA-NANCY-GRAND-EST
%~ TESTALAIN1
%~ IFIP-LNCS
%~ IFIP
%~ UNIV-LORRAINE
%~ INRIA2
%~ IFIP-TC
%~ IFIP-TC1
%~ LORIA
%~ LORIA-FM
%~ IFIP-WG1-5
%~ IFIP-AUTOMATA
%~ IECLPS
%~ IECLANALYSE
%~ IFIP-LNCS-10875