Discrete Mathematics & Theoretical Computer Science |
For a real number $β >1$, we say that a permutation $π$ of length $n$ is allowed (or realized) by the $β$-shift if there is some $x∈[0,1]$ such that the relative order of the sequence $x,f(x),\ldots,f^n-1(x)$, where $f(x)$ is the fractional part of $βx$, is the same as that of the entries of $π$ . Widely studied from such diverse fields as number theory and automata theory, $β$-shifts are prototypical examples of one-dimensional chaotic dynamical systems. When $β$ is an integer, permutations realized by shifts have been recently characterized. In this paper we generalize some of the results to arbitrary $β$-shifts. We describe a method to compute, for any given permutation $π$ , the smallest $β$ such that $π$ is realized by the $β$-shift.