
The subword complexity \(p_w (n)\) of a word \(w\) is the function that maps \(n\) to the number of distinct length-\(n\) factors occurring in \(w\). A partial word is a word with a ``don't care'' symbol \(\diamond\) that matches every other symbol. The notion of subword complexity can be extended to partial words \(w\) by counting the total number of ordinary words that are compatible with length-\(n\) factors of \(w\). In this paper, the authors show that, for all integers \(h, N \geq 0\), there exist partial words \(w\) with \(h\) holes such that \(p_w (n) = n + 1\) for \(1 \leq n \leq N\). They also study the length of the shortest such words and the number of minimal words. They also consider similar questions where \(n + 1\) is replaced by \(2n\).
Subword complexity, Automata and formal languages; Combinatorics on words; Graph theory; Subword complexity; Feasible functions; Partial words; Sturmian words., Combinatorics on words, subword complexity, Applied Mathematics, Sturmian word, Sturmian words, Formal languages and automata, 004, Graph theory, Feasible functions, partial word, Discrete Mathematics and Combinatorics, Automata and formal languages, Partial words, Number-theoretic algorithms; complexity, ddc: ddc:004
Subword complexity, Automata and formal languages; Combinatorics on words; Graph theory; Subword complexity; Feasible functions; Partial words; Sturmian words., Combinatorics on words, subword complexity, Applied Mathematics, Sturmian word, Sturmian words, Formal languages and automata, 004, Graph theory, Feasible functions, partial word, Discrete Mathematics and Combinatorics, Automata and formal languages, Partial words, Number-theoretic algorithms; complexity, ddc: ddc:004
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
