Post-surjectivity and balancedness of cellular automata over groups

We discuss cellular automata over arbitrary finitely generated groups. Wecall a cellular automaton post-surjective if for any pair of asymptoticconfigurations, every pre-image of one is asymptotic to a pre-image of theother. The well known dual concept is pre-injectivity: a cellular automaton ispre-...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2017-01, Vol.19 (3)
Main Authors: Capobianco, Silvio, Kari, Jarkko, Taati, Siamak
Format: Article
Language:English
Subjects:
37b15, 68q80, 37b10
Asymptotic properties
Cellular automata
Cellular biology
Configurations
mathematics - dynamical systems
nonlinear sciences - cellular automata and lattice gases
Simulation
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We discuss cellular automata over arbitrary finitely generated groups. Wecall a cellular automaton post-surjective if for any pair of asymptoticconfigurations, every pre-image of one is asymptotic to a pre-image of theother. The well known dual concept is pre-injectivity: a cellular automaton ispre-injective if distinct asymptotic configurations have distinct images. Weprove that pre-injective, post-surjective cellular automata are reversible.Moreover, on sofic groups, post-surjectivity alone implies reversibility. Wealso prove that reversible cellular automata over arbitrary groups arebalanced, that is, they preserve the uniform measure on the configurationspace.
ISSN:1365-8050
DOI:10.23638/DMTCS-19-3-4