Constructing partial words with subword complexities not achievable by full words

详细信息	查看全文 | 推荐本文 |

• 作者：F. Blanchet-Sadri^a ; ^{blanchet@uncg.edu} ; Aleksandar Chakarov^b ; Lucas Manuelli^c ; Jarett Schwartz^d ; Slater Stich^c
• 关键词：Automata and formal languages ; Combinatorics on words ; Partial words ; Subword complexity ; Polynomial complexity ; Intermediate complexity
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：11 May, 2012
• 卷：432
• 期：Complete
• 页码：21-27
• 文件大小：228 K

摘要

Partial words are sequences over a finite alphabet that may contain wildcard symbols, called holes, which match, or are compatible with, all letters in the alphabet ((full) words are just partial words without holes). The subword complexity function of a partial word over a finite alphabet assigns to each positive integer, , the number, , of distinct full words over that are compatible with factors of length of . In this paper, with the help of our so-called hole functions, we construct infinite partial words such that for any real number . In addition, these partial words have the property that there exist infinitely many non-negative integers satisfying . Combining these results with earlier ones on full words, we show that this represents a class of subword complexity functions not achievable by full words. We also construct infinite partial words with intermediate subword complexity, that is, between polynomial and exponential.