Orbit expandability of automaton semigroups and groups

DOI10.1016/j.tcs.2019.12.037zbMath1455.68107arXiv1812.07359OpenAlexW2903867399WikidataQ126402713 ScholiaQ126402713MaRDI QIDQ2290646

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

Publication date: 29 January 2020

Published in: Theoretical Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

decidabilityautomaton semigroupautomaton groupexpandable wordorbital growth

Mathematics Subject Classification ID

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

Infinite automaton semigroups and groups have infinite orbits ⋮ On the structure theory of partial automaton semigroups

Cites Work

• Groups of intermediate growth: an introduction.
• Automaton semigroups
• The method of forced enumeration for nondeterministic automata
• Infinite automaton semigroups and groups have infinite orbits
• On the complexity of the word problem for automaton semigroups and automaton groups
• Milnor's Problem on the Growth of Groups and its Consequences
• Nondeterministic Space is Closed under Complementation
• THE FINITENESS PROBLEM FOR AUTOMATON SEMIGROUPS IS UNDECIDABLE
• Unnamed Item
• Unnamed Item
• Unnamed Item