Simulation limitations of affine cellular automata

Kód výsledku v 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>

Nalezeny alternativní kódy

RIV/68407700:21240/24:00375917 RIV/68407700:21730/24:00375917

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Simulation limitations of affine cellular automata

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Simulation limitations of affine cellular automata

Popis výsledku anglicky

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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach<br>I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2024

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

1879-2294

Svazek periodika

1003

Číslo periodika v rámci svazku

July 2024

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

17

Strana od-do

114606

Kód UT WoS článku

001238064200001

EID výsledku v databázi Scopus

2-s2.0-85192063794