The degree of squares is an atom

DOI10.1007/978-3-319-23660-5_10zbMATH Open1330.68154arXiv1506.00884OpenAlexW1748975720MaRDI QIDQ3449362FDOQ3449362

Authors: Jörg Endrullis, Clemens Grabmayer, Dimitri Hendriks, Hans Zantema 

Publication date: 4 November 2015

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: We answer an open question in the theory of degrees of infinite sequences with respect to transducibility by finite-state transducers. An initial study of this partial order of degrees was carried out in (Endrullis, Hendriks, Klop, 2011), 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' 1 0^0 1 0^1 1 0^2 1 0^3 .... 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' 1 0^0 1 0^1 1 0^4 1 0^9 1 0^{16} ... 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.

Full work available at URL: https://arxiv.org/abs/1506.00884

Recommendations

• Degrees of infinite words, polynomials and atoms
• scientific article; zbMATH DE number 3972194
• Degrees of Infinite Words, Polynomials and Atoms
• Transducer degrees: atoms, infima and suprema
• Degrees of asynchronously automaton transformations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Cites Work

• Degrees of streams
• The degree of squares is an atom
• Periodicity, morphisms, and matrices.
• Regularity-preserving relations
• Title not available (Why is that?)
• Undecidable Extensions of Monadic Second Order Successor Arithmetic

Cited In (7)

• Degrees of transducibility
• The degree of squares is an atom
• Transducer degrees: atoms, infima and suprema
• Finite transducers and rational transductions
• Degrees of infinite words, polynomials and atoms
• Ordering sequences by permutation transducers
• Degrees of Infinite Words, Polynomials and Atoms

This page was built for publication: The degree of squares is an atom

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3449362)