Langages á un Compteur

摘要

Nous étudions les langages á un compteur, c'est-á-dire, les langages appartenant á Rocl, le cône rationnel engendré par D'1∗, le langage de semi-Dyck sur une lettre. Nous montrons que tout générateur de Rocl est bifidèle et qu'il existe un langage á un compteur qui domine tous les autres par transduction rationnelle préservant les longueurs. Nous établissons, ensuite, que le lemme d'itération des langages linéaires est presque vrai pour les langages á un compteur. Enfin, nous prouvons que Rocl ne contient aucune FAL non rationnelle et que, si Rocl est inclus dans la plus petite FAL contenant un cône rationnel L clos par union, alors Rocl est inclus dans L. De même, si Rocl est inclus dans la plus petite FAL close par substitution contenant un cone rationnel algébrique L, alors Rocl est inclus dans L.