6533b823fe1ef96bd127e282

RESEARCH PRODUCT

Topological properties of cellular automata on trees

Francesca FiorenziGabriele Fici

subject

[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)FOS: Physical sciencesComputer Science - Formal Languages and Automata Theory0102 computer and information sciences[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Computational Complexity (cs.CC)Topology01 natural scienceslcsh:QA75.5-76.95[INFO.INFO-FL]Computer Science [cs]/Formal Languages and Automata Theory [cs.FL]0101 mathematicsF.1.1;F.1.2;F.1.3MathematicsCellular Automata and Lattice Gases (nlin.CG)lcsh:Mathematics010102 general mathematicsCellular automaton tree shift expansivity permutivity right-closingness opennesslcsh:QA1-939Nonlinear Sciences::Cellular Automata and Lattice GasesCellular automatonAutomatonComputer Science - Computational Complexity010201 computation theory & mathematicsTree (set theory)lcsh:Electronic computers. Computer scienceF.1.2F.1.3ExpansiveNonlinear Sciences - Cellular Automata and Lattice GasesF.1.1Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics

description

We prove that there do not exist positively expansive cellular automata defined on the full k-ary tree shift (for k>=2). Moreover, we investigate some topological properties of these automata and their relationships, namely permutivity, surjectivity, preinjectivity, right-closingness and openness.

yearjournalcountryeditionlanguage
2012-08-13
10.4204/eptcs.90.20http://arxiv.org/abs/1208.2766