Zobrazeno 1 - 10
of 57
pro vyhledávání: '"Freydenberger, Dominik D."'
Despite considerable research on document spanners, little is known about the expressive power of generalized core spanners. In this paper, we use Ehrenfeucht-Fra\"iss\'e games to obtain general inexpressibility lemmas for the logic FC (a finite-mode
Externí odkaz:
http://arxiv.org/abs/2306.16364
This paper investigates regex CQs with string equalities (SERCQs), a subclass of core spanners. As shown by Freydenberger, Kimelfeld, and Peterfreund (PODS 2018), these queries are intractable, even if restricted to acyclic queries. This previous res
Externí odkaz:
http://arxiv.org/abs/2104.04758
We propose FC, a new logic on words that combines finite model theory with the theory of concatenation - a first-order logic that is based on word equations. Like the theory of concatenation, FC is built around word equations; in contrast to it, its
Externí odkaz:
http://arxiv.org/abs/1912.06110
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
The present paper investigates the dynamic complexity of document spanners, a formal framework for information extraction introduced by Fagin, Kimelfeld, Reiss, and Vansummeren (JACM 2015). We first look at the class of regular spanners and prove tha
Externí odkaz:
http://arxiv.org/abs/1909.10869
We investigate the complexity of evaluating queries in Relational Algebra (RA) over the relations extracted by regex formulas (i.e., regular expressions with capture variables) over text documents. Such queries, also known as the regular document spa
Externí odkaz:
http://arxiv.org/abs/1901.04182
Most modern libraries for regular expression matching allow back-references (i.e., repetition operators) that substantially increase expressive power, but also lead to intractability. In order to find a better balance between expressiveness and tract
Externí odkaz:
http://arxiv.org/abs/1802.01508
Regular expressions with capture variables, also known as "regex formulas," extract relations of spans (interval positions) from text. These relations can be further manipulated via Relational Algebra as studied in the context of document spanners, F
Externí odkaz:
http://arxiv.org/abs/1703.10350
Autor:
Freydenberger, Dominik D., Gawrychowski, Pawel, Karhumäki, Juhani, Manea, Florin, Rytter, Wojciech
Publikováno v:
"Multidisciplinary Creativity: homage to Gheorghe Paun on his 65th birthday", Pg. 239--248, Ed. Spandugino, Bucharest, Romania, ISBN: 978-606-8401-63-8, 2015
Two words $w_1$ and $w_2$ are said to be $k$-binomial equivalent if every non-empty word $x$ of length at most $k$ over the alphabet of $w_1$ and $w_2$ appears as a scattered factor of $w_1$ exactly as many times as it appears as a scattered factor o
Externí odkaz:
http://arxiv.org/abs/1509.00622
Publikováno v:
In Information and Computation November-December 2012 220-221:15-43
