Gaps in the Thue-Morse word

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Standard

Gaps in the Thue-Morse word. / Spiegelhofer, Lukas.
in: Journal of the Australian Mathematical Society, Jahrgang 114.2023, Nr. 1, 25.02.2023, S. 110-144.

Publikationen: Beitrag in FachzeitschriftArtikelForschung(peer-reviewed)

Vancouver

Spiegelhofer L. Gaps in the Thue-Morse word. Journal of the Australian Mathematical Society. 2023 Feb 25;114.2023(1):110-144. doi: 10.1017/S1446788721000380

Author

Bibtex - Download

@article{e79e7c1d91b24a04ba5ce617893976e8,
title = "Gaps in the Thue-Morse word",
abstract = "The Thue–Morse sequence is a prototypical automatic sequence found in diverse areas of mathematics, and in computer science. We study occurrences of factors w within this sequence, or more precisely, the sequence of gaps between consecutive occurrences. This gap sequence is morphic; we prove that it is not automatic as soon as the length of w is at least 2 , thereby answering a question by J. Shallit in the affirmative. We give an explicit method to compute the discrepancy of the number of occurrences of the block 01 in the Thue–Morse sequence. We prove that the sequence of discrepancies is the sequence of output sums of a certain base- 2 transducer.",
author = "Lukas Spiegelhofer",
note = "Publisher Copyright: {\textcopyright} The Author(s), 2022. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.",
year = "2023",
month = feb,
day = "25",
doi = "10.1017/S1446788721000380",
language = "English",
volume = "114.2023",
pages = "110--144",
journal = "Journal of the Australian Mathematical Society",
issn = "1446-1811",
publisher = "Cambridge University Press",
number = "1",

}

RIS (suitable for import to EndNote) - Download

TY - JOUR

T1 - Gaps in the Thue-Morse word

AU - Spiegelhofer, Lukas

N1 - Publisher Copyright: © The Author(s), 2022. Published by Cambridge University Press on behalf of Australian Mathematical Publishing Association Inc.

PY - 2023/2/25

Y1 - 2023/2/25

N2 - The Thue–Morse sequence is a prototypical automatic sequence found in diverse areas of mathematics, and in computer science. We study occurrences of factors w within this sequence, or more precisely, the sequence of gaps between consecutive occurrences. This gap sequence is morphic; we prove that it is not automatic as soon as the length of w is at least 2 , thereby answering a question by J. Shallit in the affirmative. We give an explicit method to compute the discrepancy of the number of occurrences of the block 01 in the Thue–Morse sequence. We prove that the sequence of discrepancies is the sequence of output sums of a certain base- 2 transducer.

AB - The Thue–Morse sequence is a prototypical automatic sequence found in diverse areas of mathematics, and in computer science. We study occurrences of factors w within this sequence, or more precisely, the sequence of gaps between consecutive occurrences. This gap sequence is morphic; we prove that it is not automatic as soon as the length of w is at least 2 , thereby answering a question by J. Shallit in the affirmative. We give an explicit method to compute the discrepancy of the number of occurrences of the block 01 in the Thue–Morse sequence. We prove that the sequence of discrepancies is the sequence of output sums of a certain base- 2 transducer.

UR - http://www.scopus.com/inward/record.url?scp=85124048462&partnerID=8YFLogxK

U2 - 10.1017/S1446788721000380

DO - 10.1017/S1446788721000380

M3 - Article

VL - 114.2023

SP - 110

EP - 144

JO - Journal of the Australian Mathematical Society

JF - Journal of the Australian Mathematical Society

SN - 1446-1811

IS - 1

ER -