Binary Patterns in Infinite Binary Words
Binary Patterns in Infinite Binary Words
复制标题
无限二进制单词中的二进制模式
DOI：
10.1007/3-540-45711-9_8
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
Sergio Salemi
中科院分区：
文献类型：
--
作者：
A. Restivo;Sergio Salemi
In this paper we study the setP(ω) of binary patterns that can occur in one infinite binary word ω, comparing it with the setF(ω) of factors of the word. Since the setP(ω) can be considered as an extension of the setF(ω), we first investigate how large is such extension, by introducing the parameter △(ω) that corresponds to the cardinality of the difference setP(ω) /F(ω). Some non trivial results about such parameter are obtained in the case of the Thue-Morse and the Fibonacci words. Since, in most cases, the parameter △(ω) is infinite, we introduce the pattern complexity of ω, which corresponds to the complexity of the languageP(ω). As a main result, we prove that there exist infinite words that have pattern complexity that grows more quickly than their complexity. We finally propose some problems and new research directions.
