Zobrazeno 1 - 10
of 460
pro vyhledávání: '"Manea Florin"'
For two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap constraint is a triple (i, j, C_{i, j}), where 1 <= i < j <= |u| and C_{
Externí odkaz:
http://arxiv.org/abs/2404.10497
Modern SMT solvers, such as Z3, offer user-controllable strategies, enabling users to tailor solving strategies for their unique set of instances, thus dramatically enhancing solver performance for their use case. However, this approach of strategy c
Externí odkaz:
http://arxiv.org/abs/2401.17159
In this paper, we provide a novel enumeration algorithm for the set of all walks of a given length within a directed graph. Our algorithm has worst-case constant delay between outputting succinct representations of such walks, after a preprocessing s
Externí odkaz:
http://arxiv.org/abs/2401.02163
A subsequence of a word $w$ is a word $u$ such that $u = w[i_1] w[i_2] \dots w[i_{k}]$, for some set of indices $1 \leq i_1 < i_2 < \dots < i_k \leq \lvert w\rvert$. A word $w$ is $k$-subsequence universal over an alphabet $\Sigma$ if every word in $
Externí odkaz:
http://arxiv.org/abs/2311.10658
Autor:
Fleischmann, Pamela, Kim, Sungmin, Koß, Tore, Manea, Florin, Nowotka, Dirk, Siemer, Stefan, Wiedenhöft, Max
We introduce and investigate a series of matching problems for patterns with variables under Simon's congruence. Our results provide a thorough picture of these problems' computational complexity.
Externí odkaz:
http://arxiv.org/abs/2308.08374
Autor:
Day, Joel D.1 (AUTHOR) J.Day@lboro.ac.uk, Manea, Florin2 (AUTHOR)
Publikováno v:
Theory of Computing Systems. Aug2024, Vol. 68 Issue 4, p662-739. 78p.
We study extensions of Sem\"enov arithmetic, the first-order theory of the structure $(\mathbb{N}, +, 2^x)$. It is well-knonw that this theory becomes undecidable when extended with regular predicates over tuples of number strings, such as the B\"uch
Externí odkaz:
http://arxiv.org/abs/2306.14593
We consider the longest common subsequence problem in the context of subsequences with gap constraints. In particular, following Day et al. 2022, we consider the setting when the distance (i. e., the gap) between two consecutive symbols of the subseq
Externí odkaz:
http://arxiv.org/abs/2304.05270