Simulation limitations of affine cellular automata
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F24%3A10489811" target="_blank" >RIV/00216208:11320/24:10489811 - isvavai.cz</a>
Alternative codes found
RIV/68407700:21240/24:00375917 RIV/68407700:21730/24:00375917
Result on the web
<a href="https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=bxzW_Z-t8h" target="_blank" >https://verso.is.cuni.cz/pub/verso.fpl?fname=obd_publikace_handle&handle=bxzW_Z-t8h</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2024.114606" target="_blank" >10.1016/j.tcs.2024.114606</a>
Alternative languages
Result language
angličtina
Original language name
Simulation limitations of affine cellular automata
Original language description
Cellular automata are a famous model of computation, yet it is still a challenging task to assess the computational capacity of a given automaton; especially when it comes to showing negative results. In this paper, we focus on studying this problem via the notion of CA intrinsic simulation. We say that automaton A is simulated by B if each space-time diagram of A can be, after suitable transformations, reproduced by B. We study affine automata - i.e., automata whose local rules are affine mappings of vector spaces. This broad class contains the well-studied cases of linear automata. The main result of this paper shows that (almost) every automaton affine over a finite field F-p can only simulate affine automata over F-p. We discuss how this general result implies, and widely surpasses, limitations of linear and additive automata previously proved in the literature. We provide a formalization of the simulation notions into algebraic language and discuss how this opens a new path to showing negative results about the computational power of cellular automata using deeper algebraic theorems.
Czech name
—
Czech description
—
Classification
Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics
Result continuities
Project
—
Continuities
S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace
Others
Publication year
2024
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
1879-2294
Volume of the periodical
1003
Issue of the periodical within the volume
July 2024
Country of publishing house
NL - THE KINGDOM OF THE NETHERLANDS
Number of pages
17
Pages from-to
114606
UT code for WoS article
001238064200001
EID of the result in the Scopus database
2-s2.0-85192063794