13 citations · 31 across the 11 of their papers we have counts for
11 papers
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…
The Self-Similarity of Free Semigroups and Groups
Emanuele Rodaro, Jan Philipp Wächter
We give a survey on results regarding self-similar and automaton presentations of free groups and semigroups and related products. Furthermore, we discuss open problems and results…
Preserving self-similarity in free products of semigroups
Tara Macalister Brough, Jan Philipp Wächter, Janette Welker
We improve on earlier results on the closure under free products of the class of automaton semigroups. We consider partial automata and show that the free product of two self-simil…
On Orbits and the Finiteness of Bounded Automaton Groups
Ievgen Bondarenko, Jan Philipp Wächter
We devise an algorithm which, given a bounded automaton A, decides whether the group generated by A is finite. The solution comes from a description of the infinite sequences havin…
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…
Two-Variable Ehrenfeucht-Fraisse Games over Omega-Terms
Manfred Kufleitner, Jan Philipp Wächter
Fragments of first-order logic over words can often be characterized in terms of finite monoids, and identities of omega-terms are an effective mechanism for specifying classes of…