Coverability in two dimensions. (English) Zbl 1423.68370
Dediu, Adrian-Horia (ed.) et al., Language and automata theory and applications. 9th international conference, LATA 2015, Nice, France, March 2–6, 2015. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 8977, 402-413 (2015).
Summary: A word is quasiperiodic (or coverable) if it can be covered by occurrences of another finite word, called its quasiperiod. This notion was previously studied in the domains of text algorithms and combinatorics of right infinite words. We extend several results to two dimensions. We also characterize all rectangular words that cover non-periodic two-dimensional infinite words. Then we focus on two-dimensional words with infinitely many quasiperiods. We show that such words have zero entropy. However, contrarily to the one-dimensional case, they may not be uniformly recurrent.
For the entire collection see [Zbl 1331.68009].
For the entire collection see [Zbl 1331.68009].
MSC:
| 68R15 | Combinatorics on words |
Keywords:
combinatorics on words; patterns; infinite pictures; quasiperiodicity; multi-scale coverabilityReferences:
| [1] | Apostolico, A.; Ehrenfeucht, A., Efficient detection of quasiperiodicities in strings, Theor. Comput. Sci., 119, 2, 247-265 (1993) · Zbl 0804.68109 · doi:10.1016/0304-3975(93)90159-Q |
| [2] | Brudno, A.A.: Entropy and complexity of the trajectories of a dynamical system. Tr. Mosk. Mat. O.-va 44, 124-149 (1982) · Zbl 0499.28017 |
| [3] | Cassaigne, J.: Subword complexity and periodicity in two or more dimensions. In: Rozenberg, G., Thomas, W. (eds.) Developments in Language Theory, Foundations, Applications, and Perspectives 1999, pp. 14-21. World Scientific, Aachen (1999) · Zbl 0978.68111 |
| [4] | Crochemore, M.; Iliopoulos, CS; Korda, M., Two-dimensional prefix string matching and covering on square matrices, Algorithmica, 20, 4, 353-373 (1998) · Zbl 0895.68059 · doi:10.1007/PL00009200 |
| [5] | Glen, A.; Levé, F.; Richomme, G., Quasiperiodic and lyndon episturmian words, Theor. Comput. Sci., 409, 3, 578-600 (2008) · Zbl 1155.68065 · doi:10.1016/j.tcs.2008.09.056 |
| [6] | Iliopoulos, CS; Mouchard, L., Quasiperiodicity: From detection to normal forms, Journal of Automata, Languages and Combinatorics, 4, 3, 213-228 (1999) · Zbl 0946.68112 |
| [7] | Levé, F.; Richomme, G., Quasiperiodic infinite words: Some answers (column: Formal language theory), Bulletin of the EATCS, 84, 128-138 (2004) · Zbl 1169.68566 |
| [8] | Levé, F.; Richomme, G., Quasiperiodic sturmian words and morphisms, Theor. Comput. Sci., 372, 1, 15-25 (2007) · Zbl 1108.68097 · doi:10.1016/j.tcs.2006.10.034 |
| [9] | Lothaire, M.: Combinatorics on Words. Cambridge University Press. Cambridge Mathematical Library (1997) · Zbl 0874.20040 |
| [10] | Marcus, S., Quasiperiodic infinite words (columns: Formal language theory), Bulletin of the EATCS, 82, 170-174 (2004) · Zbl 1169.68484 |
| [11] | Monteil, T., Marcus, S.: Quasiperiodic infinite words: multi-scale case and dynamical properties. http://arxiv.org/abs/math/0603354 |
| [12] | Polley, R., Staiger, L.: The maximal subword complexity of quasiperiodic infinite words. In: McQuillan, I., Pighizzini, G. (eds.) Proceedings Twelfth Annual Workshop on Descriptional Complexity of Formal Systems, DCFS 2010, vol. 31, pp. 169-176. EPTCS, Saskatoon (2010) · Zbl 1455.68155 |
| [13] | Schechter, E.: Handbook of Analysis and its Foundations. Elsevier Science (1996) · Zbl 0943.26001 |
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.
