The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy

Abstract

For two given $\omega$-terms $\alpha$ and $\beta$, the word problem for $\omega$-terms over a variety $\mathrm{V}$ asks whether $\alpha =\beta$ in all monoids in $\mathrm{V}$. We show that the word problem for $\omega$-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 $\omega$-terms (this property is also known as $\omega$-reducibility). In particular, the separation problem for the corners of the Trotter-Weil Hierarchy is decidable.

References in corpus (3)

• The FO^2 alternation hierarchy is decidable
• On logical hierarchies within FO^2-definable languages
• The separation problem for regular languages by piecewise testable languages

Cited by in corpus (1)

• Recognizing pro-R closures of regular languages