Skip to Main content Skip to Navigation
Conference papers

Generalized Dyck Shifts

Abstract : 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.
Document type :
Conference papers
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download
Contributor : Marie-Pierre Béal Connect in order to contact the contributor
Submitted on : Friday, May 11, 2018 - 3:57:07 PM
Last modification on : Saturday, January 15, 2022 - 3:57:47 AM
Long-term archiving on: : Tuesday, September 25, 2018 - 9:07:16 AM


Files produced by the author(s)


  • HAL Id : hal-01790046, version 1



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



Record views


Files downloads