13 citations · 31 across the 11 of their papers we have counts for
7 papers · 1 filter
The Finiteness Problem for Automaton Semigroups of Extended Bounded Activity
Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter
We extend the notion of activity for automaton semigroups and monoids introduced by Bartholdi, Godin, Klimann and Picantin to a more general setting. Their activity notion was alre…
The Freeness Problem for Automaton Semigroups
Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter
We show that the freeness problems for automaton semigroups and for automaton monoids are undecidable and, thereby, solve an open problem listed by Grigorchuk, Nekrashevych and Sus…
The Word Problem for Finitary Automaton Groups
Maximilian Kotowsky, Jan Philipp Wächter
A finitary automaton group is a group generated by an invertible, deterministic finite-state letter-to-letter transducer whose only cycles are self-loops at an identity state. We s…
An Automaton Group with PSPACE-Complete Word Problem
Jan Philipp Wächter, Armin Weiß
We construct an automaton group with a PSPACE-complete word problem, proving a conjecture due to Steinberg. Additionally, the constructed group has a provably more difficult, namel…
Automaton Semigroups and Groups: On the Undecidability of Problems Related to Freeness and Finiteness
Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter
In this paper, we study algorithmic problems for automaton semigroups and automaton groups related to freeness and finiteness. In the course of this study, we also exhibit some con…
On the Complexity of the Word Problem for Automaton Semigroups and Automaton Groups
Daniele D'Angeli, Emanuele Rodaro, Jan Philipp Wächter
In this paper, we study the word problem for automaton semigroups and automaton groups from a complexity point of view. As an intermediate concept between automaton semigroups and…
The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
Manfred Kufleitner, Jan Philipp Wächter
For two given -terms and , the word problem for -terms over a variety asks whether in all monoids in . We show…