Orbit expandability of automaton semigroups and groups

DOI10.1016/J.TCS.2019.12.037MaRDI QIDQ2290646zbMATH OpenOpenAlexWikidataFDO

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

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) Word problems, other decision problems, connections with logic and automata (group-theoretic aspects) (20F10) Semigroups in automata theory, linguistics, etc. (20M35)

Abstract: We introduce the notion of expandability in the context of automaton semigroups and groups: a word is k-expandable if one can append a suffix to it such that the size of the orbit under the action of the automaton increases by at least k. This definition is motivated by the question which {omega}-words admit infinite orbits: for such a word, every prefix is expandable. In this paper, we show that, on input of a word u, an automaton T and a number k, it is decidable to check whether u is k-expandable with respect to the action of T. In fact, this can be done in exponential nondeterministic space. From this nondeterministic algorithm, we obtain a bound on the length of a potential orbit-increasing suffix x. Moreover, we investigate the situation if the automaton is invertible and generates a group. In this case, we give an algebraic characterization for the expandability of a word based on its shifted stabilizer. We also give a more efficient algorithm to decide expandability of a word in the case of automaton groups, which allows us to improve the upper bound on the maximal orbit-increasing suffix length. Then, we investigate the situation for reversible (and complete) automata and obtain that every word is expandable with respect to these automata. Finally, we give a lower bound example for the length of an orbit-increasing suffix.

Recommendations

• On the orbits of automaton semigroups and groups
• Infinite automaton semigroups and groups have infinite orbits
• Orbit automata as a new tool to attack the order problem in automaton groups
• scientific article; zbMATH DE number 6887117
• Growth of action graphs of finite automata
• On orbits and the finiteness of bounded automaton groups
• Growth of Schreier graphs of automaton groups.
• A new hierarchy for automaton semigroups
• scientific article; zbMATH DE number 2169357

Cites work

• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 789816 (Why is no real title available?)
• scientific article; zbMATH DE number 7650891 (Why is no real title available?)
• Automaton semigroups
• Groups of intermediate growth: an introduction.
• Infinite automaton semigroups and groups have infinite orbits
• Milnor's problem on the growth of groups and its consequences.
• Nondeterministic Space is Closed under Complementation
• On the complexity of the word problem for automaton semigroups and automaton groups
• The finiteness problem for automaton semigroups is undecidable.
• The method of forced enumeration for nondeterministic automata

Cited in

(5)

• On the structure theory of partial automaton semigroups
• Infinite automaton semigroups and groups have infinite orbits
• Automorphism groups of a class of expanding attractors
• Orbits of abelian automaton groups
• On the orbits of automaton semigroups and groups

This page was built for publication: Orbit expandability of automaton semigroups and groups

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