2015/09/30 by Manfred Kufleitner, Jan Philipp Wächter · 2 citations
Computer Science · Mathematics · #Algebra over a field #Arithmetic #Combinatorics #Decidability #Discrete mathematics #Hierarchy #Logic, programming, and type systems #Mathematics #Natural Language Processing Techniques #Nondeterministic algorithm #Pure mathematics #Time complexity #Variety (cybernetics) #Word (group theory) #Word problem (mathematics education) #cs.FL #math.GR #semigroups and automata theory
paper · pdf · doi:10.1007/s00224-017-9763-z
published in Theory of Computing Systems 62(3), 682-738 (Springer Science+Business Media)
openalex publication_date 2017/05/15 · arxiv created 2017/05/16 · arxiv updated 2017/05/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
For two given ω-terms α and β, the word problem for ω-terms over a variety \boldsymbolV asks whether α=β in all monoids in \boldsymbolV. We show that the word problem for ω-terms over each level of the Trotter-Weil Hierarchy is decidable. More precisely, for every fixed variety in the Trotter-Weil Hierarchy, our approach yields an algorithm in nondeterministic logarithmic space (NL). In addition, we provide deterministic polynomial time algorithms which are more efficient than straightforward translations of the NL-algorithms. As an application of our results, we show that separability by the so-called corners of the Trotter-Weil Hierarchy is witnessed by ω-terms (this property is also known as ω-reducibility). In particular, the separation problem for the corners of the Trotter-Weil Hierarchy is decidable.