Source author record

Tullio Ceccherini-Silberstein

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

ResearcherUnclaimed source record

math.GR math.DS math.CO math.FA Discrete Mathematics Formal Languages and Automata Theory Information Theory math.AG math.IT math.AP math.LO math.MG math.RA

Catalog footprint

Research overview

26works

13topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2018arXiv

On the Garden of Eden theorem for endomorphisms of symbolic algebraic varieties

Let $G$ be an amenable group and let $X$ be an irreducible complete algebraic variety over an algebraically closed field $K$ . Let $A$ denote the set of $K$ -points of $X$ and let $τ\colon A^G \to A^G$ be an algebraic cellular automaton over $(G,X,K)$ , that is, a cellular automaton over the group $G$ and the alphabet $A$ whose local defining map is induced by a morphism of $K$ -algebraic varieties. We introduce a weak notion of pre-injectivity for algebraic cellular automata, namely $(*)$ -pre-injectivity, and prove that $τ$ is surjective if and only if it is $(*)$ -pre-injective. In particular, $τ$ has the Myhill property, i.e., is surjective whenever it is pre-injective. Our result gives a positive answer to a question raised by Gromov in~\cite{gromov-esav} and yields an analogue of the classical Moore-Myhill Garden of Eden theorem.

preprint2016arXiv

A Garden of Eden theorem for Anosov diffeomorphisms on tori

Let $f$ be an Anosov diffeomorphism of the $n$ -dimensional torus ${\mathbb{T}}^n$ and $τ$ a continuous self-mapping of ${\mathbb{T}}^n$ commuting with $f$ . We prove that $τ$ is surjective if and only if the restriction of $τ$ to each homoclinicity class of $f$ is injective.

preprint2016arXiv

A note on the surjunctivity of algebraic dynamical systems

Let $X$ be a compact metrizable group and $Γ$ a countable group acting on $X$ by continuous group automorphisms. We give sufficient conditions under which the dynamical system $(X,Γ)$ is surjunctive, i.e., every injective continuous map $τ\colon X \to X$ commuting with the action of $Γ$ is surjective.

preprint2016arXiv

Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces

This is an expostion of various aspects of amenability and paradoxical decompositions for groups, group actions and metric spaces. First, we review the formalism of pseudogroups, which is well adapted to stating the alternative of Tarski, according to which a pseudogroup without invariant mean gives rise to paradoxical decompositions, and to defining a Følner condition. Using a Hall-Rado Theorem on matchings in graphs, we show then for pseudogroups that existence of an invariant mean is equivalent to the Følner condition; in the case of the pseudogroup of bounded perturbations of the identity on a locally finite metric space, these conditions are moreover equivalent to the negation of the Gromov's so-called doubling condition, to isoperimetric conditions, to Kesten's spectral condition for related simple random walks, and to various other conditions. We define also the minimal Tarski number of paradoxical decompositions associated to a non-amenable group action (an integer $\ge 4$ ), and we indicate numerical estimates (Sections II.4 and IV.2). The final chapter explores for metric spaces the notion of supramenability, due for groups to Rosenblatt.

preprint2015arXiv

Expansive actions of countable amenable groups, homoclinic pairs, and the Myhill property

Let $X$ be a compact metrizable space equipped with a continuous action of a countable amenable group $G$ . Suppose that the dynamical system $(X,G)$ is expansive and is the quotient by a uniformly bounded-to-one factor map of a strongly irreducible subshift. Let $τ\colon X \to X$ be a continuous map commuting with the action of $G$ . We prove that if there is no pair of distinct $G$ -homoclinic points in $X$ having the same image under $τ$ , then $τ$ is surjective.

preprint2015arXiv

On Residually Finite Semigroups of Cellullar Automata

We prove that if $M$ is a monoid and $A$ a finite set with more than one element, then the residual finiteness of $M$ is equivalent to that of the monoid consisting of all cellular automata over $M$ with alphabet $A$ .

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

On sofic monoids

We investigate the notion of soficity for monoids. A group is sofic as a group if and only if it is sofic as a monoid. All finite monoids, all commutative monoids, all free monoids, all cancellative one-sided amenable monoids, all multiplicative monoids of matrices over a field, and all monoids obtained by adjoining an identity element to a semigroup without identity element are sofic. On the other hand, although the question of the existence of a non-sofic group remains open, we prove that the bicyclic monoid is not sofic. This shows that there exist finitely presented amenable inverse monoids that are non-sofic.

