The Degrees of Squares is an Atom

Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Hans Zantema

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

We answer an open question in the theory of degrees of infinite sequences with respect to transducibilityby finite-state transducers. An initial study of this partial order of degrees was carried out in [1], but many basic questions remain unanswered. One of the central questions concerns the existence of atom degrees, other than the degree of the ‘identity sequence’ 100101102103 · · ·. A degree is called an ‘atom’ if below it there is only the bottom degree 0, which consists of the ultimately periodic sequences. We show that also the degree of the ‘squares sequence’ 1001011041091016 · · · is an atom. As the main tool for this result we characterise the transducts of ‘spiralling’ sequences and their degrees. We use this to show that every transduct of a ‘polynomial sequence’ either is in 0 or can be transduced back to a polynomial sequence for a polynomial of the same order.
Original languageEnglish
Title of host publicationCombinatorics on Words - 10th International Conference, WORDS 2015, Proceedings
PublisherSpringer/Verlag
Pages109-121
Number of pages13
Volume9304
ISBN (Print)9783319236599
DOIs
Publication statusPublished - 2015
Event10th International Conference on Words, WORDS 2015 - Kiel, Germany
Duration: 14 Sep 201517 Sep 2015

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9304
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference10th International Conference on Words, WORDS 2015
CountryGermany
CityKiel
Period14/09/1517/09/15

Fingerprint Dive into the research topics of 'The Degrees of Squares is an Atom'. Together they form a unique fingerprint.

Cite this