Locally trivial categories and unambiguous concatenation

Jean-Éric Pin, Howard Straubing et Denis Thérien



Résumé : Nous utilisons la théorie récemment développée des catégories finies et du noyau bilatère pour étudier le produit de concaténation non ambigu sur les langages reconnaissables et sa contrepartie algébrique sur les monoïdes syntactiques de ces langages. On en déduit une caractérisation algébrique (due à Pin dans sa version originale) de la clôture d'une variété de langages par les opérations booléennes et le produit non ambigu, ainsi qu'un nouvelle preuve du théorème de Straubing qui caractérise la fermeture par produit et par opérations booléennes d'une variété de langages. On établit également quelques connections avec l'étude des hiérarchies de concaténation.

Abstract : We use the recently developed theory of finite categories and the two-sided kernel to study the effect of the unambiguous concatenation product of recognizable languages on the syntactic monoids of the languages involved. As a result of this study we obtain an algebraic characterization (originally due to Pin) of the closure of a variety of languages under Boolean operations and unambiguous concatenation, and a new proof of a theorem of Straubing characterizing the closure of a variety of languages under Boolean operations and concatenation. We also note some connections to the study of the dot-depth hierarchy.



Valid HTML 4.01!