Topological invariants for words of linear factor complexity

被引:0
作者
Bell, Jason P. [1 ]
机构
[1] Univ Waterloo, Dept Pure Math, Waterloo, ON N2L 3G1, Canada
基金
加拿大自然科学与工程研究理事会;
关键词
Combinatorics on words; Complexity; Recurrent words; Topology;
D O I
10.1016/j.aam.2022.102372
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Given a finite alphabet Sigma and a right-infinite word w over the alphabet Sigma, we construct a topological space Rec(w) consisting of all right-infinite recurrent words whose factors are all factors of w, where we work up to an equivalence in which two words are equivalent if they have the exact same set of factors (finite contiguous subwords). We show that Rec(w) can be endowed with a natural topology and we show that if w is word of linear factor complexity then Rec(w) is a finite topological space. In addition, we note that there are examples which show that if f : N -+ N is a function that tends to infinity as n -+ infinity then there is a word whose factor complexity function is O(nf(n)) such that Rec(w) is an infinite set. Finally, we pose a realization problem: which finite topological spaces can arise as Rec(w) for a word of linear factor complexity?
引用
收藏
页数:18
相关论文
共 17 条
  • [1] Allouche J.P., 2003, Automatic Sequences: Theory, Applications, Generalizations, DOI DOI 10.1017/CBO9780511546563
  • [2] Avgustinovich S.V., 2000, P INT C WORDS LANGUA, P51
  • [3] Bell J., PREPRINT
  • [4] Bell J, 2018, TRENDS MATH, P143, DOI 10.1007/978-3-319-69152-7_4
  • [5] The prime spectrum of algebras of quadratic growth
    Bell, Jason P.
    Smoktunowicz, Agata
    [J]. JOURNAL OF ALGEBRA, 2008, 319 (01) : 414 - 431
  • [6] Berstel 3Jean, 2009, CRM Monograph Series, V27
  • [7] Complexity and special factors
    Cassaigne, J
    [J]. BULLETIN OF THE BELGIAN MATHEMATICAL SOCIETY-SIMON STEVIN, 1997, 4 (01) : 67 - 88
  • [8] Cassaigne J., 1996, Developments in Language Theory II. At the Crossroads of Mathematics, Computer Science and Biology, P25
  • [9] Cyclic complexity of words
    Cassaigne, Julien
    Fici, Gabriele
    Sciortino, Marinella
    Zamboni, Luca Q.
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES A, 2017, 145 : 36 - 56
  • [10] ENUMERATION AND DECIDABLE PROPERTIES OF AUTOMATIC SEQUENCES
    Charlier, Emilie
    Rampersad, Narad
    Shallit, Jeffrey
    [J]. INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (05) : 1035 - 1066