nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Abelian Properties of Words

verfasst von : Svetlana Puzynina

Erschienen in: Combinatorics on Words

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Abelian properties of words is a widely studied field in combinatorics on words. Two finite words are abelian equivalent if for each letter they contain the same numbers of occurrences of this letter. In this paper, we give a short overview of some directions of research on abelian properties of words, and discuss in more detail two new problems: small abelian complexity of two-dimensional words, and abelian subshifts.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Matching Patterns with Variables

Nächstes Kapitel On Sets of Words of Rank Two

Adamczewski, B.: Balances for fixed points of primitive substitutions. Theor. Comput. Sci. 307(1), 47–75 (2003)MathSciNetCrossRef

Arnoux, P., Rauzy, G.: Représentation géométrique de suites de complexité \(2n+1\). Bull. Soc. Math. France 119, 199–215 (1991)MathSciNetCrossRef

Avgustinovich, S., Cassaigne, J., Karhumäki, J., Puzynina, S., Saarela, A.: On abelian saturated infinite words. Theoret. Comput. Sci. (to appear). https://doi.org/10.1016/j.tcs.2018.05.013

Avgustinovich, S., Karhumäki, J., Puzynina, S.: On abelian versions of critical factorization theorem. RAIRO - Theor. Inf. Applic. 46, 3–15 (2012)MathSciNetCrossRef

Bark, J., Varju, P.: Partitioning the positive integers to seven beatty sequences. Indag. Math. 14(2), 149–161 (2003)MathSciNetCrossRef

Berthé, V., Tijdeman, R.: Balance properties of multi-dimensional words. Theor. Comput. Sci. 273, 197–224 (2002)MathSciNetCrossRef

Berthé, V., Vuillon, L.: Tilings and rotations: a two-dimensional generalization of Sturmian sequences. Discrete Math. 223, 27–53 (2000)MathSciNetCrossRef

Blanchet-Sadri, F., Fox, N., Rampersad, N.: On the asymptotic Abelian complexity of morphic words. Adv. Appl. Math. 61, 46–84 (2014)MathSciNetCrossRef

Cassaigne, J.: Double sequences with complexity \(mn+1\). J. Autom. Lang. Comb. 4(3), 153–170 (1999)MathSciNetMATH

10.

Cassaigne, J., Richomme, G., Saari, K., Zamboni, L.Q.: Avoiding abelian powers in binary words with bounded abelian complexity. Int. J. Found. Comput. Sci. 22(4), 905–920 (2011)MathSciNetCrossRef

11.

Charlier, E., Harju, T., Puzynina, S., Zamboni, L.Q.: Abelian bordered factors and periodicity. Eur. J. Comb. 51, 407–418 (2016)MathSciNetCrossRef

12.

Christodoulakis, M., Christou, M., Crochemore, M., Iliopoulos, C.S.: Abelian borders in binary words. Discrete Appl. Math. 171, 141–146 (2014)MathSciNetCrossRef

13.

Constantinescu, S., Ilie, L.: Fine and Wilf’s theorem for abelian periods. Bull. Eur. Assoc. Theor. Comput. Sci. 89, 167–170 (2006)MathSciNetMATH

14.

Coven, E.M., Hedlund, G.A.: Sequences with minimal block growth. Math. Syst. Theory 7, 138–153 (1973)MathSciNetCrossRef

15.

Currie, J., Rampersad, N.: Recurrent words with constant Abelian complexity. Adv. Appl. Math. 47, 116–124 (2011)MathSciNetCrossRef

16.

Cyr, V., Kra, B.: Nonexpansive \(\mathbb{Z}^2\)-subdynamics and Nivat’s conjecture. Trans. Am. Math. Soc. 367(9), 6487–6537 (2015)

17.

de Luca, A.: Sturmian words: structure, combinatorics, and their arithmetics. Theor. Comput. Sci. 183, 45–82 (1997)MathSciNetCrossRef

18.

Dekking, F.M.: Strongly non-repetitive sequences and progression-free sets. J. Comb. Theory Ser. A 27(2), 181–185 (1979)CrossRef

19.

Didier, G.: Caractérisation des \(N\)-écritures et application à l’étude des suites de complexité ultimement \(n + c^{ste}\). Theoret. Comp. Sci. 215(1–2), 31–49 (1999)CrossRef

20.

Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions by de Luca and Rauzy. Theor. Comput. Sci. 255, 539–553 (2001)CrossRef

21.

Durand, F., Rigo, M.: Multidimensional extension of the Morse-Hedlund theorem. Eur. J. Comb. 34(2), 391–409 (2013)MathSciNetCrossRef

22.

Entringer, R.C., Jackson, D.E., Schatz, J.A.: On nonrepetitive sequences. J. Comb. Theory (A) 16, 159–164 (1974)MathSciNetCrossRef

23.

Epifanio, C., Koskas, M., Mignosi, F.: On a conjecture on bi-dimensional words. Theor. Comput. Sci. 299, 123–150 (2003)CrossRef

24.

Erdös, P.: Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6, 221–254 (1961)

25.

Evdokimov, A.A.: Strongly asymmetric sequences generated by a finite number of symbols. Dokl. Akad. Nauk SSSR 179, 1268–1271 (1968)MathSciNetMATH

26.

Ferenczi, S., Mauduit, C.: Transcendence of numbers with a low complexity expansion. J. Number Theory 67, 146–161 (1997)MathSciNetCrossRef

27.

Fici, G., Mignosi, F., Shallit, J.: Abelian-square-rich words. Theor. Comput. Sci. 684, 29–42 (2017)MathSciNetCrossRef

28.

Fici, G., et al.: Abelian powers and repetitions in Sturmian words. Theor. Comput. Sci. 635, 16–34 (2016)MathSciNetCrossRef

