Source author record

Francesca Fiorenzi

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Discrete Mathematics math.GR Computational Complexity Information Theory math.DS math.IT math.LO nlin.CG

Catalog footprint

Research overview

5works

9topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2014arXiv

Cellular automata between sofic tree shifts

We study the sofic tree shifts of $A^{Σ^*}$ , where $Σ^*$ is a regular rooted tree of finite rank. In particular, we give their characterization in terms of unrestricted Rabin automata. We show that if $X \subset A^{Σ^*}$ is a sofic tree shift, then the configurations in $X$ whose orbit under the shift action is finite are dense in $X$ , and, as a consequence of this, we deduce that every injective cellular automata $τ\colon X \to X$ is surjective. Moreover, a characterization of sofic tree shifts in terms of general Rabin automata is given. We present an algorithm for establishing whether two unrestricted Rabin automata accept the same sofic tree shift or not. This allows us to prove the decidability of the surjectivity problem for cellular automata between sofic tree shifts. We also prove the decidability of the injectivity problem for cellular automata defined on a tree shift of finite type.

preprint2014arXiv

Periodic configurations of subshifts on groups

We study the density of periodic configurations for shift spaces defined on (the Cayley graph of) a finitely generated group. We prove that in the case of a full shift on a residually finite group and in that of a group shift space on an abelian group, the periodic configurations are dense. In the one-dimensional case we prove the density for irreducible sofic shifts. In connection with this we study the surjunctivity of cellular automata and local selfmappings. Some related decision problems for shift spaces of finite type are also investigated.

preprint2012arXiv

Cellular automata on regular rooted trees

We study cellular automata on regular rooted trees. This includes the characterization of sofic tree shifts in terms of unrestricted Rabin automata and the decidability of the surjectivity problem for cellular automata between sofic tree shifts.

preprint2012arXiv

Groups, Graphs, Languages, Automata, Games and Second-order Monadic Logic

In this paper we survey some surprising connections between group theory, the theory of automata and formal languages, the theory of ends, infinite games of perfect information, and monadic second-order logic.

preprint2012arXiv

Topological properties of cellular automata on trees

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.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Francesca Fiorenzi

Research overview

Is this your work?

5 publications

Cellular automata between sofic tree shifts

Periodic configurations of subshifts on groups

Cellular automata on regular rooted trees

Groups, Graphs, Languages, Automata, Games and Second-order Monadic Logic

Topological properties of cellular automata on trees

See the researcher in context

Building this map preview