Morphic words, Beatty sequences and integer images of the Fibonacci language

DOI10.1016/J.TCS.2019.12.036MaRDI QIDQ2290645zbMATH OpenOpenAlexWikidataFDO

Authors F. Michel Dekking

Publication date 29 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

Frobenius problemmorphic wordgolden mean languageHD0L-systemiterated Beatty sequence

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Continued fractions (11A55) Special sequences and polynomials (11B83) Grammars and rewriting systems (68Q42) Combinatorics on words (68R15)

Abstract: Morphic words are letter-to-letter images of fixed points $x$ of morphisms on finite alphabets. There are situations where these letter-to-letter maps do not occur naturally, but have to be replaced by a morphism. We call this a decoration of $x$. Theoretically, decorations of morphic words are again morphic words, but in several problems the idea of decorating the fixed point of a morphism is useful. We present two of such problems. The first considers the so called $AA$ sequences, where $alpha$ is a quadratic irrational, $A$ is the Beatty sequence defined by $A(n)=lflooralphanfloor$, and $AA$ is the sequence $(A(A(n)))$. The second example considers homomorphic embeddings of the Fibonacci language into the integers, which turns out to lead to generalized Beatty sequences with terms of the form $V(n)=plflooralphanfloor+qn+r$, where $p,q$ and $r$ are integers.

Recommendations

• scientific article; zbMATH DE number 993516
• Morphic words and equidistributed sequences
• Some properties of the Fibonacci sequence on an infinite alphabet
• On Beatty's theorem, Wythoff's sequences and Fibonacci words
• Generalized Beatty sequences and complementary triples

Cites work

• scientific article; zbMATH DE number 1375592 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3394141 (Why is no real title available?)
• scientific article; zbMATH DE number 3402695 (Why is no real title available?)
• A remark on morphic sturmian words
• A simple characterization of Sturm numbers
• A two-parameter family of an extension of Beatty sequences
• Automatic Sequences
• Further results on iterated beatty functions
• Generalized Beatty sequences and complementary triples
• Generalized Wythoff arrays, shuffles and interspersions
• Iterated Floor Function, Algebraic Numbers, Discrete Chaos, Beatty Subsequences, Semigroups
• Morphisms, Symbolic sequences, and their Standard Forms
• On functions expressible as words on a pair of Beatty sequences
• Sturmian images of non Sturmian words and standard morphisms
• Substitution dynamical systems. Spectral analysis
• Substitution invariant cutting sequences
• The Frobenius problem for homomorphic embeddings of languages into the integers
• The equality problem for infinite words generated by primitive morphisms

Cited in

(4)

• The structure of Zeckendorf expansions
• On some conjectures of P. Barry
• Permutations of \(\mathbb{N}\) generated by left-right filling algorithms
• The sum of digits functions of the Zeckendorf and the base phi expansions

This page was built for publication: Morphic words, Beatty sequences and integer images of the Fibonacci language

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