29.

Fine, N.J., Wilf, H.S.: Uniqueness theorems for periodic functions. Proc. Am. Math. Soc. 16, 109–114 (1965)MathSciNetCrossRef

30.

Fraenkel, A.S.: Complementing and exactly covering sequences. J. Comb. Theory Ser. A 14(1), 8–20 (1973)MathSciNetCrossRef

31.

Hejda, T., Steiner, W., Zamboni, L.Q.: What is the abelianization of the tribonacci shift? In: Workshop on Automatic Sequences, Liège, May 2015

32.

Hubert, P.: Suites équilibrées. Theor. Comput. Sci. 242(1–2), 91–108 (2000)CrossRef

33.

Kaboré, I., Tapsoba, T.: Combinatoire de mots récurrents de complexité \(n + 2\). ITA 41(4), 425–446 (2007)MATH

34.

Karhumäki, J., Puzynina, S., Whiteland, M.: On abelian subshifts. In: DLT 2018, pp. 453–464 (2018)CrossRef

35.

Kari, J. Moutot, E.: Decidability and Periodicity of Low Complexity Tilings. https://arxiv.org/abs/1904.01267

36.

Kari, J., Szabados, M.: An algebraic geometric approach to nivat’s conjecture. In: Halldórsson, M.M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) ICALP 2015, Part II. LNCS, vol. 9135, pp. 273–285. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-47666-6_22CrossRef

37.

Keränen, V.: Abelian squares are avoidable on 4 letters. In: Kuich, W. (ed.) ICALP 1992. LNCS, vol. 623, pp. 41–52. Springer, Heidelberg (1992). https://doi.org/10.1007/3-540-55719-9_62CrossRef

38.

Keränen, V.: New abelian square-free DT0L-languages over 4 letters (2003, manuscript)

39.

Lind, D., Marcus, B.: An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, New York (1995)CrossRef

40.

Lothaire, M.: Algebraic Combinatorics on Words. Cambridge University Press, Cambridge (2002)CrossRef

41.

Masáková, Z., Pelantová, E.: Enumerating abelian returns to prefixes of sturmian words. In: Karhumäki, J., Lepistö, A., Zamboni, L. (eds.) WORDS 2013. LNCS, vol. 8079, pp. 193–204. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40579-2_21CrossRefMATH

42.

Morse, M., Hedlund, G.: Symbolic dynamics. Am. J. Math. 60, 815–866 (1938)MathSciNetCrossRef

43.

Morse, M., Hedlund, G.: Symbolic dynamics II: sturmian sequences. Am. J. Math. 62, 1–42 (1940)CrossRef

44.

Nivat M.: Invited talk at ICALP’97 (1997)

45.

Pansiot, J.-J.: Complexité des facteurs des mots infinis engendrés par morphismes itérés. In: Paredaens, J. (ed.) ICALP 1984. LNCS, vol. 172, pp. 380–389. Springer, Heidelberg (1984). https://doi.org/10.1007/3-540-13345-3_34CrossRef

46.

Puzynina, S.: Small abelian complexity of two-dimensional infinite words (submitted)

47.

Puzynina, S., Zamboni, L.Q.: Abelian returns in sturmian words. J. Comb. Theory Ser. A 120(2), 390–408 (2013)MathSciNetCrossRef

48.

Quas, A., Zamboni, L.Q.: Periodicity and local complexity. Theor. Comput. Sci. 319(1–3), 229–240 (2004)MathSciNetCrossRef

49.

Rampersad, N., Rigo, M., Salimov, P.: A note on abelian returns in rotation words. Theor. Comput. Sci. 528, 101–107 (2014)MathSciNetCrossRef

50.

Rao, M., Rosenfeld, M.: Avoidability of long k-abelian repetitions. Math. Comput. 85(302), 3051–3060 (2016)MathSciNetCrossRef

51.

Rao, M., Rosenfeld, M.: Avoiding two consecutive blocks of same size and same sum over \(\mathbb{Z}^2\). SIAM J. Discrete Math. 32(4), 2381–2397 (2018)MathSciNetCrossRef

52.

Richomme, G., Saari, K., Zamboni, L.Q.: Abelian complexity in minimal subshifts. J. London Math. Soc. 83, 79–95 (2011)MathSciNetCrossRef

53.

Richomme, G., Saari, K., Zamboni, L.Q.: Balance and abelian complexity of the tribonacci word. Adv. Appl. Math. 45, 212–231 (2010)MathSciNetCrossRef

54.

Rigo, M., Salimov, P., Vandomme, E.: Some properties of abelian return words. J. Integer Seq. 16 (2013). Article number 13.2.5

55.

Saarela, A.: Ultimately constant abelian complexity of infinite words. J. Autom. Lang. Comb. 14(3–4), 255–258 (2009)MathSciNetMATH

56.

Simpson, J.: An abelian periodicity lemma. Theor. Comput. Sci. 656, 249–255 (2016)MathSciNetCrossRef

57.

Vuillon, L.: A characterization of Sturmian words by return words. Eur. J. Comb. 22, 263–275 (2001)MathSciNetCrossRef

58.

Whiteland, M.A.: Asymptotic abelian complexities of certain morphic binary words. J. Autom. Lang. Comb. 24(1), 89–114 (2019)MathSciNet

59.

Zamboni, L.Q.: Personal communication (2018)

Titel: Abelian Properties of Words
verfasst von: Svetlana Puzynina
Verlag: Springer International Publishing
Buch: Combinatorics on Words
Print ISBN: 978-3-030-28795-5

Electronic ISBN: 978-3-030-28796-2

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-28796-2_2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner