Zobrazeno 1 - 10
of 112
pro vyhledávání: '"Diptarama"'
Publikováno v:
Electronic Proceedings in Theoretical Computer Science, Vol 305, Iss Proc. GandALF 2019, Pp 140-153 (2019)
We propose a query learning algorithm for residual symbolic finite automata (RSFAs). Symbolic finite automata (SFAs) are finite automata whose transitions are labeled by predicates over a Boolean algebra, in which a big collection of characters leadi
Externí odkaz:
https://doaj.org/article/49f2233ff7f54c648f6d21a958f2e16b
We introduce height-bounded LZ encodings (LZHB), a new family of compressed representations that are variants of Lempel-Ziv parsings with a focus on bounding the worst-case access time to arbitrary positions in the text directly via the compressed re
Externí odkaz:
http://arxiv.org/abs/2403.08209
Lyndon words are extensively studied in combinatorics on words -- they play a crucial role on upper bounding the number of runs a word can have [Bannai+, SIAM J. Comput.'17]. We can determine Lyndon words, factorize a word into Lyndon words in lexico
Externí odkaz:
http://arxiv.org/abs/2403.02636
Autor:
Iseri, Kento, I, Tomohiro, Hendrian, Diptarama, Köppl, Dominik, Yoshinaka, Ryo, Shinohara, Ayumi
A parameterized string (p-string) is a string over an alphabet $(\Sigma_{s} \cup \Sigma_{p})$, where $\Sigma_{s}$ and $\Sigma_{p}$ are disjoint alphabets for static symbols (s-symbols) and for parameter symbols (p-symbols), respectively. Two p-string
Externí odkaz:
http://arxiv.org/abs/2308.05977
The parameterized matching problem is a variant of string matching, which is to search for all parameterized occurrences of a pattern $P$ in a text $T$. In considering matching algorithms, the combinatorial natures of strings, especially periodicity,
Externí odkaz:
http://arxiv.org/abs/2306.10714
Publikováno v:
Algorithms, Vol 12, Iss 4, p 73 (2019)
A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this pa
Externí odkaz:
https://doaj.org/article/4a62dbb11cc14fd0ba9e2be7fa549cc2
The suffix trees are fundamental data structures for various kinds of string processing. The suffix tree of a text string $T$ of length $n$ has $O(n)$ nodes and edges, and the string label of each edge is encoded by a pair of positions in $T$. Thus,
Externí odkaz:
http://arxiv.org/abs/2301.04295
Position heaps are index structures of text strings used for the string matching problem. They are rooted trees whose edges and nodes are labeled and numbered, respectively. This paper is concerned with variants of the inverse problem of position hea
Externí odkaz:
http://arxiv.org/abs/2209.12405
Parameterized strings are a generalization of strings in that their characters are drawn from two different alphabets, where one is considered to be the alphabet of static characters and the other to be the alphabet of parameter characters. Two param
Externí odkaz:
http://arxiv.org/abs/2206.15100
Publikováno v:
In Theoretical Computer Science 1 November 2024 1015