In this work, we combine the research on (absent) scattered factors with the one of jumbled words. For instance, \(\texttt{wolf}\) is an absent scattered factor of \(\texttt{cauliflower}\) but since \(\texttt{lfow}\) , a jumbled (or abelian) version of \(\texttt{wolf}\) , is a scattered factor, \(\texttt{wolf}\) occurs as a jumbled scattered factor in \(\texttt{cauliflower}\) . A jumbled scattered factor u of a word w is constructed by letters of w with the only rule that the number of occurrences per letter in u is smaller than or equal to the one in w. We proceed to partition and characterise the set of jumbled scattered factors by the number of jumbled letters and use the latter as a measure. For this new class of words, we relate the folklore longest common subsequence (scattered factor) to the number of required jumbles. Further, we investigate the smallest possible number of jumbles alongside the jumbled scattered factor relation as well as Simon’s congruence from the point of view of jumbled scattered factors and jumbled universality.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Jumbled Scattered Factors

  • Pamela Fleischmann,
  • Annika Huch,
  • Melf Kammholz,
  • Tore Koß

摘要

In this work, we combine the research on (absent) scattered factors with the one of jumbled words. For instance, \(\texttt{wolf}\) is an absent scattered factor of \(\texttt{cauliflower}\) but since \(\texttt{lfow}\) , a jumbled (or abelian) version of \(\texttt{wolf}\) , is a scattered factor, \(\texttt{wolf}\) occurs as a jumbled scattered factor in \(\texttt{cauliflower}\) . A jumbled scattered factor u of a word w is constructed by letters of w with the only rule that the number of occurrences per letter in u is smaller than or equal to the one in w. We proceed to partition and characterise the set of jumbled scattered factors by the number of jumbled letters and use the latter as a measure. For this new class of words, we relate the folklore longest common subsequence (scattered factor) to the number of required jumbles. Further, we investigate the smallest possible number of jumbles alongside the jumbled scattered factor relation as well as Simon’s congruence from the point of view of jumbled scattered factors and jumbled universality.