1. Quasi-periodic β-expansions and cut languages
- Author
-
Petr Savický and Jiří Šíma
- Subjects
Rational number ,General Computer Science ,010102 general mathematics ,02 engineering and technology ,Base (topology) ,01 natural sciences ,Theoretical Computer Science ,Combinatorics ,Unit circle ,Integer ,Tail sequence ,Field extension ,0202 electrical engineering, electronic engineering, information engineering ,020201 artificial intelligence & image processing ,0101 mathematics ,Algebraic number ,Finite set ,Mathematics - Abstract
Motivated by the analysis of neural net models between integer and rational weights, we introduce a so-called cut language over a real digit alphabet, which contains finite β-expansions (i.e. base-β representations) of the numbers less than a given threshold. We say that an infinite β-expansion is eventually quasi-periodic if its tail sequence formed by the numbers whose representations are obtained by removing leading digits, contains an infinite constant subsequence. We prove that a cut language is regular iff its threshold is a quasi-periodic number whose all β-expansions are eventually quasi-periodic, by showing that altogether they have a finite number of tail values. For algebraic bases β, we prove that there is an eventually quasi-periodic β-expansion with an infinite number of tail values iff there is a conjugate of β on the unit circle. For transcendental β combined with algebraic digits, a β-expansion is eventually quasi-periodic iff it has a finite number of tail values. For a Pisot base β and digits from the smallest field extension Q ( β ) over rational numbers including β, we show that any number from Q ( β ) is quasi-periodic. In addition, we achieve a dichotomy that a cut language is either regular or non-context-free and we show that any cut language with rational parameters is context-sensitive.
- Published
- 2018