BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Michel Coornaert

Michel Coornaert appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.DSmath.GRDiscrete MathematicsFormal Languages and Automata Theorymath.AGmath.FAInformation Theorymath.APmath.COmath.ITmath.LOmath.RA

Catalog footprint

What is connected

22works
12topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

22 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
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.

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
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.

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

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
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.

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