×

Multidimensional unrepetitive configurations. (English) Zbl 0649.68073

An existence of bi-finite words on finite alphabets which are r-th power- free together with a certain class of their subwords is used for an effective construction of the following n-dimensional configuration: It is possible to associate with each lattice-point of the n-dimensional space a letter of a finite alphabet so that the sequences of the letters corresponding to the points lying on a same straight line are r-th power- free words \((r>1)\). An analogous result is obtained also for some avoidable sets of patterns.
Reviewer: M.Demlová

MSC:

68R99 Discrete mathematics in relation to computer science
05B99 Designs and configurations
68Q45 Formal languages and automata
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Bean, D.; Ehrenfeucht, A.; McNulty, G., Avoidable patterns in strings of symbols, Pacific J. of Math., 85, 261-294 (1979) · Zbl 0428.05001
[2] Berstel, J., Some recent results on square-free words, (Fontent, M.; Melhom, K., Proc. STACS 84. Proc. STACS 84, Lecture Notes in Computer Science, 166 (1984), Springer: Springer Berlin), 14-25
[3] Brandenburg, F. J., Uniformly growing \(k\) th power-free homomorphisms, Theoret. Comput. Sci., 23, 69-82 (1983) · Zbl 0508.68051
[4] Crochemore, M., Régularités évitables, (Thése d’Etat (1983), Université de Haute-Normandie)
[5] Dejean, F., Sur un théoreme de Thue, J. Combin. Theory, 13, 90-99 (1972) · Zbl 0245.20052
[6] Leech, J., A problem of strings of beads, Math. Gazette, 41, 277-278 (1957) · Zbl 0079.01101
[7] Lothaire, M., Combinatorics on Words (1982), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 1001.68093
[8] Morse, M.; Hedlund, G., Unending chess, symbolic dynamics and a problem in semigroups, Duke Math. J., 11, 1-7 (1944) · Zbl 0063.04115
[9] Pansiot, J., A propos d’une conjecture de F. Dejean sur les répétitions dans les mots, Discrete Appl. Math., 7, 297-311 (1984) · Zbl 0536.68072
[10] Thue, A., Ueber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 1, 1-22 (1906) · JFM 39.0283.01
[11] Thue, A., Ueber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania, 7, 1-67 (1912) · JFM 44.0462.01
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.