preprint2014arXiv

On surjunctive monoids

A monoid $M$ is called surjunctive if every injective cellular automata with finite alphabet over $M$ is surjective. We show that all finite monoids, all finitely generated commutative monoids, all cancellative commutative monoids, all residually finite monoids, all finitely generated linear monoids, and all cancellative one-sided amenable monoids are surjunctive. We also prove that every limit of marked surjunctive monoids is itself surjunctive. On the other hand, we show that the bicyclic monoid and, more generally, all monoids containing a submonoid isomorphic to the bicyclic monoid are non-surjunctive.

preprint2013arXiv

Sensitivity and Devaney's chaos in uniform spaces

We give sufficient conditions for sensitivity of continuous group actions on uniform spaces.

preprint2013arXiv

The Myhill property for cellular automata on amenable semigroups

Let $S$ be a cancellative left-amenable semigroup and let $A$ be a finite set. We prove that every pre-injective cellular automaton $τ\colon A^S \to A^S$ is surjective.

preprint2012arXiv

An analogue of Fekete's lemma for subadditive functions on cancellative amenable semigroups

We prove an analogue of Fekete's lemma for subadditive right-subinvariant functions defined on the finite subsets of a cancellative left-amenable semigroup. This extends results previously obtained in the case of amenable groups by E. Lindenstrauss and B. Weiss and by M. Gromov.

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

Surjunctivity and reversibility of cellular automata over concrete categories

Following ideas developed by Misha Gromov, we investigate surjunctivity and reversibility properties of cellular automata defined over certain concrete categories.

preprint2011arXiv

Expansive actions on uniform spaces and surjunctive maps

We present a uniform version of a result of M. Gromov on the surjunctivity of maps commuting with expansive group actions and discuss several applications. We prove in particular that for any group $Γ$ and any field $\K$, the space of $Γ$ -marked groups $G$ such that the group algebra $\K[G]$ is stably finite is compact.

preprint2011arXiv

On a family of Schreier graphs of intermediate growth associated with a self-similar group

For every infinite sequence $ω=x_1,x_2,...$ , with $x_i\in\{0,1\}$ , we construct an infinite 4-regular graph $X_ω$ . These graphs are precisely the Schreier graphs of the action of a certain self-similar group on the space $\{0,1\}^{\infty}$ . We solve the isomorphism and local isomorphism problems for these graphs, and determine their automorphism groups. Finally, we prove that all graphs $X_ω$ have intermediate growth.

preprint2011arXiv

On algebraic cellular automata

We investigate some general properties of algebraic cellular automata, i.e., cellular automata over groups whose alphabets are affine algebraic sets and which are locally defined by regular maps. When the ground field is assumed to be uncountable and algebraically closed, we prove that such cellular automata always have a closed image with respect to the prodiscrete topology on the space of configurations and that they are reversible as soon as they are bijective.

preprint2011arXiv

On the density of periodic configurations in strongly irreducible subshifts

Let $G$ be a residually finite group and let $A$ be a finite set. We prove that if $X \subset A^G$ is a strongly irreducible subshift of finite type containing a periodic configuration then periodic configurations are dense in $X$ . The density of periodic configurations implies in particular that every injective endomorphism of $X$ is surjective and that the group of automorphisms of $X$ is residually finite. We also introduce a class of subshifts $X \subset A^\Z$ , including all strongly irreducible subshifts and all irreducible sofic subshifts, in which periodic configurations are dense.

preprint2011arXiv

The surjectivity of the combinatorial Laplacian on infinite graphs

Given a connected locally finite simplicial graph $G$ with vertex set $V$ , the combinatorial Laplacian $Δ_G \colon \R^V \to \R^V$ is defined on the space of all real-valued functions on $V$ . We prove that $Δ_G$ is surjective if $G$ is infinite.

preprint2010arXiv

A Garden of Eden theorem for linear subshifts

Let $G$ be an amenable group and let $V$ be a finite-dimensional vector space over an arbitrary field $\K$. We prove that if $X \subset V^G$ is a strongly irreducible linear subshift of finite type and $τ\colon X \to X$ is a linear cellular automaton, then $τ$ is surjective if and only if it is pre-injective. We also prove that if $G$ is countable and $X \subset V^G$ is a strongly irreducible linear subshift, then every injective linear cellular automaton $τ\colon X \to X$ is surjective.

