×

Balance properties of multi-dimensional words. (English) Zbl 0997.68091

Summary: A word \(u\) is called 1-balanced if for any two factors \(v\) and \(w\) of \(u\) of equal length, we have \(-1<|v|_{i}-|w|_{i}<1\) for each letter \(i,\) where \(|v|_{i}\) denotes the number of occurrences of \(i\) in the factor \(v.\) The aim of this paper is to extend the notion of balance to multi-dimensional words. We first characterize all 1-balanced words on \(Z^{n}.\) In particular, we prove they are fully periodic for \(n>1.\) We then give a quantitative measure of non-balancedness for some words on \(Z^{2}\) with irrational density, including two-dimensional Sturmian words.

MSC:

68R15 Combinatorics on words
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] E. Altman, B. Gaujal, A. Hordijk, Balanced sequences and optimal routing, J. Assoc. Comput. Mach. to appear. · Zbl 1327.68180
[2] Arnoux, P.; Rauzy, G., Représentation géométrique de suites de complexité \(2n+1\), Bull. soc. math. France, 119, 199-215, (1991) · Zbl 0789.28011
[3] Berthé, V.; Vuillon, L., Tilings and rotations on the torusa two-dimensional generalization of Sturmian sequences, Discrete math., 223, 27-53, (2000) · Zbl 0970.68124
[4] Berthé, V.; Vuillon, L., Suites doubles de basse complexité, J. théor. nombres Bordeaux, 12, 179-208, (2000) · Zbl 1018.37010
[5] Brown, T.C.; Shiue, P.J.-S., Sums of fractional parts of integer multiples of an irrational, J. number theory, 50, 181-192, (1995) · Zbl 0824.11041
[6] Cassaigne, J.; Ferenczi, S.; Zamboni, L.Q., Imbalances in arnoux – rauzy sequences, Ann. inst. Fourier, 50, 1265-1276, (2000) · Zbl 1004.37008
[7] Droubay, X.; Justin, J.; Pirillo, G., Episturmian words and some constructions of de luca and Rauzy, Theoret. comput. sci., 255, 539-553, (2001) · Zbl 0981.68126
[8] Dulucq, S.; Gouyou-beauchamp, D., Sur LES facteurs des suites de Sturm, Theoret. comput. sci., 71, 381-400, (1990) · Zbl 0694.68048
[9] I. Fagnot, L. Vuillon, Generalized balances in Sturmian words, preprint 2000. · Zbl 1002.68117
[10] Ferenczi, S., Bounded remainder sets, Acta arith., 61, 319-326, (1992) · Zbl 0774.11037
[11] Graham, R.L., Covering the positive integers by disjoint sets of the form \({[n α +β] : n=1,2,…}\), J. combin. theory A, 15, 354-358, (1973) · Zbl 0279.10042
[12] Hardy, G.H.; Littlewood, J.E., Some problems of Diophantine approximations: the lattice-points of a right-angled triangle, Proc. London math. soc., 20, 15-36, (1922) · JFM 48.0197.07
[13] A. Heinis, On low-complexity Z-words and their factors, preprint 1999.
[14] A. Heinis, R.Tijdeman, Extending balanced and stiff words, Report 97-15, Math. Inst. Leiden Univ., The Netherlands, 7pp.
[15] Hubert, P., Well balanced sequences, Theoret. comput. sci., 242, 91-108, (2000) · Zbl 0944.68149
[16] Kesten, H., On a conjecture of erdős and szűsz related to uniform distribution mod1, Acta arith., 12, 193-212, (1966) · Zbl 0144.28902
[17] Lerch, M., Question 1547, Intermédiaire math., 11, 145-146, (1904)
[18] Lipatov, E.P., A classification of binary collections and properties of homogeneity classes, Problemy kibernet., 39, 67-84, (1982), (in Russian) · Zbl 0555.94007
[19] M. Lothaire, in: J. Berstel, P. Séébold (Eds.), Algebraic Combinatoric on Words, Ch. 2: Sturmian Words, Cambridge Univ. Press, to appear. · Zbl 1001.68093
[20] Mignosi, F., On the number of factors of Sturmian words, Theoret. comput. sci., 82, 71-84, (1991) · Zbl 0728.68093
[21] Morse, M.; Hedlund, G.A., Symbolic dynamics, Amer. J. math., 60, 815-866, (1938) · JFM 64.0798.04
[22] Morse, M.; Hedlund, G.A., Symbolic dynamics Iisturmian trajectories, Amer. J. math., 62, 1-42, (1940) · JFM 66.0188.03
[23] A. Ostrowski, Bemerkungen zur Theorie der Diophantischen Approximationen I, II, Abh. Math. Sem. Hamburg I (1922) 77-98, 250-251. · JFM 48.0185.01
[24] Pinner, C., On sums of fractional parts \({n α + γ}\), J. number theory, 65, 48-73, (1997) · Zbl 0886.11045
[25] G. Rauzy, Ensembles à restes bornés, Séminaire de Théorie des Nombres de Bordeaux, exposé 24, 1983-1984. · Zbl 0547.10044
[26] Sierpinski, W., Pewne twierdzenie tyczace sie liczb niewymiernych. un théorème sur LES nombres irrationnels, Bull. internat. acad. polon. sci. lett. cl. sci. math. naturelles Sér. A (cracovie), 725-727, (1909)
[27] Tijdeman, R., On complementary triples of Sturmian bisequences, Indag. math. N. S., 7, 419-424, (1996) · Zbl 0862.68085
[28] R. Tijdeman, Exact covers of balanced sequences and Fraenkel’s conjecture, Algebraic Numer Theory and Diophantine Analysis (Graz, 1998), de Gruyter, Berlin, 2000, pp. 467-483. · Zbl 0971.11003
[29] Tijdeman, R., Fraenkel’s conjecture for six sequences, Discrete math., 222, 223-234, (2000) · Zbl 1101.11314
[30] Vuillon, L., Combinatoire des motifs d’une suite sturmienne bidimensionnelle, Theoret. comput. sci., 209, 261-285, (1998) · Zbl 0913.68206
[31] Zorich, A., Deviation for interval exchange transformations, Ergodic theory dynamical systems, 17, 1477-1499, (1997) · Zbl 0958.37002
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.