Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.

Branching Frequency and Markov Entropy of Repetition-Free Languages

Autor: Petrova, E. A., Shur, A. M.

Publikováno v: Lect. Notes Comput. Sci.
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

We define a new quantitative measure for an arbitrary factorial language: the entropy of a random walk in the prefix tree associated with the language; we call it Markov entropy. We relate Markov entropy to the growth rate of the language and the par

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=od_______917::00b8bedebfba06d1741d1afc82182903
https://hdl.handle.net/10995/111364

Crucial abelian k-power-free words

Autor: Amy Glen, Bjarni V. Halldorsson, Sergey Kitaev

Publikováno v: Discrete Mathematics & Theoretical Computer Science, Vol Vol. 12 no. 5, Iss Combinatorics (2010)

Combinatorics

Externí odkaz: https://doaj.org/article/564ddf3a0a0a46628556adc8d93497e7

Abelian Powers and Repetitions in Sturmian Words

Autor: Alessio Langiu, Élise Prieur-Gaston, Gabriele Fici, Filippo Mignosi, Thierry Lecroq, Jarkko Peltomäki, Arnaud Lefebvre

Publikováno v: Theoretical computer science 635 (2016): 16–34. doi:10.1016/j.tcs.2016.04.039
info:cnr-pdr/source/autori:Fici, Gabriele; Langiu, Alessio; Lecroq, Thierry; Lefebvre, Arnaud; Mignosi, Filippo; Peltomäki, Jarkko; Prieur-Gaston, Élise/titolo:Abelian powers and repetitions in Sturmian words/doi:10.1016%2Fj.tcs.2016.04.039/rivista:Theoretical computer science/anno:2016/pagina_da:16/pagina_a:34/intervallo_pagine:16–34/volume:635
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2016, 635, pp.16-34. ⟨10.1016/j.tcs.2016.04.039⟩
Fici, G, Langiu, A, Lecroq, T, Lefebvre, A, Mignosi, F, Peltomäki, J & Prieur-Gaston, É 2016, ' Abelian powers and repetitions in Sturmian words ', Theoretical Computer Science . https://doi.org/10.1016/j.tcs.2016.04.039

Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian power

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::92f85ad06f065b9feed476c54cd14447
https://hal.archives-ouvertes.fr/hal-01956122

On shortest crucial words avoiding abelian powers

Autor: Sergey Kitaev, Sergey Avgustinovich, Amy Glen, Bjarni V. Halldorsson

Publikováno v: Discrete Applied Mathematics. 158:605-607

Let k>=2 be an integer. An abeliankth power is a word of the form X"1X"2...X"k where X"i is a permutation of X"1 for 2@?i@?k. A word W is said to be crucial with respect to abelian kth powers if W avoids abelian kth powers, but Wx ends with an abelia

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::b3885b1a6ffdc3bbfebbd2719672db5a
https://doi.org/10.1016/j.dam.2009.11.010