Geodesic
A family of two-dimensional words with maximal pattern complexity~$2k$
Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 5, pp. 3-14.

Voir la notice de l'article provenant de la source Math-Net.Ru

Maximal pattern complexity $p^*(k)$ is one of the counting functions over infinite words. In this paper we consider it over two-dimensional words. We construct an infinite family of two-dimensional words with the maximal pattern complexity $p^*(k)=2k$ for $k\in\mathbb N$. It is the minimum of maximal pattern complexity over two-dimensional and not two-periodic words. Bibliogr. 21.
Keywords: complexity, maximal pattern complexity, two-dimensional word, Toeplitz word. 
@article{DA_2010_17_5_a0,
     author = {Ts. Ch.-D. Batueva},
     title = {A family of two-dimensional words with maximal pattern complexity~$2k$},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {3--14},
     publisher = {mathdoc},
     volume = {17},
     number = {5},
     year = {2010},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2010_17_5_a0/}
}
TY  - JOUR
AU  - Ts. Ch.-D. Batueva
TI  - A family of two-dimensional words with maximal pattern complexity~$2k$
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2010
SP  - 3
EP  - 14
VL  - 17
IS  - 5
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2010_17_5_a0/
LA  - ru
ID  - DA_2010_17_5_a0
ER  - 
%0 Journal Article
%A Ts. Ch.-D. Batueva
%T A family of two-dimensional words with maximal pattern complexity~$2k$
%J Diskretnyj analiz i issledovanie operacij
%D 2010
%P 3-14
%V 17
%N 5
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2010_17_5_a0/
%G ru
%F DA_2010_17_5_a0
Ts. Ch.-D. Batueva. A family of two-dimensional words with maximal pattern complexity~$2k$. Diskretnyj analiz i issledovanie operacij, Tome 17 (2010) no. 5, pp. 3-14. http://geodesic.mathdoc.fr/item/DA_2010_17_5_a0/

[1] Batueva Ts. Ch.-D., “Arifmeticheskoe zamykanie dvumernykh slov Tëplitsa”, Diskret. analiz i issled. operatsii, 16:2 (2009), 3–15 | MR

[2] Allouche J.-P., Baake M., Cassaigne J., Damanik D., “Palindrom complexity”, Theor. Comput. Sci., 292 (2003), 9–31 | DOI | MR | Zbl

[3] Allouche J.-P., Shallit J., Automatic sequences: theory, applications, generalizations, Cambridge Univ. Press, Cambridge, 2003, 592 pp. | MR | Zbl

[4] Avgustinovich S. V., Fon-Der-Flaass D. G., Frid A.\, “Arithmetical complexity of infinite words”, Words, languages and combinatorics, v. III, World Sci. Publ., Singapore, 2003, 51–62 ; ICWLC 2000 (Kyoto, Japan, 2000, March), 14–18 | MR

[5] Cassaigne J., “Double sequences with complexity $mn+1$”, J. Autom. Lang. Comb., 4:3 (1999), 153–170 | MR | Zbl

[6] Cassaigne J., Karhumäki J., “Toeplitz words, generalized periodicity and periodically iterated morphisms”, Eur. J. Comb., 18 (1997), 497–510 | DOI | MR | Zbl

[7] Choffrut C., Karhumäki J., “Combinatorics of words”, Handbook of formal languages, v. 1, 1997, 329–438 | MR

[8] Ehrenfeucht A., Rozenberg G., “A limit theorem for sets of subwords in deterministic T0L languages”, Inf. Process. Lett., 2–3 (1973), 70–73 | DOI | MR | Zbl

[9] Epifanio C., Koskas M., Mignosi F., “On a conjecture on bidimensional words”, Theor. Comput. Sci., 299:1–3 (2003), 123–150 | DOI | MR | Zbl

[10] Frid A. E., “Arithmetical complexity of symmetric DOL words”, Theor. Comput. Sci., 306 (2003), 535–542 | DOI | MR | Zbl

[11] Quas A., Zamboni L., “Periodicity and local complexity”, Theor. Comput. Sci., 319:1–3 (2004), 229–240 | DOI | MR | Zbl

[12] Kamae T., Rao H., Xue Y.-M., “Maximal pattern complexity for 2-dimensional words”, Theor. Comput. Sci., 359 (2002), 15–27 | DOI | MR

[13] Kamae T., Xue Y.-M., “Two dimensional word with $2k$ maximal pattern complexity”, Osaka J. Math., 41 (2004), 257–265 | MR | Zbl

[14] Kamae T., Zamboni L., “Sequence entropy and the maximal pattern complexity of infinite words”, Ergodic Theory Dyn. Syst., 22 (2002), 1191–1199 | MR | Zbl

[15] Kamae T., Zamboni L., “Maximal pattern complexity for discrete systems”, Ergodic Theory Dyn. Syst., 22:4 (2002), 1201–1214 | MR | Zbl

[16] Koskas M., “Complexités de suites de Toeplitz”, Discrete Math., 183 (1998), 161–183 | DOI | MR | Zbl

[17] Lothaire M., Algebraic combinatorics on words, Encycl. Math. Appl., 90, 2002, 528 pp. | MR

[18] Morse M., Hedlund G. A., “Symbolic dynamics”, Amer. J. Math., 60 (1938), 815–866 | DOI | MR | Zbl

[19] Morse M., Hedlund G. A., “Symbolic dynamics. II”, Amer. J. Math., 62 (1940), 1–42 | DOI | MR | Zbl

[20] Nakashima I., Tamura J.-I., Yasutomi S.-I., “$^*$-Sturmian words and complexity”, J. Theór. Nombres Bord., 15 (2003), 767–804 | MR | Zbl

[21] Restivo A., Salemi S., “Binary patterns in infinite binary words”, Formal and natural computing, Lect. Notes Comput. Sci., 2300, Springer-Verl., Berlin, 2002, 107–118 | MR