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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01790046
Contributor : Marie-Pierre Béal <>
Submitted on : Friday, May 11, 2018 - 3:57:07 PM
Last modification on : Thursday, July 5, 2018 - 2:45:46 PM
Long-term archiving on : Tuesday, September 25, 2018 - 9:07:16 AM

File

generalizedDyckConf.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01790046, version 1

Citation

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

Share

Metrics

Record views

32

Files downloads

16