zbMATH — the first resource for mathematics

On the enumeration and generation of generalized Dyck words. (English) Zbl 0971.68090
Summary: We provide a new algebraic grammar for generalized Dyck languages as introduced by J. Labelle and Y.-N. Yeh [ibid. 82, No. 1, 1-6 (1990; Zbl 0723.05074)]. The study of these languages leads to the particular sublanguages of words without proper actors 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 \({3\over 2}\) slope Dyck paths.

68Q45 Formal languages and automata
68R15 Combinatorics on words
05A15 Exact enumeration problems, generating functions
Full Text: DOI