Inverse monoids of dot-depth two
The dot-depth hierarchy of star-free regular languages has been introduced by \textit{J. Brzozowski} and \textit{R. Cohen} [J. Comput. Syst. Sci. 5, 1-16 (1971; Zbl 0217.296)]. A variant has been considered by \textit{H. Straubing} [J. Pure Appl. Algebra, 36, 53-94 (1985; Zbl 0561.20042)]. Its level 0 consists of \(A^*\) and the empty set, and its \((n+1)\)-th level is the boolean algebra generated by languages of the form \(L_ 0a_ 1L_ 1...a_ kL_ k\), \(k\geq 0\), where \(a_ i\) are letters and \(L_ i\) are languages in level n, for each i. In [Lect. Notes Comput. Sci. 226, 416-423 (1986; Zbl 0596.68056)], \textit{H. Straubing} gives a decidable necessary condition for a language to have dot-depth two, and proves that it is sufficient for languages over a two- letter alphabet. This condition it is investigated in the case of languages whose syntactic monoid is inverse, and it is proved that it is sufficient if the syntactic monoid has two inverse generators.
- A generalization of the Schützenberger product of finite monoids
- Categories as algebra: An essential ingredient in the theory of monoids
- Catégories et langages de dot-depth un
- Characterizations of locally testable events
- Classifying regular events in symbolic logic
- Dot-depth of star-free events
- Finite semigroup varieties of the form V*D
- First-order logic and star-free sets
- scientific article; zbMATH DE number 3827223 (Why is no real title available?)
- scientific article; zbMATH DE number 3961008 (Why is no real title available?)
- scientific article; zbMATH DE number 4034007 (Why is no real title available?)
- scientific article; zbMATH DE number 4037246 (Why is no real title available?)
- scientific article; zbMATH DE number 3654376 (Why is no real title available?)
- scientific article; zbMATH DE number 3495598 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3894493 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- On finite monoids having only trivial subgroups
- Parity, circuits, and the polynomial-time hierarchy
- The dot-depth hierarchy of star-free languages is infinite
- Varieties of finite categories
- Weak Second‐Order Arithmetic and Finite Automata
- Semigroups and languages of dot-depth two
- Polynomial operations and hierarchies of concatenation
- AUTOMATE, a computing package for automata and finite semigroups
- On a conjecture concerning dot-depth two languages
- Some results on the dot-depth hierarchy
- Equations and monoid varieties of dot-depth one and two
- Polynomial closure and unambiguous product
- Logic, semigroups and automata on words
- Some complexity results for polynomial rational expressions.
- Inclusion relations between some congruences related to the dot-depth hierarchy
- Two-dimensional monadicity
- A conjecture on the concatenation product
- scientific article; zbMATH DE number 1254093 (Why is no real title available?)
- INVERSE MONOIDS OF DOT-DEPTH TWO
- The product of rational languages
- Polynomial closure and unambiguous product
- On dot-depth two
- Dot-depth three, return of the j-class
This page was built for publication: Inverse monoids of dot-depth two
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1124363)
