Leírás
Combinatorics on words studies combinatorial properties of words (which are finite or infinite sequences of symbols) and analyses various patterns appearing in them. The notion of palindromes is a topic that often emerges in its research strands. In this talk some measures of the degree of ``palindromicity" of words will be presented (that is, how to classify words with respect to, very loosely said, which word is ``more palindromic" than another one). Several such approaches have been introduced and researched in the literature, and we here focus on two of them.
The first approach is the so-called \emph{palindromic defect}. Let $|\mathrm{Pal}(w)|$ denote the number of palindromic factors (contiguous subsequences) of a finite word $w$. It can be shown that $w$ has at most $|w|+1$ different palindromic factors, which motivates the definition of the palindromic defect: it is the difference $|w|+1-|\mathrm{Pal}(w)|$. This definition can be extended to infinite words in a natural way.
The second approach is the so-called \emph{MP-ratio} of a given $n$-ary word $w$ (where the abbreviation MP stands for minimal-palindromic). An $n$-ary word is called \emph{minimal-palindromic} if it does not contain palindromic subwords (not necessarily contiguous subsequences) of length greater than $\big\lceil\frac{|w|}n\big\rceil$. The MP-ratio of a given $n$-ary word $w$ is defined as the quotient $\frac{|rws|}{|w|}$, where $r$ and $s$ are such that the word $rws$ is minimal-palindromic and the length $|r|+|s|$ is the minimal possible.
After introducing the necessary background, there will be presented some recent results of the speaker and her coauthors on these two measures. Concerning the palindromic defect, we will introduce a class of words, named \emph{generalized highly potential words}, and analyze their significance within the frame of various questions regarding the palindromic defect, but also regarding some different notions.
Concerning the MP-ratio, the main result that will be presented is the demonstration that the MP-ratio is well-defined for words of any arity (the initial definition from the literature was provided only for the binary alphabet, and it was posed as an open problem whether the definition can be extended to larger alphabets). Besides that, there will be presented some further results toward the goal of finding the sharpest possible upper bound on the MP-ratio of words of a given arity.
This is a joint work with B. Ba\v si\'c, and partially a joint work with S. Ha\v cko and D. Popovi\'c.