Portal de Periódicos da CAPES

Inverse monoids of dot-depth two

1989; Elsevier BV; Volume: 66; Issue: 3 Linguagem: Francês

10.1016/0304-3975(89)90151-5

1879-2294

Pascal Weil,

Algorithms and Data Compression

Nous étudions une condition nécessaire, énoncée par Straubing, pour qu'un langage rationnel sans étoile appartienne au niveau deux de la hiérarchie de concaténation de Straubing. Nous prouvons que la condition est suffisante pour les langages dont le monoïde syntaxique est un monoïde inversif á deux générateurs inversifs. We investigate a necessary condition, enounced by Straubing, for a star-free regular language to have dot-depth two. We prove that the condition is sufficient for languages whose syntactic monoid is an inverse monoid with two inverse generators.