Inverse monoids of dot-depth two (Q1124363): Difference between revisions

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.