Freydenberger.pdf (609.67 kB)
A logic for document spanners
conference contribution
posted on 2017-03-10, 11:36 authored by Dominik FreydenbergerDominik FreydenbergerDocument spanners are a formal framework for information extraction that was introduced by
Fagin, Kimelfeld, Reiss, and Vansummeren (PODS 2013, JACM 2015). One of the central models in this framework are core spanners, which are based on regular expressions with variables that are then extended with an algebra. As shown by Freydenberger and Holldack (ICDT 2016), there is a connection between core spanners and ECreg, the existential theory of concatenation with
regular constraints. The present paper further develops this connection by defining SpLog, a fragment of ECreg that has the same expressive power as core spanners. This equivalence extends beyond equivalence of expressive power, as we show the existence of polynomial time conversions between this fragment and core spanners. This even holds for variants of core spanners that are based on automata instead of regular expressions. Applications of this approach include an
alternative way of defining relations for spanners, insights into the relative succinctness of various classes of spanner representations, and a pumping lemma for core spanners.
Funding
This research was supported by Deutsche Forschungsgemeinschaft (DFG) under grant FR 3551/1-1.
History
School
- Science
Department
- Computer Science
Published in
International Conference on Database TheoryCitation
FREYDENBERGER, D.D., 2017. A Logic for Document Spanners. Presented at the International Conference on Database Theory (ICDT 2017), Venice, Italy, Mar 21-24th.Publisher
Schloss Dagstuhl – Leibniz Center for InformaticsVersion
- VoR (Version of Record)
Publisher statement
This work is made available according to the conditions of the Creative Commons Attribution 4.0 International (CC BY 4.0) licence. Full details of this licence are available at: http://creativecommons.org/licenses/ by/4.0/Acceptance date
2016-05-28Publication date
2017Notes
This is an Open Access Article. It is published by Schloss Dagstuhl under the Creative Commons Attribution 4.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/4.0/ISBN
9783959770248ISSN
1868-8969Publisher version
Book series
Leibniz International Proceedings in Informatics (LIPIcs); 68Language
- en