Factor-balanced S-adic languages

DOI10.1016/J.TCS.2024.114535arXiv2211.14076OpenAlexW4309987952MaRDI QIDQ6129704FDOQ6129704

Authors:

Publication date: 17 April 2024

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

Abstract: A set of words, also called a language, is letter-balanced if the number of occurrences of each letter only depends on the length of the word, up to a constant. Similarly, a language is factor-balanced if the difference of the number of occurrences of any given factor in words of the same length is bounded. The most prominent example of a letter-balanced but not factor-balanced language is given by the Thue-Morse sequence. We establish connections between the two notions, in particular for languages given by substitutions and, more generally, by sequences of substitutions. We show that the two notions essentially coincide when the sequence of substitutions is proper. For the example of Thue-Morse-Sturmian languages, we give a full characterisation of factor-balancedness.

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

Recommendations

• Languages under substitutions and balanced words
• Balanced words
• scientific article; zbMATH DE number 148020
• Generalized balances in Sturmian words
• Balanced words and dynamical systems

zbMATH Keywords

balancednesssubstitutionmorphismThue-Morse sequenceSturmian word\(S\)-adic shift

Mathematics Subject Classification ID

Theory of computing (68Qxx)

This page was built for publication: Factor-balanced \(S\)-adic languages

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