Substitutions, abstract number systems and the space filling property
Clemens Fuchs[1]; Robert Tijdeman[2]
- [1] ETH Zürich Departement Mathematik Rämistrasse 101 8092 Zürich (Switzerland)
- [2] Universiteit Leiden Mathematisch Instituut Niels Bohrweg 1 2300 RA Leiden (The Netherlands)
Annales de l’institut Fourier (2006)
- Volume: 56, Issue: 7, page 2345-2389
- ISSN: 0373-0956
Access Full Article
topAbstract
topHow to cite
topFuchs, Clemens, and Tijdeman, Robert. "Substitutions, abstract number systems and the space filling property." Annales de l’institut Fourier 56.7 (2006): 2345-2389. <http://eudml.org/doc/10207>.
@article{Fuchs2006,
abstract = {In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo $1$ and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.},
affiliation = {ETH Zürich Departement Mathematik Rämistrasse 101 8092 Zürich (Switzerland); Universiteit Leiden Mathematisch Instituut Niels Bohrweg 1 2300 RA Leiden (The Netherlands)},
author = {Fuchs, Clemens, Tijdeman, Robert},
journal = {Annales de l’institut Fourier},
keywords = {Substitutions; limit word; discretisation of the hyperplane; lattices; automata; abstract number systems; substitutions; discretization of the hyperplane; space filling},
language = {eng},
number = {7},
pages = {2345-2389},
publisher = {Association des Annales de l’institut Fourier},
title = {Substitutions, abstract number systems and the space filling property},
url = {http://eudml.org/doc/10207},
volume = {56},
year = {2006},
}
TY - JOUR
AU - Fuchs, Clemens
AU - Tijdeman, Robert
TI - Substitutions, abstract number systems and the space filling property
JO - Annales de l’institut Fourier
PY - 2006
PB - Association des Annales de l’institut Fourier
VL - 56
IS - 7
SP - 2345
EP - 2389
AB - In this paper we study multi-dimensional words generated by fixed points of substitutions by projecting the integer points on the corresponding broken halfline. We show for a large class of substitutions that the resulting word is the restriction of a linear function modulo $1$ and that it can be decided whether the resulting word is space filling or not. The proof uses lattices and the abstract number system associated with the substitution.
LA - eng
KW - Substitutions; limit word; discretisation of the hyperplane; lattices; automata; abstract number systems; substitutions; discretization of the hyperplane; space filling
UR - http://eudml.org/doc/10207
ER -
References
top- Shigeki Akiyama, Pisot numbers and greedy algorithm, Number theory (Eger, 1996) (1998), 9-21, de Gruyter, Berlin Zbl0919.11063MR1628829
- Shigeki Akiyama, Self affine tiling and Pisot numeration system, Number theory and its applications (Kyoto, 1997) 2 (1999), 7-17, Kluwer Acad. Publ., Dordrecht Zbl0999.11065MR1738803
- Shigeki Akiyama, Cubic Pisot units with finite beta expansions, Algebraic number theory and Diophantine analysis (Graz, 1998) (2000), 11-26, de Gruyter, Berlin Zbl1001.11038MR1770451
- Shigeki Akiyama, Jörg M. Thuswaldner, A survey on topological properties of tiles related to number systems, Geom. Dedicata 109 (2004), 89-105 Zbl1073.37017MR2113188
- Pierre Arnoux, Shunji Ito, Pisot substitutions and Rauzy fractals, Bull. Belg. Math. Soc. Simon Stevin 8 (2001), 181-207 Zbl1007.37001MR1838930
- Pierre Arnoux, G. Rauzy, Représentation géométrique de suites de complexité , Bull. Soc. Math. France 119 (1991), 199-215 Zbl0789.28011MR1116845
- Directions in mathematical quasicrystals, 13 (2000), BaakeMichaelM., Providence, RI Zbl0955.00025MR1798986
- R. B. Bapat, T. E. S. Raghavan, Nonnegative matrices and applications, 64 (1997), Cambridge University Press, Cambridge Zbl0879.15015MR1449393
- Valérie Berthé, Michel Rigo, Abstract numeration systems and tilings, Mathematical foundations of computer science 2005 3618 (2005), 131-143, Springer, Berlin Zbl1156.68443MR2237364
- Valérie Berthé, Anne Siegel, Tilings associated with beta-numeration and substitutions, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005) Zbl1139.37008MR2191748
- Valérie Berthé, Robert Tijdeman, Lattices and multi-dimensional words, Theoret. Comput. Sci. 319 (2004), 177-202 Zbl1068.37005MR2074953
- Valérie Berthé, Laurent Vuillon, Suites doubles de basse complexité, J. Théor. Nombres Bordeaux 12 (2000), 179-208 Zbl1018.37010MR1827847
- Valérie Berthé, Laurent Vuillon, Tilings and rotations on the torus: a two-dimensional generalization of Sturmian sequences, Discrete Math. 223 (2000), 27-53 Zbl0970.68124MR1782038
- Valérie Berthé, Laurent Vuillon, Palindromes and two-dimensional Sturmian sequences, J. Autom. Lang. Comb. 6 (2001), 121-138 Zbl1002.11026MR1828855
- Anne Bertrand, Développements en base de Pisot et répartition modulo , C. R. Acad. Sci. Paris Sér. A-B 285 (1977), A419-A421 Zbl0362.10040MR447134
- V. Canterini, Connectedness of geometric representation of substitutions of Pisot type, Bull. Belg. Math. Soc. Simon Stevin 10 (2003), 77-89 Zbl1031.37015MR2032327
- Vincent Canterini, Anne Siegel, Automate des préfixes-suffixes associé à une substitution primitive, J. Théor. Nombres Bordeaux 13 (2001), 353-369 Zbl1071.37011MR1879663
- Vincent Canterini, Anne Siegel, Geometric representation of substitutions of Pisot type, Trans. Amer. Math. Soc. 353 (2001), 5121-5144 (electronic) Zbl1142.37302MR1852097
- Jean-Marie Dumont, Alain Thomas, Systemes de numeration et fonctions fractales relatifs aux substitutions, Theoret. Comput. Sci. 65 (1989), 153-169 Zbl0679.10010MR1020484
- Hiromi Ei, Shunji Ito, Tilings from some non-irreducible, Pisot substitutions, Discrete Math. Theor. Comput. Sci. 7 (2005), 81-121 (electronic) Zbl1153.37323MR2164061
- Hiromi Ei, Shunji Ito, H. Rao, Atomic surfaces, tilings and coincidences II. Reducible case Zbl1119.52013
- Samuel Eilenberg, Automata, languages, and machines. Vol. A, (1974), Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York Zbl0317.94045MR530382
- Jan-Hendrik Evertse, On the norm form inequality , Publ. Math. Debrecen 56 (2000), 337-374 Zbl0961.11009MR1765986
- Christiane Frougny, Boris Solomyak, Finite beta-expansions, Ergodic Theory Dynam. Systems 12 (1992), 713-723 Zbl0814.68065MR1200339
- Peter J. Grabner, Michel Rigo, Additive functions with respect to numeration systems on regular languages, Monatsh. Math. 139 (2003), 205-219 Zbl1125.11008MR1994380
- S. Ito, H. Rao, Atomic surfaces, tilings and coincidence I. Irreducible case, Israel J. Math. 153 (2006), 129-156 Zbl1143.37013MR2254640
- Jeffrey C. Lagarias, Yang Wang, Substitution Delone sets, Discrete Comput. Geom. 29 (2003), 175-209 Zbl1037.52017MR1957227
- P. Lecomte, M. Rigo, On the representation of real numbers using regular languages, Theory Comput. Syst. 35 (2002), 13-38 Zbl0993.68050MR1879170
- P. Lecomte, M. Rigo, Real numbers having ultimately periodic representations in abstract numeration systems, Inform. and Comput. 192 (2004), 57-83 Zbl1055.11005MR2063624
- P. B. A. Lecomte, M. Rigo, Numeration systems on a regular language, Theory Comput. Syst. 34 (2001), 27-44 Zbl0969.68095MR1799066
- D. A. Lind, The entropies of topological Markov shifts and a related class of algebraic integers, Ergodic Theory Dynam. Systems 4 (1984), 283-300 Zbl0546.58035MR766106
- Douglas Lind, Matrices of Perron numbers, J. Number Theory 40 (1992), 211-217 Zbl0748.11051MR1149738
- M. Lothaire, Algebraic combinatorics on words, 90 (2002), Cambridge University Press, Cambridge Zbl1001.68093MR1905123
- Marston Morse, Gustav A. Hedlund, Symbolic Dynamics, Amer. J. Math. 60 (1938), 815-866 Zbl0019.33502MR1507944
- W. Parry, On the -expansions of real numbers, Acta Math. Acad. Sci. Hungar. 11 (1960), 401-416 Zbl0099.28103MR142719
- G. Rauzy, Nombres algébriques et substitutions, Bull. Soc. Math. France 110 (1982), 147-178 Zbl0522.10032MR667748
- A. Rényi, Representations for real numbers and their ergodic properties, Acta Math. Acad. Sci. Hungar 8 (1957), 477-493 Zbl0079.08901MR97374
- Michel Rigo, Wolfgang Steiner, Abstract -expansions and ultimately periodic representations, J. Théor. Nombres Bordeaux 17 (2005), 283-299 Zbl1084.11059MR2152225
- S. W. Rosema, R. Tijdeman, The Tribonacci substitution, Integers: Electronic Journal of Combinatorial Number Theory 5 (2005) Zbl1099.11004MR2191759
- Raphaël Salem, Algebraic numbers and Fourier analysis, (1963), D. C. Heath and Co., Boston, Mass. Zbl0505.00033MR157941
- Yuki Sano, Pierre Arnoux, Shunji Ito, Higher dimensional extensions of substitutions and their dual maps, J. Anal. Math. 83 (2001), 183-206 Zbl0987.11013MR1828491
- Klaus Schmidt, On periodic expansions of Pisot numbers and Salem numbers, Bull. London Math. Soc. 12 (1980), 269-278 Zbl0494.10040MR576976
- Wolfgang M. Schmidt, Linearformen mit algebraischen Koeffizienten. II, Math. Ann. 191 (1971), 1-20 Zbl0198.07103MR308062
- Marjorie Senechal, Quasicrystals and geometry, (1995), Cambridge University Press, Cambridge Zbl0828.52007MR1340198
- Anne Siegel, Pure discrete spectrum dynamical system and periodic tiling associated with a substitution, Ann. Inst. Fourier (Grenoble) 54 (2004), 341-381 Zbl1083.37009MR2073838
- R. J. Simpson, R. Tijdeman, Multi-dimensional versions of a theorem of Fine and Wilf and a formula of Sylvester, Proc. Amer. Math. Soc. 131 (2003), 1661-1671 (electronic) Zbl1013.05087MR1953570
- V. F. Sirvent, B. Solomyak, Pure discrete spectrum for one-dimensional substitution systems of Pisot type, Canad. Math. Bull. 45 (2002), 697-710 Zbl1038.37008MR1941235
- J.M. Thuswaldner, Unimodular substitions and their associated tiles Zbl1161.37016
- Robert Tijdeman, Rauzy substitutions and multi-dimensional Sturmian words, Theoret. Comput. Sci. 346 (2005), 469-489 Zbl1081.68077MR2187420
Citations in EuDML Documents
topNotesEmbed ?
topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.