On surjunctive monoids

DOI10.1142/S0218196715500113MaRDI QIDQ5256843zbMATH OpenOpenAlexFDO

Authors Michel Coornaert, Tullio Ceccherini-Silberstein

Publication date 29 June 2015

Published in International Journal of Algebra and Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.1340

zbMATH Keywords

cellular automatonmarked monoidmonoidsurjunctive monoiduniform space

Mathematics Subject Classification ID

Semigroups in automata theory, linguistics, etc. (20M35) Symbolic dynamics (37B10) Dynamical aspects of cellular automata (37B15) Uniform structures and generalizations (54E15) Cellular automata (computational aspects) (68Q80)

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

Recommendations

• On surjunctivity of the transition functions of cellular automata on groups
• The Myhill property for cellular automata on amenable semigroups
• On dual surjunctivity and applications
• On residually finite semigroups of cellullar automata
• scientific article; zbMATH DE number 5343230

Cites work

• A generalization of the Curtis-Hedlund theorem
• Amenability of inverse semigroups and their semigroup algebras
• Amenable groups and cellular automata
• Cellular automata and groups
• Cellular automata between sofic tree shifts
• Endomorphisms and automorphisms of the shift dynamical system
• Endomorphisms of symbolic algebraic varieties
• Expansive actions on uniform spaces and surjunctive maps
• Invariant means and the Stone-Cech compactification
• On sofic monoids
• On the reversibility and the closed image property of linear cellular automata
• Residual finiteness of finitely generated commutative semigroups
• The Myhill property for cellular automata on amenable semigroups

Cited in

(8)

• Shadowing for families of endomorphisms of generalized group shifts
• On dual surjunctivity and applications
• Generating infinite monoids of cellular automata
• On residually finite semigroups of cellullar automata
• On images of subshifts under embeddings of symbolic varieties
• First-order model theory and Kaplansky's stable finiteness conjecture for surjunctive groups
• Stable finiteness of monoid algebras and surjunctivity
• On surjunctivity of the transition functions of cellular automata on groups

This page was built for publication: On surjunctive monoids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5256843)