Relations on words

[en] In the first part of this survey, we present classical notions arising in combinatorics on words: growth function of a language, complexity function of an infinite word, pattern avoidance, periodicity and uniform recurrence. Our presentation tries to set up a unified framework with respect to a given binary relation. In the second part, we mainly focus on abelian equivalence, $k$-abelian equivalence, combinatorial coefficients and associated relations, Parikh matrices and $M$-equivalence. In particular, some new refinements of abelian equivalence are introduced.

Disciplines :

Computer science
Mathematics

Author, co-author :

Rigo, Michel ; Université de Liège > Département de mathématique > Mathématiques discrètes

Language :

English

Title :

Relations on words

Publication date :

2017

Journal title :

Indagationes Mathematicae

ISSN :

0019-3577

eISSN :

1872-6100

Publisher :

Elsevier, Amsterdam, Netherlands

Volume :

Pages :

183-204

Peer reviewed :

Peer Reviewed verified by ORBi

Available on ORBi :

since 25 November 2016

Statistics

Number of views

121 (10 by ULiège)

Number of downloads

110 (5 by ULiège)

More statistics

Scopus citations^®

Scopus citations^®
without self-citations

OpenCitations

Bibliography

[1] Aberkane, A., Currie, J.D., Rampersad, N., The number of ternary words avoiding abelian cubes grows exponentially. J. Integer Seq., 7.2, 2004 Art. 04.2.7.
[2] Adamczewski, B., Balances for fixed points of primitive substitutions. Theoret. Comput. Sci. 307 (2003), 47–75.
[3] Allouche, J.-P., Sur la complexité des suites infinies. Bull. Belg. Math. Soc. 1 (1994), 133–143.
[4] Allouche, J.-P., Shallit, J., Sums of digits, overlaps, and palindromes. Discrete Math. Theor. Comput. Sci. 4 (2000), 1–10.
[5] Allouche, J.-P., Shallit, J., Automatic Sequences: Theory, Applications, Generalizations. 2003, Cambridge Univ. Press.
[6] Arnoux, P., Rauzy, G., Représentation géométrique de suites de complexité 2n+1. Bull. Soc. Math. France 119 (1991), 199–215.
[7] Berstel, J., Boasson, L., Partial words and a theorem of Fine and Wilf. Theoret. Comput. Sci. 218 (1999), 135–141.
[8] Berstel, J., Karhumäki, J., Combinatorics on words — a tutorial. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 79 (2003), 178–228.
[9] Berstel, J., Reutenauer, C., Noncommutative Rational Series with Applications Encycl. of Math. and its Appl., vol. 137, 2011, Cambridge Univ. Press.
[10] Berstel, J., Vuillon, L., Coding rotations on intervals. Theoret. Comput. Sci. 281 (2002), 99–107.
[11] Berthé, V., Rigo, M., (eds.) Combinatorics, Automata and Number Theory Encycl. of Math. and its Appl., vol. 135, 2010, Cambridge Univ. Press.
[12] Berthé, V., Rigo, M., (eds.) Combinatorics, Words and Symbolic Dynamics Encycl. of Math. and its Appl., vol. 159, 2016, Cambridge Univ. Press.
[13] Blanchet-Sadri, F., Codes, orderings and partial words. Theoret. Comput. Sci. 239 (2004), 177–202.
[14] Blanchet-Sadri, F., Periodicity on partial words. Comput. Math. Appl. 47 (2004), 71–82.
[15] Blanchet-Sadri, F., Currie, J.D., Rampersad, N., Fox, N., Abelian complexity of fixed point of morphism 0↦012, 1↦02, 2↦1. Integers, 14, 2014 Paper A11.
[16] Blanchet-Sadri, F., Hegstrom, R.A., Partial words and a theorem of Fine and Wilf revisited. Theoret. Comput. Sci. 270 (2002), 401–419.
[17] Blanchet-Sadri, F., Oey, T., Rankin, T., Fine and Wilf's theorem for partial words with arbitrarily many weak periods. Internat. J. Found. Comput. Sci. 21 (2010), 705–722.
[18] Blanchet-Sadri, F., Simmons, S., Tebbe, A., Veprauskas, A., Abelian periods, partial words, and an extension of a theorem of Fine and Wilf. RAIRO Theor. Inform. Appl. 47 (2013), 215–234.
[19] Brandenburg, F.-J., Uniformly growing k-th power-free homomorphisms. Theoret. Comput. Sci. 23 (1983), 69–82.
[20] Brown, T.C., Is there a sequence on four symbols in which no two adjacent segments are permutations of one another?. Amer. Math. Monthly 78 (1971), 886–888.
[21] Carpi, A., On Abelian Power-Free Morphisms. Int. J. Algebra Comput. 3 (1993), 151–167.
[22] Carpi, A., On the number of Abelian square-free words on four letters. Discrete Appl. Math. 81 (1998), 155–167.
[23] Cassaigne, J., Counting overlap-free binary words. Lect. Notes Comput. Sci. 665 (1993), 216–225.
[24] Cassaigne, J., Currie, J.D., Schaeffer, L., Shallit, J., Avoiding three consecutive blocks of the same size and same sum. J. ACM, 61, 2014 Art. 10.
[25] Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q., Avoiding Abelian powers in binary words with bounded Abelian complexity. Internat. J. Found. Comput. Sci. 22 (2011), 905–920.
[26] Cassaigne, J., Karhumäki, J., Saarela, A., On growth and fluctuation of k-abelian complexity. Lect. Notes Comput. Sci. 9139 (2015), 109–122.
[27] Cobham, A., Uniform tag sequences. Math. Syst. Theory 6 (1972), 164–192.
[28] Constantinescu, S., Ilie, L., Fine and Wilf's theorem for abelian periods. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 89 (2006), 167–170.
[29] Coven, E.M., Hedlund, G.A., Sequences with minimal block growth. Math. Syst. Theory 7 (1973), 138–153.
[30] Currie, J.D., Rampersad, N., Fixed points avoiding Abelian k-powers. J. Combin. Theory Ser. A 119 (2012), 942–948.
[31] Currie, J., Rampersad, N., Growth rate of binary words avoiding xxxR. Theoret. Comput. Sci. 609 (2016), 456–468.
[32] Dekking, F.M., Strongly nonrepetitive sequences and progression-free sets. J. Combin. Theory Ser. A 27 (1979), 181–185.
[33] Didier, G., Combinatoire des codages de rotations. Acta Arith. 85 (1998), 157–177.
[34] Dress, A.W.M., Erdős, P.L., Reconstructing words from subwords in linear time. Ann. Comb. 8 (2004), 457–462.
[35] Dudik, M., Schulman, L.J., Reconstruction from subsequences. J. Combin. Theory Ser. A 103 (2003), 337–348.
[36] Durand, F., A characterization of substitutive sequences using return words. Discrete Math. 179 (1998), 89–101.
[37] Durand, F., Decidability of the HD0L ultimate periodicity problem. RAIRO - Theor. Inform. Appl. 47 (2013), 201–214.
[38] Ehlers, T., Manea, F., Mercas, R., Nowotka, D., k-abelian pattern matching. Lect. Notes Comput. Sci. 8633 (2014), 178–190.
[39] Ehrenfeucht, A., Lee, K.P., Rozenberg, G., Subword complexities of various classes of deterministic developmental languages without interaction. Theoret. Comput. Sci. 1 (1975), 59–75.
[40] Erdős, P., Some unsolved problems. Michigan Math. J. 4 (1957), 291–300.
[41] Entringer, R.C., Jackson, D.E., Schatz, J.A., On nonrepetitive sequences. J. Combin. Theory Ser. A 16 (1974), 159–164.
[42] Fraenkel, A.S., Simpson, R.J., How many squares must a binary sequence contain?. Electron. J. Combin., 2, 1995.
[43] D.D. Freydenberger, P. Gawrychowski, J. Karhumäki, F. Manea, W. Rytter, Testing k-binomial equivalence, arXiv:22600.9051.
[44] Greinecker, F., On the 2-abelian complexity of the Thue–Morse word. Theoret. Comput. Sci. 593 (2015), 88–105.
[45] Halava, V., Harju, T., Kärki, T., Relational codes of words. Theoret. Comput. Sci. 389 (2007), 237–249.
[46] Halava, V., Harju, T., Kärki, T., The theorem of fine and Wilf for relational periods. Theor. Inform. Appl. 43 (2009), 209–220.
[47] Halava, V., Harju, T., Kärki, T., Rigo, M., On the periodicity of morphic words. Lect. Notes Comput. Sci. 6224 (2010), 209–217.
[48] Harju, T., Linna, M., On the periodicity of morphisms on free monoids. RAIRO Inform. Théor. Appl. 20 (1986), 47–54.
[49] Holton, C., Zamboni, L.Q., Descendants of primitive substitutions. Theory Comput. Syst. 32 (1999), 133–157.
[50] Huova, M., Existence of an infinite ternary 64-abelian square-free word. RAIRO - Theor. Inform. Appl. 48 (2014), 307–314.
[51] Huova, M., Karhumäki, J., On unavoidability of k-abelian squares in pure morphic words. J. Integer Seq., 16(2), 2013 Art. 13.2.9.
[52] Huova, M., Saarela, A., Strongly k-Abelian Repetitions Lect. Notes Comput. Sci., vol. 8079, 2013, Springer.
[53] L.I. Kalashnik, The reconstruction of a word from fragments, in Numerical Mathematics and Computer Technology, pp. 56–57, Akad. Nauk Ukrain. SSR Inst. Mat., Preprint IV, 1973.
[54] Karandikar, P., Kufleitner, M., Schnoebelen, Ph., On the index of Simon's congruence for piecewise testability. Inform. Process. Lett. 15 (2015), 515–519.
[55] Karhumäki, J., Generalized Parikh mappings and homomorphisms. Inform. Control 47 (1980), 155–165.
[56] Karhumäki, J., Puzynina, S., Saarela, A., Fine and Wilf's theorem for k-abelian periods. Internat. J. Found. Comput. Sci. 24 (2013), 1135–1152.
[57] Karhumäki, J., Saarela, A., Zamboni, L.Q., On a generalization of Abelian equivalence and complexity of infinite words. J. Combin. Theory Ser. A 120 (2013), 2189–2206.
[58] Karhumäki, J., Saarela, A., Zamboni, L.Q., Variations of the Morse-Hedlund theorem for k-abelian equivalence. Lect. Notes Comput. Sci. 8633 (2014), 203–214.
[59] Karhumäki, J., Shallit, J., Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 105 (2004), 335–347.
[60] Kärki, T., Compatibility relations on codes and free monoids. Theor. Inform. Appl. 42 (2008), 539–552.
[61] Keränen, V., Abelian squares are avoidable on 4 letters. Lect. Notes Comput. Sci. 623 (1992), 41–52.
[62] Kiefer, S., Murawski, A.S., Ouaknine, J., Wachter, B., Worrell, J., On the complexity of the equivalence problem for probabilistic automata. Lect. Notes Comput. Sci. 7213 (2012), 467–481.
[63] Kobayashi, Y., Enumeration of irreducible binary words. Discrete Appl. Math. 20 (1988), 221–232.
[64] Krasikov, I., Roditty, Y., On a Reconstruction Problem for Sequences. J. Combin. Theory Ser. A 77 (1997), 344–348.
[65] Leroy, J., Rigo, M., Stipulanti, M., Generalized Pascal triangle for binomial coefficients of words. Adv. Appl. Math. 80 (2016), 24–47.
[66] Lothaire, M., Combinatorics on Words Cambridge Mathematical Library, 1997, Cambridge Univ. Press.
[67] Lothaire, M., Algebraic Combinatorics on Words Encycl. of Math. and its Applic., vol. 90, 2002, Cambridge Univ. Press.
[68] Madill, B., Rampersad, N., The abelian complexity of the paperfolding word. Discrete Math. 313 (2013), 831–838.
[69] Maňuch, J., Characterization of a word by its subwords. Rozenberg, G., Thomas, W., (eds.) Developments in Language Theory, 2000, World Scientific Publ. Co, Singapore, 210–219.
[70] Mateescu, A., Salomaa, A., Salomaa, K., Yu, S., A sharpening of the parikh mapping. RAIRO-Theor. Inform. Appl. 35 (2001), 551–564.
[71] Mateescu, A., Salomaa, A., Yu, S., Subword histories and Parikh matrices. J. Comput. Systems Sci. 68 (2004), 1–21.
[72] Morse, M., Hedlund, G.A., Symbolic dynamics. Amer. J. Math. 60 (1938), 815–866.
[73] Ochem, P., Rampersad, N., Shallit, J., Avoiding approximate squares. Internat. J. Found. Comput. Sci. 19 (2008), 633–648.
[74] Pansiot, J.-J., Bornes inférieures sur la complexité des facteurs des mots infinis engendrés par morphismes itérés. Lect. Notes Comput. Sci. 166 (1984), 230–240.
[75] Pansiot, J.-J., Complexité des facteurs des mots infinis engendrés par morphismes itérés. Lect. Notes Comput. Sci. 172 (1984), 380–389.
[76] Pansiot, J.-J., Decidability of periodicity for infinite words. RAIRO Inform. Théor. Appl. 20 (1986), 43–46.
[77] Parreau, A., Rigo, M., Rowland, E., Vandomme, É., A new approach to the 2-regularity of the ℓ-abelian complexity of 2-automatic sequences. Electron. J. Combin., 22, 2015 Paper 1.27.
[78] Parikh, R., On context-free languages. J. ACM, 13, 1966.
[79] Puzynina, S., Zamboni, L.Q., Abelian returns in Sturmian words. J. Combin. Theory Ser. A 120 (2013), 390–408.
[80] Rampersad, N., Rigo, M., Salimov, P., A note on abelian returns in rotation words. Theoret. Comput. Sci. 528 (2014), 101–107.
[81] Rao, M., On some generalizations of abelian power avoidability. Theoret. Comput. Sci. 601 (2015), 39–46.
[82] Rao, M., Rigo, M., Salimov, P., Avoiding 2-binomial squares and cubes. Theoret. Comput. Sci. 572 (2015), 83–91.
[83] Richomme, G., Saari, K., Zamboni, L.Q., Balance and abelian complexity of the Tribonacci word. Adv. Appl. Math. 45 (2010), 212–231.
[84] Richomme, G., Saari, K., Zamboni, L.Q., Abelian complexity of minimal subshifts. J. Lond. Math. Soc. 83 (2011), 79–95.
[85] Rigo, M., Formal Languages, Automata and Numeration Systems: Introduction to Combinatorics on Words. 2014, ISTE-Wiley.
[86] Rigo, M., Salimov, P., Another generalization of abelian equivalence: binomial complexity of infinite words. Theoret. Comput. Sci. 601 (2015), 47–57.
[87] Rigo, M., Salimov, P., Vandomme, E., Some properties of abelian return words. J. Integer Seq., 16, 2013 Art. 13.2.5.
[88] Salomaa, A., Counting (scattered) subwords. Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 81 (2003), 165–179.
[89] Salomaa, A., Connections between subwords and certain matrix mappings. Theoret. Comput. Sci. 340 (2005), 188–203.
[90] Salomaa, A., Criteria for the matrix equivalence of words. Theoret. Comput. Sci. 411 (2010), 1818–1827.
[91] Salomaa, A., Subword balance, position indices and power sums. J. Comput. Systems Sci. 76 (2010), 861–871.
[92] Schützenberger, M.-P., On the definition of a family of automata. Inf. Control, 1961, 245–270.
[93] Şerbănuţă, T.-F., Extending Parikh matrices. Theoret. Comput. Sci. 310 (2004), 23–246.
[94] Sudkamp, T.A., Languages and Machines: An Introduction to the Theory of Computer Science. 1997, Addison-Wesley Pub.
[95] Thue, A., Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1–22.
[96] Thue, A., Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912), 1–67.
[97] Turek, O., Abelian complexity and abelian co-decomposition. Theoret. Comput. Sci. 469 (2013), 77–91.
[98] Turek, O., Abelian complexity function of the Tribonacci word. J. Integer Seq., 18, 2015 Art. 15.3.4.
[99] Tzeng, W., A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21 (1992), 216–227.
[100] Vuillon, L., A characterization of Sturmian words by return words. European J. Combin. 22 (2001), 263–275.