Some further results on squarefree arithmetic progressions in infinite words

被引：6

作者：

Currie, James ^{[1
]}

Harju, Tero ^{[2
]}

Ochem, Pascal ^{[3
]}

Rampersad, Narad ^{[1
]}

机构：

[1] Univ Winnipeg, Dept Math & Stat, Winnipeg, MB, Canada

[2] Univ Turku, Dept Math & Stat, Turku, Finland

[3] Univ Montpellier, CNRS, LIRMM, Montpellier, France

来源：

THEORETICAL COMPUTER SCIENCE | 2019年 / 799卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Squarefree word; Squarefree morphism; Automatic sequence; Thue word; Arithmetic progression;

D O I：

10.1016/j.tcs.2019.10.006

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In a recent paper, one of us posed three open problems concerning squarefree arithmetic progressions in infinite words. In this paper we solve these problems and prove some additional results. For instance, among other things, we show that there exists a squarefree word w over a ternary alphabet such that for every p >= 3, the subsequence of w indexed by the multiples of p contains a square. (C) 2019 Elsevier B.V. All rights reserved.

引用

页码：140 / 148

页数：9

共 16 条

[1]

Berstel J., 1979, SEM THEOR NOMBR 1978

[2]

Blanchet-Sadri F., 2014, INTEGERS, V14

[3]

BRANDENBURG FJ, 1983, THEOR COMPUT SCI, V23, P69, DOI 10.1016/0304-3975(88)90009-6

[4]

Braunholtz C., 1963, AM MATH MONTHLY, V70, P675

[5] MULTIDIMENSIONAL UNREPETITIVE CONFIGURATIONS [J].

CARPI, A .

THEORETICAL COMPUTER SCIENCE, 1988, 56 (02) :233-241

[6] SHARP CHARACTERIZATIONS OF SQUAREFREE MORPHISMS [J].

CROCHEMORE, M .

THEORETICAL COMPUTER SCIENCE, 1982, 18 (02) :221-226

[7]

Currie J., 2002, ELECTRON J COMB, V9

[8] Infinite ternary square-free words concatenated from permutations of a single word [J].

Currie, James .

THEORETICAL COMPUTER SCIENCE, 2013, 482 :1-8

[9]

Hall M., 1964, LECT MODERN MATH, V2, P42

[10] On square-free arithmetic progressions in infinite words [J].

Harju, Tero .

THEORETICAL COMPUTER SCIENCE, 2019, 770 :95-100

← 1 2 →