Zobrazeno 1 - 10
of 66
pro vyhledávání: '"Arseny M. Shur"'
Autor:
Elena A. Petrova, Arseny M. Shur
Publikováno v:
Algorithms, Vol 14, Iss 4, p 126 (2021)
Binary cube-free language and ternary square-free language are two “canonical” representatives of a wide class of languages defined by avoidance properties. Each of these two languages can be viewed as an infinite binary tree reflecting the prefi
Externí odkaz:
https://doaj.org/article/7a0de29ce7294823a93c65365d08bce8
Autor:
Irina A. Gorbunova, Arseny M. Shur
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 63, Iss Proc. WORDS 2011, Pp 138-146 (2011)
The recently confirmed Dejean's conjecture about the threshold between avoidable and unavoidable powers of words gave rise to interesting and challenging problems on the structure and growth of threshold words. Over any finite alphabet with k >= 5 le
Externí odkaz:
https://doaj.org/article/5205aab700664a099b8fcecac0ef0567
Autor:
Elena A. Petrova, Arseny M. Shur
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 63, Iss Proc. WORDS 2011, Pp 168-178 (2011)
We study the structure of the language of binary cube-free words. Namely, we are interested in the cube-free words that cannot be infinitely extended preserving cube-freeness. We show the existence of such words with arbitrarily long finite extension
Externí odkaz:
https://doaj.org/article/0fe6f6a52e3f4b97a0b4406b788cef64
Autor:
Arseny M. Shur
Publikováno v:
Developments in Language Theory ISBN: 9783031332630
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::a0d156f14f914f9126834bcf55115731
https://doi.org/10.1007/978-3-031-33264-7_18
https://doi.org/10.1007/978-3-031-33264-7_18
Publikováno v:
Theoretical Computer Science
We study the threshold between avoidable and unavoidable repetitions in infinite balanced sequences over finite alphabets. The conjecture stated by Rampersad, Shallit and Vandomme says that the minimal critical exponent of balanced sequences over the
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f266244b62a07634a6c7baac31b96cc2
https://hdl.handle.net/10995/117863
https://hdl.handle.net/10995/117863
Autor:
Dmitry Kosolobov, Arseny M. Shur
Publikováno v:
Inf. Process. Lett.
Information Processing Letters
Information Processing Letters
We investigate the relations between different variants of the LZ77 parsing existing in the literature. All of them are defined as greedily constructed parsings encoding each phrase by reference to a string occurring earlier in the input. They differ
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::de5df621e9727ed3f5dc257808b0e0c5
https://doi.org/10.1016/j.ipl.2018.09.005
https://doi.org/10.1016/j.ipl.2018.09.005
Autor:
Elena A. Petrova, Arseny M. Shur
Publikováno v:
Developments in Language Theory ISBN: 9783030815073
DLT
DLT
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=doi_________::6e306f02907d14be8c9d764eea9e8fb4
https://doi.org/10.1007/978-3-030-81508-0_27
https://doi.org/10.1007/978-3-030-81508-0_27
Autor:
Arseny M. Shur, Daniil Gasnikov
Publikováno v:
International Journal of Foundations of Computer Science. 29:845-860
We contribute to the study of square-free words. The classical notion of a square-free word has a natural generalization to partial words, studied in several papers since 2008. We prove that the maximal density of wildcards in the ternary infinite sq
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::20498d2c467aad521c5245b1e33e0eb1
https://doi.org/10.1142/s0129054118420078
https://doi.org/10.1142/s0129054118420078
Publikováno v:
Inf. Process. Lett.
Information Processing Letters
Information Processing Letters
A length n word is (palindromic) rich if it contains the maximum possible number, which is n, of distinct non-empty palindromic factors. We prove both necessary and sufficient conditions for richness in terms of run-length encodings of words. Relatin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e608a8645420a478d6f8194a308e094c
https://doi.org/10.1016/j.ipl.2016.07.001
https://doi.org/10.1016/j.ipl.2016.07.001
Autor:
Oleg Merkurev, Arseny M. Shur
Publikováno v:
String Processing and Information Retrieval ISBN: 9783030326852
SPIRE
SPIRE
Runs, or maximal periodic substrings, capture the whole picture of periodic fragments in a string. Computing all runs of a string in the usual RAM model is a well-studied problem. We approach this problem in the streaming model, where input symbols a
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::5324aba30ead6e0d0655f1bb11476726
https://doi.org/10.1007/978-3-030-32686-9_15
https://doi.org/10.1007/978-3-030-32686-9_15