TY - GEN

T1 - The Degrees of Squares is an Atom

AU - Endrullis, Jörg

AU - Grabmayer, Clemens

AU - Hendriks, Dimitri

AU - Zantema, Hans

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

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

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

U2 - 10.1007/978-3-319-23660-5_10

DO - 10.1007/978-3-319-23660-5_10

M3 - Conference contribution

SN - 9783319236599

VL - 9304

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 109

EP - 121

BT - Combinatorics on Words - 10th International Conference, WORDS 2015, Proceedings

PB - Springer/Verlag

T2 - 10th International Conference on Words, WORDS 2015

Y2 - 14 September 2015 through 17 September 2015

ER -