Please use this identifier to cite or link to this item: http://dx.doi.org/10.18419/opus-11267
Authors: Wächter, Jan Philipp
Title: Automaton structures : decision problems and structure theory
Issue Date: 2020
metadata.ubs.publikation.typ: Dissertation
metadata.ubs.publikation.seiten: v, 131
URI: http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-ds-112840
http://elib.uni-stuttgart.de/handle/11682/11284
http://dx.doi.org/10.18419/opus-11267
Abstract: This thesis is devoted to the class of automaton groups and semigroups, which has gained a reputation of containing groups and semigroups with special algebraic properties that are hard to find elsewhere. Both automaton groups and semigroups are studied from a structural and an algorithmic perspective. We motivate the use of partial automata as generating objects for algebraic structures and compare them to their complete counterparts. Additionally, we give further examples of semigroups that cannot be generated by finite automata and show that every inverse automaton semigroup is generated by a partial, invertible automaton. Moreover, we study the finite and infinite orbits of ω-words under the action induced by an automaton. Here, our main result is that every infinite automaton semigroup admits an ω-word with an infinite orbit. We apply these structural results algorithmically and show that the word problem for automaton groups and semigroups is PSpace-complete. Furthermore, we investigate a decision problem related to the freeness of automaton groups and semigroups: we show that it is undecidable whether a given automaton admits a non-trivial state sequences that acts trivially and we use this problem for further reductions. Afterwards, we strengthen Gillibert’s result on the undecidability of the finiteness problem for automaton semigroups and give a partial solution for the group case of the same problem. Finally, we consider algorithmic questions about increasing the orbits of finite words and apply these results to show that, among others, the finiteness problem for (subgroups of) automaton groups of bounded activity is decidable.
Appears in Collections:05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Files in This Item:
File Description SizeFormat 
AutomatonStructures_final.pdf1,18 MBAdobe PDFView/Open


Items in OPUS are protected by copyright, with all rights reserved, unless otherwise indicated.