BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Tullio Ceccherini-Silberstein

Tullio Ceccherini-Silberstein contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
math.GRmath.DSDiscrete MathematicsFormal Languages and Automata TheoryInformation Theorymath.AGmath.ITmath.APmath.COmath.LOmath.RA

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
14works
0followers
11topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

14 published item(s)

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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access
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.

0 citations0 reviewsNo code linkedOpen access