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

DOI10.1016/J.TCS.2019.12.036zbMATH Open1447.68012arXiv1909.13208OpenAlexW2999288959WikidataQ126402363 ScholiaQ126402363MaRDI QIDQ2290645FDOQ2290645

Authors: F. Michel Dekking 

Publication date: 29 January 2020

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

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.

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

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

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)

Cites Work

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

Cited In (4)

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

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)