×

Analysis of alternative digit sets for nonadjacent representations. (English) Zbl 1094.11007

For some integers \(x\) all positive integers can be written as \(\sum a_i2^i\), where \(a_i\in\{0,1,x\}\), and no two consecutive \(a_i\)’s are simultaneously different from zero. The authors construct transducers to convent binary expansions into such representations. Looking at left-to-right transducers show an exceptional set with interesting topological (fractal-type) properties. The cases where \(x=-1\) (classical) and \(x=3\) play a particular rôle.

MSC:

11A63 Radix representation; digital problems
28A78 Hausdorff and packing measures
68W40 Analysis of algorithms
90C35 Programming involving graphs or networks
94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Cook WJ, Cunningham WH, Pulleyblank WR, Schrijver A (1998) Combinatorial Optimization. New York: Wiley
[3] Edgar GA (1990) Measure, Topology, and Fractal Geometry. New York: Springer · Zbl 0727.28003
[4] Falconer K (1997) Techniques in Fractal Geometry. Chichester: Wiley · Zbl 0869.28003
[6] Graham RL, Knuth DE, Patashnik O (1994) Concrete Mathematics. A Foundation for Computer Science, 2nd ed. New York: Addison-Wesley · Zbl 0836.00001
[7] Heuberger C (2006) Hwang’s quasi-power-theorem in higher dimensions, in preparation
[12] Knuth DE (1998) Seminumerical Algorithms, 3rd ed. New York: Addison-Wesley · Zbl 0895.65001
[13] Lancaster P, Tismenetsky M (1985) The Theory of Matrices, 2nd ed. Orlando, FL: Academic Press · Zbl 0558.15001
[14] Muir JA, Stinson DR (2004) Alternative digit sets for nonadjacent representations. Lect Notes Comput Sci 3006, 306–319. Berlin: Springer · Zbl 1081.94031
[16] Prodinger H (2000) On binary representations of integers with digits , 0, 1, Integers 0, A08, available at http://www.integers-ejcnt.org/vol0.html. · Zbl 1088.11501
[18] Avoine G, Monnerat J, Peyrin Th (2004) Advances in alternative non-adjacent form representations. Lect Notes Comput Sci 3348, 260–274. Berlin: Springer · Zbl 1115.94004
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.