Silvio Capobianco ; Jarkko Kari ; Siamak Taati - Post-surjectivity and balancedness of cellular automata over groups

dmtcs:1485 - Discrete Mathematics & Theoretical Computer Science, September 15, 2017, Vol. 19 no. 3 -
Post-surjectivity and balancedness of cellular automata over groupsArticle

Authors: Silvio Capobianco ; Jarkko Kari ORCID; Siamak Taati

    We discuss cellular automata over arbitrary finitely generated groups. We call a cellular automaton post-surjective if for any pair of asymptotic configurations, every pre-image of one is asymptotic to a pre-image of the other. The well known dual concept is pre-injectivity: a cellular automaton is pre-injective if distinct asymptotic configurations have distinct images. We prove that pre-injective, post-surjective cellular automata are reversible. Moreover, on sofic groups, post-surjectivity alone implies reversibility. We also prove that reversible cellular automata over arbitrary groups are balanced, that is, they preserve the uniform measure on the configuration space.

    Volume: Vol. 19 no. 3
    Section: Automata, Logic and Semantics
    Published on: September 15, 2017
    Accepted on: August 30, 2017
    Submitted on: July 18, 2017
    Keywords: Mathematics - Dynamical Systems,Nonlinear Sciences - Cellular Automata and Lattice Gases,37B15, 68Q80, 37B10
      Source : OpenAIRE Graph
    • From local interactions to global structures; Funder: Academy of Finland; Code: 296018
    • Variational Approach to Random Interacting Systems; Funder: European Commission; Code: 267356

    Consultation statistics

    This page has been seen 830 times.
    This article's PDF has been downloaded 561 times.