Sofic-Dyck shifts

详细信息    查看全文

• 作者：Marie-Pierre Bé ; al^a ; ^{beal@u-pem.fr" class="auth_mail" title="E-mail the corresponding author} ; Michel Blockelet^b ; ^{michel.blockelet@u-pec.fr" class="auth_mail" title="E-mail the corresponding author} ; Cǎtǎlin Dima^b ; ^{catalin.dima@u-pec.fr" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Dyck shift ; Markov&ndash ; Dyck shift ; Sofic-Dyck shift ; Sofic shift ; Symbolic dynamics ; Visibly pushdown automaton ; Visibly pushdown language ; Zeta function
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：4 January 2016
• 年：2016
• 卷：609
• 期：part_P1
• 页码：226-244
• 全文大小：582 K

文摘

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.