Zobrazeno 1 - 10
of 74
pro vyhledávání: '"Badkobeh, Golnaz"'
We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that for any string $w$, a bidirectional macro scheme of size $O(r_B)$ can be induced from the BBWT of $w$, where $r_B$ is the number of maximal character runs in th
Externí odkaz:
http://arxiv.org/abs/2406.16475
Autor:
Badkobeh, Golnaz, Ochem, Pascal
An interesting phenomenon in combinatorics on words is when every recurrent word satisfying some avoidance constraints has the same factor set as a morphic word. An early example is the Hall-Thue word, fixed point of the morphism $\texttt{0}\to\textt
Externí odkaz:
http://arxiv.org/abs/2312.10757
A string is closed if it has length 1 or has a nonempty border without internal occurrences. In this paper we introduce the definition of a \emph{maximal closed substring} (MCS), which is an occurrence of a closed substring that cannot be extended to
Externí odkaz:
http://arxiv.org/abs/2209.00271
Given a string $T$ of length $n$ over an alphabet $\Sigma\subset \{1,2,\ldots,n^{O(1)}\}$ of size $\sigma$, we are to preprocess $T$ so that given a range $[i,j]$, we can return a representation of a shortest string over $\Sigma$ that is absent in th
Externí odkaz:
http://arxiv.org/abs/2106.01763
We consider sets of factors that can be avoided in square-free words on two-generator free groups. The elements of the group are presented in terms of 0,1,2,3 such that 0 and 2 (resp.,1 and 3) are inverses of each other so that 02, 20, 13 and 31 do n
Externí odkaz:
http://arxiv.org/abs/2104.06837
Autor:
Badkobeh, Golnaz, Crochemore, Maxime
We extend the left-to-right Lyndon factorisation of a word to the left Lyndon tree construction of a Lyndon word. It yields an algorithm to sort the prefixes of a Lyndon word according to the infinite ordering defined by Dolce et al. (2019). A straig
Externí odkaz:
http://arxiv.org/abs/2011.12742
A word $x$ that is absent from a word $y$ is called minimal if all its proper factors occur in $y$. Given a collection of $k$ words $y_1,y_2,\ldots,y_k$ over an alphabet $\Sigma$, we are asked to compute the set $\mathrm{M}^{\ell}_{y_{1}\#\ldots\#y_{
Externí odkaz:
http://arxiv.org/abs/1902.04785
Autor:
Badkobeh, Golnaz, Ochem, Pascal
We construct an infinite word $w$ over the $5$-letter alphabet such that for every factor $f$ of $w$ of length at least two, there exists a cyclic permutation of $f$ that is not a factor of $w$. In other words, $w$ does not contain a non-trivial conj
Externí odkaz:
http://arxiv.org/abs/1811.08231
Publikováno v:
Published in Informnation Processing Letters Volume 137, September 2018, Pages 57-60
A string $S[1,n]$ is a power (or tandem repeat) of order $k$ and period $n/k$ if it can decomposed into $k$ consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient comput
Externí odkaz:
http://arxiv.org/abs/1805.10042
Autor:
Badkobeh, Golnaz, Crochemore, Maxime
Publikováno v:
In Information and Computation May 2022 285 Part B
