The -inequality problem for concatenation hierarchies of star-free languages
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.
- New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
- Games, equations and the dot-depth hierarchy
- Reducibility vs. definability for pseudovarieties of semigroups
- On classes of regular languages related to monotone WQOs
- Regular solutions of language inequalities and well quasi-orders
- Automata, Languages and Programming
- Regular tree languages and quasi orders
- scientific article; zbMATH DE number 4067251
- Tree Automata Make Ordinal Theory Easy
- Nonfinite axiomatizability of the equational theory of shuffle
- A generalization of the Schützenberger product of finite monoids
- A Reiterman theorem for pseudovarieties of finite first-order structures
- Classification of finite monoids: the language approach
- Classifying regular events in symbolic logic
- Dot-depth of star-free events
- Equidivisible semigroups
- Factoriality and the Pin-Reutenauer procedure
- Finite semigroup varieties of the form V*D
- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 798167 (Why is no real title available?)
- scientific article; zbMATH DE number 3326329 (Why is no real title available?)
- HYPERDECIDABLE PSEUDOVARIETIES AND THE CALCULATION OF SEMIDIRECT PRODUCTS
- Implicit operations on finite \({\mathcal J}\)-trivial semigroups and a conjecture of I. Simon
- Infinite-vertex free profinite semigroupoids and symbolic dynamics.
- Iterated periodicity over finite aperiodic semigroups
- McCammond’s normal forms for free aperiodic semigroups revisited
- Nonstandard characterization of pseudovarieties
- NORMAL FORMS FOR FREE APERIODIC SEMIGROUPS
- On decidability of intermediate levels of concatenation hierarchies
- On fixed points of the lower set operator
- On the Decidability of Iterated Semidirect Products with Applications to Complexity
- Polynomial closure and unambiguous product
- Pro-aperiodic monoids via saturated models
- Profinite semigroups and applications.
- Profinite semigroups, Mal'cev products, and identities
- Separating regular languages with first-order logic
- The \(\mathfrak q\)-theory of finite semigroups.
- The Birkhoff theorem for finite algebras
- The word problem for omega-terms over the Trotter-Weil hierarchy
- Pro-aperiodic monoids via saturated models
- scientific article; zbMATH DE number 1688391 (Why is no real title available?)
- scientific article; zbMATH DE number 3894493 (Why is no real title available?)
- New decidable upper bound of the second level in the Straubing-Thérien concatenation hierarchy of star-free languages
- The omega-reducibility of pseudovarieties of ordered monoids representing low levels of concatenation hierarchies
- Pseudovarieties of semigroups
- A purely algebraic proof of the omega-reducibility of pseudovarieties representing low half levels of concatenation hierarchies
This page was built for publication: The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1748357)
