Sofic-Dyck shifts

Abstract : We define the class of sofic-Dyck shifts which extends the class of Markov-Dyck shifts introduced by Inoue, Krieger and Matsumoto. Sofic-Dyck shifts are shifts of sequences whose finite factors form unambiguous context-free languages. We show that they correspond exactly to the class of shifts of sequences whose sets of factors are visibly pushdown languages. We give an expression of the zeta function of a sofic-Dyck shift.
Document type :
Journal articles
Complete list of metadatas

Cited literature [39 references]  Display  Hide  Download

https://hal-upec-upem.archives-ouvertes.fr/hal-01801266
Contributor : Marie-Pierre Béal <>
Submitted on : Monday, May 28, 2018 - 12:57:00 PM
Last modification on : Friday, October 4, 2019 - 1:35:20 AM
Long-term archiving on: Wednesday, August 29, 2018 - 1:36:04 PM

File

soficDyckFinal.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Marie-Pierre Béal, Michel Blockelet, Catalin Dima. Sofic-Dyck shifts. Theoretical Computer Science, Elsevier, 2016, 609, pp.226 - 244. ⟨10.1016/j.tcs.2015.09.027⟩. ⟨hal-01801266⟩

Share

Metrics

Record views

68

Files downloads

90