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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2016, 609, pp.226 - 244. 〈10.1016/j.tcs.2015.09.027〉
Liste complète des métadonnées

Littérature citée [39 références]  Voir  Masquer  Télécharger

https://hal-upec-upem.archives-ouvertes.fr/hal-01801266
Contributeur : Marie-Pierre Béal <>
Soumis le : lundi 28 mai 2018 - 12:57:00
Dernière modification le : jeudi 5 juillet 2018 - 14:45:54
Document(s) archivé(s) le : mercredi 29 août 2018 - 13:36:04

Fichier

soficDyckFinal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

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〉

Partager

Métriques

Consultations de la notice

23

Téléchargements de fichiers

16