The degree of squares is an atom

J. Endrullis, C.A. Grabmayer, D. Hendriks, H. Zantema

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

5 Citations (Scopus)

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 00 , 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 00 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
Place of PublicationAmsterdam
PublisherSpringer
Pages109-121
Number of pages13
ISBN (Electronic)978-3-319-23660-5
ISBN (Print)978-3-319-23659-9
DOIs
Publication statusPublished - 2015
Event10th international conference WORDS 2015 - Kiel, Germany
Duration: 14 Sep 201517 Sep 2015

Publication series

NameLecture Notes in Computer Science

Conference

Conference10th international conference WORDS 2015
CountryGermany
CityKiel
Period14/09/1517/09/15

Cite this