The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages (Q1748357): Difference between revisions

By an extension of the Reiterman's theorem to the ordered setting [\textit{J. E. Pin} and \textit{P. Weil}, Algebra Univers. 35, No. 4, 577--595 (1996; Zbl 0864.03024)], each pseudovariety of ordered monoids can be defined via a set of pseudoinequalities, i.e., inequalities between profinite words. An $\omega$-inequality is a special pseudoinequality, in which both sides are $\omega$-terms -- that is, formal expressions constructed from symbols of some alphabet of variables and the symbol $1$ by recursively applying the binary operation $\cdot$ (interpreted as the monoid operation) and the unary operation $\omega$ (interpreted as taking the unique idempotent in the single-generated subsemigroup). In the $\omega$-inequality problem for a pseudovariety $\pmb V$, two $\omega$-terms $u$, $v$ are given and the task is to decide whether the $\omega$-inequality $u \leq v$ holds in $\pmb V$. \par The authors prove that the $\omega$-inequality problem is decidable for all pseudovarieties of ordered monoids corresponding to levels of the Straubing-Thérien hierarchy of star-free languages. There is a hope that this result might help to establish the decidability of the membership to all levels of the Straubing-Thérien hierarchy, a long-standing conjecture.