Minimal expansions in redundant number systems: Fibonacci bases and greedy algorithms (Q2567414): Difference between revisions

Let \(\{G_j\}\) denote a sequence of integers. The cost of the (redundant) digit expansion \(n= \sum_{j\geq 0}\varepsilon_j G_j, \varepsilon_j\in {\mathbb Z}\) is defined as \[ c({\mathbf \varepsilon}(n))= \sum_{j\geq 0}| \varepsilon_j|. \] In the present paper minimal expansions with respect to two base sequences are examined. In part one \(G_j=F_j\), where \(F_j\) denotes the \(j\)th term of the Fibonacci sequence. A sequence \({\mathbf \varepsilon}=(\dots,\varepsilon_2,\varepsilon_1)\in \{0,\pm 1\}^{\mathbb N}\) with finitely many nonzero elements is called admissible, if \(\varepsilon_1=0\) and none of the patterns \((-1,1),(1,1),(-1,0,1),(1,0,1),(1,0,0,1)\) or their negatives appear as subsequences of \(\mathbf \varepsilon\). An admissible sequence \({\mathbf\varepsilon}\) is called an admissible expansion of an integer \(n\), if \(n=\sum_{j\geq 1}\varepsilon_j F_j\). Then there is a unique admissible expansion of every integer \(n\). Moreover it is minimal with respect to the cost function and can be calculated by a greedy algorithm and it cannot be calculated by a deterministic transducer from right to left. However, it is possible to calculate some minimal expansion from right to left. In part two some result about the Fibonacci expansion is ported back to the \(q\)-ary case, i.e. when \(G_j=q^j\) for a fixed integer \(q\geq 2\). It is proved that the symmetric signed digit expansion can be computed by a greedy algorithm.