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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/Congresprocedure › Conferentiebijdrage › Academic › peer review

8 Citaten (Scopus)

Samenvatting

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.

Originele taal-2	Engels
Titel	Combinatorics on Words: 10th International Conference, WORDS 2015
Plaats van productie	Amsterdam
Uitgeverij	Springer
Pagina's	109-121
Aantal pagina's	13
ISBN van elektronische versie	978-3-319-23660-5
ISBN van geprinte versie	978-3-319-23659-9
DOI's	https://doi.org/10.1007/978-3-319-23660-5_10
Status	Gepubliceerd - 2015
Evenement	10th international conference WORDS 2015 - Kiel, Duitsland Duur: 14 sep. 2015 → 17 sep. 2015

Publicatie series

Naam	Lecture Notes in Computer Science

Congres

Congres	10th international conference WORDS 2015
Land/Regio	Duitsland
Stad	Kiel
Periode	14/09/15 → 17/09/15

Toegang tot document

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

Citeer dit

@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 = "10th international conference WORDS 2015 ; 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

T2 - 10th international conference WORDS 2015

Y2 - 14 September 2015 through 17 September 2015

ER -