nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

On Infinite Prefix Normal Words

verfasst von : Ferdinando Cicalese, Zsuzsanna Lipták, Massimiliano Rossi

Erschienen in: SOFSEM 2019: Theory and Practice of Computer Science

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

Prefix normal words are binary words that have no factor with more 1s than the prefix of the same length. Finite prefix normal words were introduced in [Fici and Lipták, DLT 2011]. In this paper, we study infinite prefix normal words and explore their relationship to some known classes of infinite binary words. In particular, we establish a connection between prefix normal words and Sturmian words, between prefix normal words and abelian complexity, and between prefix normality and lexicographic order.

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 Phase Transition in Matched Formulas and a Heuristic for Biclique Satisfiability

Nächstes Kapitel Priority Scheduling in the Bamboo Garden Trimming Problem

For ease of presentation, we use Lyndon to mean lexicographically greatest among its conjugates; this is equivalent to the usual definition up to renaming characters.

Note the different terminology in [17]: characteristic word \(\rightarrow \) proper standard Sturmian, Sturmian \(\rightarrow \) proper Sturmian, rational mechanical word \(\rightarrow \) periodic Sturmian.

Amir, A., Chan, T.M., Lewenstein, M., Lewenstein, N.: On hardness of jumbled indexing. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 114–125. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-43948-7_10CrossRef

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

Blondin Massé, A., de Carufel, J., Goupil, A., Lapointe, M., Nadeau, É., Vandomme, É.: Leaf realization problem, caterpillar graphs and prefix normal words. Theoret. Comput. Sci. 732, 1–13 (2018)MathSciNetCrossRef

Burcsi, P., Cicalese, F., Fici, G., Lipták, Zs.: Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci. 23, 357–374 (2012)MathSciNetCrossRef

Burcsi, P., Fici, G., Lipták, Zs., Ruskey, F., Sawada, J.: On combinatorial generation of prefix normal words. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 60–69. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-07566-2_7MATH

Burcsi, P., Fici, G., Lipták, Zs., Ruskey, F., Sawada, J.: On prefix normal words and prefix normal forms. Theoret. Comput. Sci. 659, 1–13 (2017)MathSciNetCrossRef

Cassaigne, J., Kaboré, I.: Abelian complexity and frequencies of letters in infinite words. Int. J. Found. Comput. Sci. 27(05), 631–649 (2016)MathSciNetCrossRef

Chan, T.M., Lewenstein, M.: Clustered integer 3SUM via additive combinatorics. In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pp. 31–40 (2015)

Cicalese, F., Lipták, Zs., Rossi, M.: Bubble-Flip - a new generation algorithm for prefix normal words. Theoret. Comput. Sci. 743, 38–52 (2018)MathSciNetCrossRef

10.

Cunha, L.F.I., Dantas, S., Gagie, T., Wittler, R., Kowada, L.A.B., Stoye, J.: Fast and simple jumbled indexing for binary run-length encoded strings. In: 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017). LIPIcs, vol. 78, pp. 19:1–19:9 (2017)

11.

Davis, C., Knuth, D.: Number representations and dragon curves, I, II. J. Recreat. Math. 3, 133–149 and 161–181 (1970)

12.

Fici, G., Lipták, Zs.: On prefix normal words. In: Mauri, G., Leporati, A. (eds.) DLT 2011. LNCS, vol. 6795, pp. 228–238. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22321-1_20CrossRef

13.

Gagie, T., Hermelin, D., Landau, G.M., Weimann, O.: Binary jumbled pattern matching on trees and tree-like structures. Algorithmica 73(3), 571–588 (2015)MathSciNetCrossRef

14.

Kaboré, I., Kientéga, B.: Abelian complexity of Thue-Morse word over a ternary alphabet. In: Brlek, S., Dolce, F., Reutenauer, C., Vandomme, É. (eds.) WORDS 2017. LNCS, vol. 10432, pp. 132–143. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66396-8_13CrossRef

15.

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

16.

Madill, B., Rampersad, N.: The abelian complexity of the paperfolding word. Discrete Math. 313(7), 831–838 (2013)MathSciNetCrossRef

17.

Pirillo, G.: Inequalities characterizing standard Sturmian and episturmian words. Theoret. Comput. Sci. 341(1–3), 276–292 (2005)MathSciNetCrossRef

18.

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

19.

Ruskey, F., Savage, C., Wang, T.: Generating necklaces. J. Algorithms 13(3), 414–430 (1992)MathSciNetCrossRef

20.

Ruskey, F., Sawada, J., Williams, A.: Binary bubble languages and cool-lex order. J. Comb. Theory Ser. A 119(1), 155–169 (2012)MathSciNetCrossRef

21.

Sawada, J., Williams, A.: Efficient oracles for generating binary bubble languages. Electron. J. Comb. 19(1), P42 (2012)MathSciNetMATH

22.

Sawada, J., Williams, A., Wong, D.: Inside the Binary Reflected Gray Code: Flip-Swap languages in 2-Gray code order (2017, unpublished manuscript)

23.

Sloane, N.J.A.: The On-Line Encyclopedia of Integer Sequences. http://oeis.org

24.

Siromoney, R., Mathew, L., Dare, V., Subramanian, K.: Infinite Lyndon words. Inf. Process. Lett. 50, 101–104 (1994)MathSciNetCrossRef

25.

Turek, O.: Abelian complexity function of the Tribonacci word. J. Integer Seq. 18 (2015). Article 15.3.4

Titel: On Infinite Prefix Normal Words
verfasst von: Ferdinando Cicalese
Zsuzsanna Lipták
Massimiliano Rossi
Verlag: Springer International Publishing
Buch: SOFSEM 2019: Theory and Practice of Computer Science
Print ISBN: 978-3-030-10800-7

Electronic ISBN: 978-3-030-10801-4

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-10801-4_11

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"