Word Complexity And Repetitions In Words
Word Complexity And Repetitions In Words
复制标题
单词复杂性和单词重复
DOI：
10.1142/s0129054104002297
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Kaizhong Zhang
中科院分区：
文献类型：
--
作者：
Lucian Ilie;Sheng Yu;Kaizhong Zhang
通过数据压缩和单词组合的想法，我们引入了单词的复杂度度量，称为重复的复杂性，该单词的重复数量是W，R（W）的重复性。通过重复应用以下步骤来存储w：n连续出现W的u ... u的u u的u u的u被存储为（u，n）。复杂性，子和lempel-ziv复杂性，我们始终具有r（w）≥lz（w），甚至可能是前者是线性的，而后者仅是对数的；通过迭代的形态获得。无限的单词α最终等同于：（i），（ii）和（iii）。精度复杂性保持开放。
With ideas from data compression and combinatorics on words, we introduce a complexity measure for words, called repetition complexity, which quantifies the amount of repetition in a word. The repetition complexity of w, R(w), is defined as the smallest amount of space needed to store w when reduced by repeatedly applying the following procedure: n consecutive occurrences uu…u of the same subword u of w are stored as (u,n). The repetition complexity has interesting relations with well-known complexity measures, such as subword complexity, SUB, and Lempel-Ziv complexity, LZ. We have always R(w)≥LZ(w) and could even be that the former is linear while the latter is only logarithmic; e.g., this happens for prefixes of certain infinite words obtained by iterated morphisms. An infinite word α being ultimately periodic is equivalent to: (i) , (ii) , and (iii) . De Bruijn words, well known for their high subword complexity, are shown to have almost highest repetition complexity; the precise complexity remains open. R(w) can be computed in time and it is open, and probably very difficult, to find fast algorithms.