论文标题
k-local单词的阻塞序列
Blocksequences of k-local Words
论文作者
论文摘要
单词的局部性是Day等人提出的相对年轻的结构复杂度度量。在2017年，为了定义具有变量的模式类，可以在多项式时间内匹配。用于计算单词局部性的主要工具称为标记序列：以相应顺序出现的不同字母的顺序。一旦定义了标记序列，单词的字母将以步骤标记：在标记步骤中，标记序列的ITH字母的所有出现都会标记。因此，在每个标记步骤之后，单词可以看作是一系列标记字母的序列，该字母被非标记字母块隔开。通过跟踪通过标记序列定义的标记，通过标记块的演变来定义相应标记序列的块序列。我们首先表明共享相同块序列的单词仅是松散连接的，因此我们考虑扩展块序列的更强烈的概念，该概念存储了有关每个单个标记块形式的其他信息。在这种情况下，我们为单词提供了一系列共享扩展区块序列的组合结果。
The locality of words is a relatively young structural complexity measure, introduced by Day et al. in 2017 in order to define classes of patterns with variables which can be matched in polynomial time. The main tool used to compute the locality of a word is called marking sequence: an ordering of the distinct letters occurring in the respective order. Once a marking sequence is defined, the letters of the word are marked in steps: in the ith marking step, all occurrences of the ith letter of the marking sequence are marked. As such, after each marking step, the word can be seen as a sequence of blocks of marked letters separated by blocks of non-marked letters. By keeping track of the evolution of the marked blocks of the word through the marking defined by a marking sequence, one defines the blocksequence of the respective marking sequence. We first show that the words sharing the same blocksequence are only loosely connected, so we consider the stronger notion of extended blocksequence, which stores additional information on the form of each single marked block. In this context, we present a series of combinatorial results for words sharing the extended blocksequence.
