Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness

DOI10.1007/s11856-020-1972-5zbMath1484.20115arXiv1712.07408OpenAlexW3100772292MaRDI QIDQ2190041

Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter

Publication date: 18 June 2020

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Free semigroups, generators and relations, word problems (20M05) Undecidability and degrees of sets of sentences (03D35) Algebraic theory of languages and automata (68Q70) Semigroups in automata theory, linguistics, etc. (20M35) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10)

Related Items

Corrigendum to: ``Automaton semigroups and groups: on the undecidability of problems related to freeness and finiteness ⋮ Eraser morphisms and membership problem in groups and monoids ⋮ On a class of poly-context-free groups generated by automata ⋮ Unnamed Item ⋮ On the structure theory of partial automaton semigroups

Cites Work

• On the conjugacy problem for finite-state automorphisms of regular rooted trees. With an appendix by Raphaël M. Jungers
• Automaton semigroups: new constructions results and examples of non-automaton semigroups
• Automaton semigroup constructions.
• Schreier graphs of the Basilica group.
• The 4-way deterministic tiling problem is undecidable
• Automaton semigroups
• Deterministic aperiodic tile sets
• An automaton group with undecidable order and Engel problems
• The conjugacy problem in automaton groups is not solvable.
• A geometric approach to (semi)-groups defined by automata via dual transducers.
• On the complexity of the word problem for automaton semigroups and automaton groups
• Undecidability and nonperiodicity for tilings of the plane
• Freeness of automaton groups vs boundary dynamics
• On Torsion-Free Semigroups Generated by Invertible Reversible Mealy Automata
• Notes on the Schreier graphs of the Grigorchuk group
• Implementing Computations in Automaton (Semi)groups
• Groups and semigroups defined by colorings of synchronizing automata
• The finiteness of a group generated by a 2-letter invertible-reversible Mealy automaton is decidable
• Some undecidability results for asynchronous transducers and the Brin-Thompson group $2V$
• ON THE UNDECIDABILITY OF THE IDENTITY CORRESPONDENCE PROBLEM AND ITS APPLICATIONS FOR WORD AND MATRIX SEMIGROUPS
• INVERSE SEMIGROUPS OF PARTIAL AUTOMATON PERMUTATIONS
• ON A CLASS OF AUTOMATA GROUPS GENERALIZING LAMPLIGHTER GROUPS
• SELF-SIMILAR INVERSE SEMIGROUPS AND SMALE SPACES
• The Generation of GL(n, Z) by Finite State Automata
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• ON THE UNDECIDABILITY OF THE FREENESS OF INTEGER MATRIX SEMIGROUPS
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item