论文标题
m-nearly k-通用词 - 调查西蒙一致性
m-Nearly k-Universal Words -- Investigating Simon Congruence
论文作者
论文摘要
确定西蒙一致性的索引是一个漫长的开放问题。如果$ u $和$ v $具有相同的分散因素，则称为Simon一致，这些因素是正确顺序的一部分，但不一定是连续的，例如，$ \ Mathtt {Oath} $是$ \ Mathtt {legarithm} $的散射因子。遵循分散因子$ k $ - 宇宙的想法，我们调查了$ m $ nearly $ k $ - 宇宙，即缺少$ m $长度$ k $的单词，W.R.T。西蒙一致。我们提供了完整的表征以及$ m = 1 $的一致性索引。对于$ m \ neq 1 $，如果此外，我们还会显示一些结果，如果$ w $是$（k-1）$ - 通用以及对不同$ m $的一些进一步见解。
Determining the index of the Simon congruence is a long outstanding open problem. Two words $u$ and $v$ are called Simon congruent if they have the same set of scattered factors, which are parts of the word in the correct order but not necessarily consecutive, e.g., $\mathtt{oath}$ is a scattered factor of $\mathtt{logarithm}$. Following the idea of scattered factor $k$-universality, we investigate $m$-nearly $k$-universality, i.e., words where $m$ scattered factors of length $k$ are absent, w.r.t. Simon congruence. We present a full characterisation as well as the index of the congruence for $m=1$. For $m\neq 1$, we show some results if in addition $w$ is $(k-1)$-universal as well as some further insights for different $m$.
