Greedy and lazy representations in negative base systems

Tomáš Hejda; Zuzana Masáková; Edita Pelantová

Kybernetika (2013)

  • Volume: 49, Issue: 2, page 258-279
  • ISSN: 0023-5954

Abstract

top
We consider positional numeration systems with negative real base - β , where β > 1 , and study the extremal representations in these systems, called here the greedy and lazy representations. We give algorithms for determination of minimal and maximal ( - β ) -representation with respect to the alternate order. We also show that both extremal representations can be obtained as representations in the positive base β 2 with a non-integer alphabet. This enables us to characterize digit sequences admissible as greedy and lazy ( - β ) -representation. Such a characterization allows us to study the set of uniquely representable numbers. In the case that β is the golden ratio and the Tribonacci constant, we give the characterization of digit sequences admissible as greedy and lazy ( - β ) -representation using a set of forbidden strings.

How to cite

top

Hejda, Tomáš, Masáková, Zuzana, and Pelantová, Edita. "Greedy and lazy representations in negative base systems." Kybernetika 49.2 (2013): 258-279. <http://eudml.org/doc/260585>.

@article{Hejda2013,
abstract = {We consider positional numeration systems with negative real base $-\beta $, where $\beta >1$, and study the extremal representations in these systems, called here the greedy and lazy representations. We give algorithms for determination of minimal and maximal $(-\beta )$-representation with respect to the alternate order. We also show that both extremal representations can be obtained as representations in the positive base $\beta ^2$ with a non-integer alphabet. This enables us to characterize digit sequences admissible as greedy and lazy $(-\beta )$-representation. Such a characterization allows us to study the set of uniquely representable numbers. In the case that $\beta $ is the golden ratio and the Tribonacci constant, we give the characterization of digit sequences admissible as greedy and lazy $(-\beta )$-representation using a set of forbidden strings.},
author = {Hejda, Tomáš, Masáková, Zuzana, Pelantová, Edita},
journal = {Kybernetika},
keywords = {numeration systems; lazy representation; greedy representation; negative base; unique representation; numeration systems; lazy representation; greedy representation; negative base; unique representation},
language = {eng},
number = {2},
pages = {258-279},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Greedy and lazy representations in negative base systems},
url = {http://eudml.org/doc/260585},
volume = {49},
year = {2013},
}

TY - JOUR
AU - Hejda, Tomáš
AU - Masáková, Zuzana
AU - Pelantová, Edita
TI - Greedy and lazy representations in negative base systems
JO - Kybernetika
PY - 2013
PB - Institute of Information Theory and Automation AS CR
VL - 49
IS - 2
SP - 258
EP - 279
AB - We consider positional numeration systems with negative real base $-\beta $, where $\beta >1$, and study the extremal representations in these systems, called here the greedy and lazy representations. We give algorithms for determination of minimal and maximal $(-\beta )$-representation with respect to the alternate order. We also show that both extremal representations can be obtained as representations in the positive base $\beta ^2$ with a non-integer alphabet. This enables us to characterize digit sequences admissible as greedy and lazy $(-\beta )$-representation. Such a characterization allows us to study the set of uniquely representable numbers. In the case that $\beta $ is the golden ratio and the Tribonacci constant, we give the characterization of digit sequences admissible as greedy and lazy $(-\beta )$-representation using a set of forbidden strings.
LA - eng
KW - numeration systems; lazy representation; greedy representation; negative base; unique representation; numeration systems; lazy representation; greedy representation; negative base; unique representation
UR - http://eudml.org/doc/260585
ER -

References

top
  1. Dajani, K., Kalle, Ch., Transformations generating negative β -expansions., Integers 11B (2011), A5, 1-18. MR3054424
  2. Dajani, K., Kraaikamp, C., 10.1016/S0723-0869(02)80010-X, Exposition. Math. 20 (2002), 4, 315-327. Zbl1030.11035MR1940010DOI10.1016/S0723-0869(02)80010-X
  3. Vries, M. de, Komornik, V., 10.1016/j.aim.2008.12.008, Adv. Math. 221 (2009), 2, 390-427. Zbl1166.11007MR2508926DOI10.1016/j.aim.2008.12.008
  4. Erdös, P., Joó, I., Komornik, V., Characterization of the unique expansions 1 = ∑ i = 1 ∞ q - n i and related problems., Bull. Soc. Math. France 118 (1990), 3, 377-390. MR1078082
  5. Ito, S., Sadahiro, T., Beta-expansions with negative bases., Integers 9 (2009), A22, 239-259. Zbl1191.11005MR2534912
  6. Kalle, Ch., Steiner, W., 10.1090/S0002-9947-2012-05362-1, Trans. Amer. Math. Soc. 364 (2012), 2281-2318. MR2888207DOI10.1090/S0002-9947-2012-05362-1
  7. Parry, W., 10.1007/BF02020954, Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416. Zbl0099.28103MR0142719DOI10.1007/BF02020954
  8. Pedicini, M., 10.1016/j.tcs.2004.11.002, Theoret. Comput. Sci. 332 (2005), 1-3, 313-336. Zbl1080.11009MR2122508DOI10.1016/j.tcs.2004.11.002
  9. Rényi, A., 10.1007/BF02020331, Acta Math. Acad. Sci. Hungar. 8 (1957), 477-493. Zbl0079.08901MR0097374DOI10.1007/BF02020331
  10. Schmidt, K., 10.1112/blms/12.4.269, Bull. London Math. Soc. 12 (1980), 4, 269-278. Zbl0494.10040MR0576976DOI10.1112/blms/12.4.269
  11. Thurston, W., Groups, tilings, and finite state automata., AMS Colloquium Lecture Notes, American Mathematical Society, Boulder, 1989. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.