The degree of squares is an atom

DOI10.1007/978-3-319-23660-5_10MaRDI QIDQ3449362zbMATH OpenOpenAlexFDO

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)

Full work available at URL https://arxiv.org/abs/1506.00884, http://hdl.handle.net/2066/143773

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 5643878 (Why is no real title available?)
• Degrees of streams
• Periodicity, morphisms, and matrices.
• Regularity-preserving relations
• The degree of squares is an atom
• Undecidable Extensions of Monadic Second Order Successor Arithmetic

Cited in

(7)

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

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)