Abstract :
We provide a new algebraic grammar for generalized Dyck languages as introduced by Labelle and Yeh (Discrete Math. 82 (1990) 1–6). The study of these languages leads to the particular sublanguages of words without proper factors belonging to the studied language. A random generation scheme is shown for generalized Dyck languages, which leads to some asymptotic results. In the two-letter case, for which the words correspond to ‘rational slope Dyck paths’, more exact and asymptotic enumerative results are obtained, including the asymptotic average area to integer or 32 slope Dyck paths.
Résumé
Nous proposons une nouvelle grammaire algébrique engendrant les languages de Dyck généralisés introduits par Labelle et Yeh dans [7]. Leur étude suggère dʹintroduire des sous-langages des mots nʹayant aucun facteur propre dans le langage étudié, qui sont également algébriques. Nous proposons également une méthode de génération aléatoire des mots de ces langages, liée à des réultats asymptotiques d’énumération. Enfin, dans le cas des langages sur deux lettres (‘mots de Dyck à pente rationnelle’), nous obtenons dʹautres résultats d’énumération exacts ou asymptotiques, en particulier sur lʹaire moyenne des chemins de Dyck à pente entière ou 3/2
