Zobrazeno 1 - 10
of 192
pro vyhledávání: '"Smyth, W. F."'
We say that a family $\mathcal{W}$ of strings over $\Sigma^+$ forms a Unique Maximal Factorization Family (UMFF) if and only if every $w \in \mathcal{W}$ has a unique maximal factorization. Further, an UMFF $\mathcal{W}$ is called a circ-UMFF wheneve
Externí odkaz:
http://arxiv.org/abs/2409.02757
Autor:
Mhaskar, Neerja, Smyth, W. F.
Publikováno v:
Fundamenta Informaticae, Volume 190, Issue 1 (October 14, 2023) fi:10368
The study of strings is an important combinatorial field that precedes the digital computer. Strings can be very long, trillions of letters, so it is important to find compact representations. Here we first survey various forms of one potential compa
Externí odkaz:
http://arxiv.org/abs/2211.11856
In this paper we describe two simple, fast, space-efficient algorithms for finding all matches of an indeterminate pattern $p = p[1..m]$ in an indeterminate string $x = x[1..n]$, where both $p$ and $x$ are defined on a "small" ordered alphabet $\Sigm
Externí odkaz:
http://arxiv.org/abs/2204.08331
In this paper we propose a new, more appropriate definition of regular and indeterminate strings. A regular string is one that is "isomorphic" to a string whose entries all consist of a single letter, but which nevertheless may itself include entries
Externí odkaz:
http://arxiv.org/abs/2012.07892
In this note, we obtain an upper bound on the maximum number of distinct non-empty palindromes in starlike trees. This bound implies, in particular, that there are at most $4n$ distinct non-empty palindromes in a starlike tree with three branches eac
Externí odkaz:
http://arxiv.org/abs/1805.10646
We introduce the Parikh-de-Bruijn grid, a graph whose vertices are fixed-order Parikh vectors, and whose edges are given by a simple shift operation. This graph gives structural insight into the nature of sets of Parikh vectors as well as that of the
Externí odkaz:
http://arxiv.org/abs/1711.06264
Publikováno v:
Journal of Discrete Algorithms, 50 (2018), 2-9
In this paper we present an algorithm to compute the Lyndon array of a string $T$ of length $n$ as a byproduct of the inversion of the Burrows-Wheeler transform of $T$. Our algorithm runs in linear time using only a stack in addition to the data stru
Externí odkaz:
http://arxiv.org/abs/1710.10105
Recently the Fibonacci word $W$ on an infinite alphabet was introduced by [Zhang et al., Electronic J. Combinatorics 24-2 (2017) #P2.52] as a fixed point of the morphism $\phi: (2i) \mapsto (2i)(2i+ 1),\ (2i+ 1) \mapsto (2i+ 2)$ over all $i \in \math
Externí odkaz:
http://arxiv.org/abs/1710.02782
In this paper, we determine the maximum number of distinct Lyndon factors that a word of length $n$ can contain. We also derive formulas for the expected total number of Lyndon factors in a word of length $n$ on an alphabet of size $\sigma$, as well
Externí odkaz:
http://arxiv.org/abs/1701.00928
We first describe three algorithms for computing the Lyndon array that have been suggested in the literature, but for which no structured exposition has been given. Two of these algorithms execute in quadratic time in the worst case, the third achiev
Externí odkaz:
http://arxiv.org/abs/1605.08935