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

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

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 |