|logo_uqam_couleur-blanc.svg|UQAM, Université du Québec à Montréal|38


Calendrier des événements


Séminaire du LaCIM : «$k$-abelian equivalence - an equivalence relation inbetween the equality and the abelian equality»

Conférencier: Juhani Karhumäki, Université de Turku

Abstract: Two words $u$ and $v$ are $k$-abelian equivalent if, for each $w$ of length at most $k$, the number of occurrences of $w$ in $u$ coincides to that in $v$. The $k$-abelian equivalence is a natural equivalence relation, in fact a congruence, between the equality and the abelian equality. Topics we consider in this lecture are the avoidability of patterns, the palindromicity, and different types of complexity issues, in particular the number of the equivalence classes and the fluctuation of the complexity function of infinite words. We show that the set of minimal elements of the equivalence classes is a rational set. Consequently, for each parameter $k$ and alphabet size $m$, the numbers of equivalence classes of words of length $n$ form a rational sequence. Given $k$ and $m$ this sequence is algorithmically computable, but in practice only on very small values of the parameters.

Date / heure

Débute à 


201, avenue du Président-Kennedy
Montréal (QC) Canada  H2X 2J6


Site Web


  • Google Agenda
  • Yahoo
  • iCal
  • Imprimer
Consulté 4 fois   ·   Modifier
Retour en haut de page