The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages (Q1748357)
From MaRDI portal
![]() | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages |
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages |
scientific article |
Statements
The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages (English)
0 references
9 May 2018
0 references
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.
0 references
pseudovariety
0 references
ordered monoid
0 references
concatenation hierarchy
0 references
Straubing-Thérien hierarchy
0 references
$\omega$-inequality problem
0 references
0 references
0.7550684
0 references
0.72832555
0 references
0.71708393
0 references
0.7149732
0 references
0 references
0 references