Shifts of k-nested sequences

Marie-Pierre Béal (1) , Pavel Heller (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

We introduce a new class of subshifts of sequences, called k-graph shifts, which expresses nested constraints on k symbols instead of on two symbols like for Dyck shifts. These shifts share many properties with Markov-Dyck shifts but are generally not conjugate to them. We prove that they are conjugate to sofic-Dyck shifts. We give a computation of the multivariate zeta function for this class of shifts.

Mots clés: Dyck shifts; Markov-Dyck shifts; sofic-Dyck shifts; sofic shifts; symbolic dynamics; visibly-pushdown languages; zeta function

Domaines: Informatique et langage [cs.CL]

Marie-Pierre Béal, Pavel Heller. Shifts of k-nested sequences . Theoretical Computer Science, 2017, 658 (A), pp.18-26. ⟨10.1016/j.tcs.2016.06.041⟩. ⟨hal-01790002⟩