Výsledky vyhledávání

Akademický článek

Autor: Esteban Gabory, Moses Njagi Mwaniki, Nadia Pisanti, Solon P. Pissis, Jakub Radoszewski, Michelle Sweering, Wiktor Zuba

Publikováno v: Frontiers in Bioinformatics, Vol 4 (2024)

IntroductionAn elastic-degenerate (ED) string is a sequence of sets of strings. It can also be seen as a directed acyclic graph whose edges are labeled by strings. The notion of ED strings was introduced as a simple alternative to variation and seque

Externí odkaz: https://doaj.org/article/0fbb0868164048a0936e75501aa9841c

Zobrazit plný text záznamu

Finding the cyclic covers of a string

Autor: Roberto Grossi, Costas S. Iliopoulos, Jesper Jansson, Zara Lim, Wing-Kin Sung, Wiktor Zuba

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783031270505

We introduce the concept of cyclic covers, which generalizes the classical notion of covers in strings. Given any nonempty string X of length n, a factor W of X is called a cyclic cover if every position of X belongs to an occurrence of a cyclic shif

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::302c4d8b16d516be1c624952dbd8e713
https://ir.cwi.nl/pub/32986

Zobrazit plný text záznamu

Shortest covers of all cyclic shifts of a string

Autor: Maxime Crochemore, Costas S. Iliopoulos, Jakub Radoszewski, Wojciech Rytter, Juliusz Straszyński, Tomasz Waleń, Wiktor Zuba

Publikováno v: Theoretical Computer Science. 866:70-81

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::aa0d59f07363f9d4b80dc633f1b978c4
https://doi.org/10.1016/j.tcs.2021.03.011

Zobrazit plný text záznamu

Efficient representation and counting of antipower factors in words

Autor: Juliusz Straszyński, Tomasz Kociumaka, Wiktor Zuba, Wojciech Rytter, Tomasz Waleń, Jakub Radoszewski

Publikováno v: Information and Computation. 286:104779

A k-antipower (for k ≥ 2 ) is a concatenation of k distinct words of the same length. Fici et al. (ICALP 2016) initiated the study of antipowers occurring as fragments of a word, whereas Badkobeh et al. (Inf. Process. Lett., 2018) presented first a

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::346d47f2781b5611cf0d55cf4fbfead6
https://doi.org/10.1016/j.ic.2021.104779

Zobrazit plný text záznamu

String Covers of a Tree

Autor: Juliusz Straszyński, Jakub Radoszewski, Wiktor Zuba, Wojciech Rytter, Tomasz Waleń

Publikováno v: String Processing and Information Retrieval ISBN: 9783030866914
SPIRE

We consider covering labeled trees by a collection of paths with the same string label, called a (string) cover of a tree. We show how to compute all covers of a directed (rooted) labeled tree in ${\mathcal {O}}(n \log n/\log \log n)$ time and all

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::ad4eb35a587d41f13438cf2ff53844bd
https://doi.org/10.1007/978-3-030-86692-1_7

Zobrazit plný text záznamu

Efficient Enumeration of Distinct Factors Using Package Representations

Autor: Wiktor Zuba, Panagiotis Charalampopoulos, Wojciech Rytter, Tomasz Kociumaka, Tomasz Waleń, Jakub Radoszewski

Publikováno v: String Processing and Information Retrieval ISBN: 9783030592110
SPIRE

We investigate properties and applications of a new compact representation of string factors: families of packages. In a string T, each package $(i,\ell ,k)$ represents the factors of T of length $\ell $ that start in the interval $[i,i+k]$. A

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::099040dc233d25506a04ea20e929ef2c
https://doi.org/10.1007/978-3-030-59212-7_18

Zobrazit plný text záznamu

Shortest Covers of All Cyclic Shifts of a String

Autor: Wiktor Zuba, Juliusz Straszyński, Maxime Crochemore, Tomasz Waleń, Wojciech Rytter, Jakub Radoszewski, Costas S. Iliopoulos

Publikováno v: WALCOM: Algorithms and Computation ISBN: 9783030398804
WALCOM

A factor W of a string X is called a cover of X, if X can be constructed by concatenations and superpositions of W. Breslauer (IPL, 1992) proposed a well-known $\mathcal {O}(n)$-time algorithm that computes the shortest cover of every prefix of a s

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::fd7755986406daadee0fa04d978ec63d
https://doi.org/10.1007/978-3-030-39881-1_7

Zobrazit plný text záznamu

Circular Pattern Matching with $k$ Mismatches

Autor: Solon P. Pissis, Tomasz Waleń, Tomasz Kociumaka, Juliusz Straszyński, Wiktor Zuba, Jakub Radoszewski, Wojciech Rytter, Panagiotis Charalampopoulos

Publikováno v: Fundamentals of Computation Theory ISBN: 9783030250263
FCT
Journal of Computer and System Sciences
Journal of Computer and System Sciences, Elsevier, 2021, 115, pp.73-85. ⟨10.1016/j.jcss.2020.07.003⟩
Journal of Computer and System Sciences, 115, 73-85
Charalampopoulos, P, Kociumaka, T, Pissis, S P, Radoszewski, J, Rytter, W, Straszyński, J, Waleń, T & Zuba, W 2021, ' Circular pattern matching with k mismatches ', Journal of Computer and System Sciences, vol. 115, pp. 73-85 . https://doi.org/10.1016/j.jcss.2020.07.003
Journal of Computer and System Sciences, 115, 73-85. Elsevier
Journal of Computer and System Sciences, 2021, 115, pp.73-85. ⟨10.1016/j.jcss.2020.07.003⟩

The $k$-mismatch problem consists in computing the Hamming distance between a pattern $P$ of length $m$ and every length-$m$ substring of a text $T$ of length $n$, if this distance is no more than $k$. In many real-world applications, any cyclic rota

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::041ed6040f1afa64539671181094359b
http://arxiv.org/abs/1907.01815

Zobrazit plný text záznamu

Syntactic View of Sigma-Tau Generation of Permutations

Autor: Wojciech Rytter, Wiktor Zuba

We give a syntactic view of the Sawada-Williams $(\sigma,\tau)$-generation of permutations. The corresponding sequence of $\sigma-\tau$-operations, of length $n!-1$ is shown to be highly compressible: it has $O(n^2\log n)$ bit description. Using this

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0183b439536ed8b022ad2afc3aed2d85

Zobrazit plný text záznamu

Efficient Representation and Counting of Antipower Factors in Words

Autor: Wiktor Zuba, Tomasz Kociumaka, Wojciech Rytter, Juliusz Straszyński, Jakub Radoszewski, Tomasz Waleń

Publikováno v: Language and Automata Theory and Applications ISBN: 9783030134341
LATA

A k-antipower (for $k \ge 2$) is a concatenation of k pairwise distinct words of the same length. The study of antipower factors of a word was initiated by Fici et al. (ICALP 2016) and first algorithms for computing antipower factors were presented

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::0177a5fb9d5b92941bd81c8eea1256c6
https://doi.org/10.1007/978-3-030-13435-8_31

Zobrazit plný text záznamu

Vyhledávací nástroje:

Upřesnit hledání