preprint2010arXiv

On the reversibility and the closed image property of linear cellular automata

When $G$ is an arbitrary group and $V$ is a finite-dimensional vector space, it is known that every bijective linear cellular automaton $τ\colon V^G \to V^G$ is reversible and that the image of every linear cellular automaton $τ\colon V^G \to V^G$ is closed in $V^G$ for the prodiscrete topology. In this paper, we present a new proof of these two results which is based on the Mittag-Leffler lemma for projective sequences of sets. We also show that if $G$ is a non-periodic group and $V$ is an infinite-dimensional vector space, then there exist a linear cellular automaton $τ_1 \colon V^G \to V^G$ which is bijective but not reversible and a linear cellular automaton $τ_2 \colon V^G \to V^G$ whose image is not closed in $V^G$ for the prodiscrete topology.

preprint2010arXiv

The Myhill property for strongly irreducible subshifts over amenable groups

Let $G$ be an amenable group and let $A$ be a finite set. We prove that if $X \subset A^G$ is a strongly irreducible subshift then $X$ has the Myhill property, that is, every pre-injective cellular automaton $τ\colon X \to X$ is surjective.

preprint2010arXiv

The Tutte Polynomial of the Schreier graphs of the Grigorchuk group and the Basilica group

We study the Tutte polynomial of two infinite families of finite graphs. These are the Schreier graphs associated with the action of two well-known self-similar groups acting on the binary rooted tree by automorphisms: the first Grigorchuk group of intermediate growth, and the iterated monodromy group of the complex polynomial $z^2-1$ known as the Basilica group. For both of them, we describe the Tutte polynomial and we compute several special evaluations of it, giving further information about the combinatorial structure of these graphs.

preprint2009arXiv

Context-free pairs of groups I: Context-free pairs and graphs

Let $G$ be a finitely generated group, $A$ a finite set of generators and $K$ a subgroup of $G$ . We call the pair $(G,K)$ context-free if the set of all words over $A$ that reduce in $G$ to an element of $K$ is a context-free language. When $K$ is trivial, $G$ itself is called context-free; context-free groups have been classified more than 20 years ago in celebrated work of Muller and Schupp as the virtually free groups. Here, we derive some basic properties of such group pairs. Context-freeness is independent of the choice of the generating set. It is preserved under finite index modifications of $G$ and finite index enlargements of $K$ . If $G$ is virtually free and $K$ is finitely generated then $(G,K)$ is context-free. A basic tool is the following: $(G,K)$ is context-free if and only if the Schreier graph of $(G,K)$ with respect to $A$ is a context-free graph.

preprint2009arXiv

On a characterization of locally finite groups in terms of linear cellular automata

We prove that a group $G$ is locally finite if and only if every surjective real (or complex) linear cellular automaton with finite-dimensional alphabet over $G$ is injective.

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.

Tullio Ceccherini-Silberstein

Research overview

Is this your work?

26 publications

On the Garden of Eden theorem for endomorphisms of symbolic algebraic varieties

A Garden of Eden theorem for Anosov diffeomorphisms on tori

A note on the surjunctivity of algebraic dynamical systems

Amenability and paradoxical decompositions for pseudogroups and for discrete metric spaces

Expansive actions of countable amenable groups, homoclinic pairs, and the Myhill property

On Residually Finite Semigroups of Cellullar Automata

Cellular automata between sofic tree shifts

On sofic monoids

On surjunctive monoids

Sensitivity and Devaney's chaos in uniform spaces

The Myhill property for cellular automata on amenable semigroups

An analogue of Fekete's lemma for subadditive functions on cancellative amenable semigroups

Cellular automata on regular rooted trees

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

Surjunctivity and reversibility of cellular automata over concrete categories

Expansive actions on uniform spaces and surjunctive maps

On a family of Schreier graphs of intermediate growth associated with a self-similar group

On algebraic cellular automata

On the density of periodic configurations in strongly irreducible subshifts

The surjectivity of the combinatorial Laplacian on infinite graphs

A Garden of Eden theorem for linear subshifts

On the reversibility and the closed image property of linear cellular automata

The Myhill property for strongly irreducible subshifts over amenable groups

The Tutte Polynomial of the Schreier graphs of the Grigorchuk group and the Basilica group

Context-free pairs of groups I: Context-free pairs and graphs

On a characterization of locally finite groups in terms of linear cellular automata

See the researcher in context

Building this map preview