The degree of squares is an atom

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

doi:10.1007/978-3-319-23660-5_10

The degree of squares is an atom

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

Formal System Analysis

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	Combinatorics on Words: 10th International Conference, WORDS 2015
Place of Publication	Amsterdam
Publisher	Springer
Pages	109-121
Number of pages	13
ISBN (Electronic)	978-3-319-23660-5
ISBN (Print)	978-3-319-23659-9
DOIs	https://doi.org/10.1007/978-3-319-23660-5_10
Publication status	Published - 2015
Event	10th international conference WORDS 2015 - Kiel, Germany Duration: 14 Sep 2015 → 17 Sep 2015

Publication series

Name	Lecture Notes in Computer Science

Conference

Conference	10th international conference WORDS 2015
Country	Germany
City	Kiel
Period	14/09/15 → 17/09/15

Access to Document

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

Cite this

@inproceedings{5ccf13d80ad84e55aad1547f8c363aaf,

title = "The degree of squares is an atom",

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 {\textquoteleft}identity sequence{\textquoteright} 100101102103⋯ . A degree is called an {\textquoteleft}atom{\textquoteright} 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 {\textquoteleft}squares sequence{\textquoteright} 1001011041091016⋯ is an atom.As the main tool for this result we characterise the transducts of {\textquoteleft}spiralling{\textquoteright} sequences and their degrees. We use this to show that every transduct of a {\textquoteleft}polynomial sequence{\textquoteright} either is in 00 or can be transduced back to a polynomial sequence for a polynomial of the same order.",

author = "J. Endrullis and C.A. Grabmayer and D. Hendriks and H. Zantema",

year = "2015",

doi = "10.1007/978-3-319-23660-5_10",

language = "English",

isbn = "978-3-319-23659-9",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "109--121",

booktitle = "Combinatorics on Words: 10th International Conference, WORDS 2015",

address = "Germany",

note = "null ; Conference date: 14-09-2015 Through 17-09-2015",

}

TY - GEN

T1 - The degree of squares is an atom

AU - Endrullis, J.

AU - Grabmayer, C.A.

AU - Hendriks, D.

AU - Zantema, H.

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

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

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

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

M3 - Conference contribution

SN - 978-3-319-23659-9

T3 - Lecture Notes in Computer Science

SP - 109

EP - 121

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

PB - Springer

CY - Amsterdam

Y2 - 14 September 2015 through 17 September 2015

ER -