We examine three permutations on Dyck words. The first one, α, is related to the Baker and Norine theorem on graphs, the second one, β, is the symmetry, and the third one is the composition of these two. The first two permutations are involutions and it is not difficult to compute the number of their fixed points, while the third one has cycles of different lengths. We show that the lengths of these cycles are odd numbers. This result allows us to give some information about the interplay between α and β , and a characterization of the fixed points of α∘β .

Barnabei, M., Bonetti, F., Castronuovo, N., Cori, R. (2016). Some permutations on Dyck words. THEORETICAL COMPUTER SCIENCE, 635, 51-63 [10.1016/j.tcs.2016.05.007].

Some permutations on Dyck words

BARNABEI, MARILENA;BONETTI, FLAVIO;CASTRONUOVO, NICCOLÒ;
2016

Abstract

We examine three permutations on Dyck words. The first one, α, is related to the Baker and Norine theorem on graphs, the second one, β, is the symmetry, and the third one is the composition of these two. The first two permutations are involutions and it is not difficult to compute the number of their fixed points, while the third one has cycles of different lengths. We show that the lengths of these cycles are odd numbers. This result allows us to give some information about the interplay between α and β , and a characterization of the fixed points of α∘β .
2016
Barnabei, M., Bonetti, F., Castronuovo, N., Cori, R. (2016). Some permutations on Dyck words. THEORETICAL COMPUTER SCIENCE, 635, 51-63 [10.1016/j.tcs.2016.05.007].
Barnabei, Marilena; Bonetti, Flavio; Castronuovo, Niccolò; Cori, Robert
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/566812
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 2
  • ???jsp.display-item.citation.isi??? 1
social impact