0000000000524581

AUTHOR

Francesca Fiorenzi

showing 2 related works from this author

Topological properties of cellular automata on trees

2012

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.

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

Minimal forbidden patterns of multi-dimensional shifts

2005

We study whether the entropy (or growth rate) of minimal forbidden patterns of symbolic dynamical shifts of dimension 2 or more, is a conjugacy invariant. We prove that the entropy of minimal forbidden patterns is a conjugacy invariant for uniformly semi-strongly irreducible shifts. We prove a weaker invariant in the general case.

General Mathematics[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]020206 networking & telecommunications0102 computer and information sciences02 engineering and technology01 natural sciencesCombinatoricsConjugacy class010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineeringMulti dimensionalComputingMilieux_MISCELLANEOUSMathematics
researchProduct