Generalized Dyck Shifts

Marie-Pierre Béal (1) , Pavel Heller (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We introduce a new class of subshifts of sequences, called generalized Dyck shifts, which extends the class of Dyck shifts introduced by Krieger. The finite factors of these shifts are factors of generalized Dyck words. Generalized Dyck words were introduced by Labelle and Yeh who exhibited unambiguous algebraic grammars generating these context-free languages. Other unambiguous algebraic grammars for generalized Dyck languages were found by Duchon. We define a coding of periodic patterns of generalized Dyck shifts which allows to compute their zeta function. We prove that the zeta function of a generalized Dyck shift is the commutative image of the generating function of an unambiguous context-free language and is thus an N-algebraic series.

Domaines: Informatique et langage [cs.CL]

Marie-Pierre Béal, Pavel Heller. Generalized Dyck Shifts . CSR 2017 , 2017, Kazan, Russia. pp.99-111. ⟨hal-01790046⟩