Automatic Sequences in Negative Bases and Proofs of Some Conjectures of Shevelev

被引：1

作者：

Shallit, Jeffrey ^{[1
]}

Shan, Sonja Linghui ^{[1
]}

Yang, Kai Hsiang ^{[1
]}

机构：

[1] Univ Waterloo, Sch Comp Sci, Waterloo, ON N2L 3G1, Canada

来源：

RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2023年 / 57卷

基金：

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

关键词：

Automatic sequence; representation in negative base; Fibonacci representation; combinatorics on words; logic; decision procedure; Thue-Morse sequence;

D O I：

10.1051/ita/2022011

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We discuss the use of negative bases in automatic sequences. Recently the theorem-prover Walnut has been extended to allow the use of base (-k) to express variables, thus permitting quantification over DOUBLE-STRUCK CAPITAL Z instead of N. This enables us to prove results about two-sided (bi-infinite) automatic sequences. We first explain the theory behind negative bases in Walnut. Next, we use this new version of Walnut to give a very simple proof of a strengthened version of a theorem of Shevelev. We use our ideas to resolve two open problems of Shevelev from 2017. We also reprove a 2000 result of Shut involving bi-infinite binary words.

引用

页数：22

共 27 条

[1]

Allouche J.P., 1999, Sequences and their applications, P1, DOI DOI 10.1007/978-1-4471-0551-0_1

[2]

Allouche J.-P., 2003, AUTOMATIC SEQUENCES, DOI DOI 10.1017/CBO9780511546563

[3]

Alpert H., 2009, Integers: Electron. J. Comb. Number Theory, V9, P745

[4]

Berstel J., 1979, PROC 6 INT C AUTOMAT, V71, P16

[5]

Berstel J, 1980, SEM INF THEOR, P57

[6]

Berstel J., 1995, NUMBER 20 PUBLICATIO

[7]

BUNDER MW, 1992, FIBONACCI QUART, V30, P111

[8] ON THE EXISTENCE OF SOLUTIONS FOR THE FRENKEL-KONTOROVA MODELS ON QUASI-CRYSTALS [J].

Du, Jianxing ;

Su, Xifeng .

ELECTRONIC RESEARCH ARCHIVE, 2021, 29 (06) :4177-4198

[9]

Grunwald V., 1885, GIORNALE MATEMATICHE, P203

[10]

Hajnal P., 2023, B ICA, P54

← 1 2 3 →