A1 Refereed original research article in a scientific journal

Realization problems for nonuniform cellular automata




AuthorsVille Salo

PublisherElsevier BV

Publication year2014

JournalTheoretical Computer Science

Journal acronymTCS

Volume559

First page 91

Last page107

Number of pages17

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2014.07.031


Abstract

Given a finite set of local rules, the sequences built from them give a set of nonuniform cellular automata. It is known [1] that for any such set of local rules, the subset of nonuniform cellular automata built from them which give a surjective global map is in fact a sofic subshift. For the injective sequences, this set is only ζ-automatic (accepted by a Büchi automaton), and it is not necessarily open or closed. We prove the first corresponding realization result: we provide, for any SFT, a set of local rules such that the surjective (injective) nonuniform cellular automata over them are precisely the sequences in the SFT (up to a renaming of symbols). In fact, we prove that SFTs are exactly the subshifts which are the set of injective sequences of nonuniform cellular automata for some set of local rules. We also consider surjectivity of subclasses of nonuniform cellular automata, and realizability questions for other properties, in particular number conservation and chain transitivity.




Last updated on 2024-26-11 at 15:54