LIPIcs-ICDT-2020-11.pdf (707.79 kB)
Dynamic complexity of document spanners
conference contribution
posted on 2020-01-13, 11:03 authored by Dominik FreydenbergerDominik Freydenberger, Sam ThompsonThe 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 that any regular spanner can be maintained in the dynamic complexity class DynPROP. This result follows from work done previously on the dynamic complexity of formal languages by Gelade, Marquardt, and Schwentick (TOCL 2012). To investigate core spanners we use SpLog, a concatenation logic that exactly captures core spanners. We show that the dynamic complexity class DynCQ, is more expressive than SpLog and therefore can maintain any core spanner. This result is then extended to show that DynFO can maintain any generalized core spanner and that DynFO is more powerful than SpLog with negation.
History
School
- Science
Department
- Computer Science
Published in
23rd International Conference on Database Theory (ICDT 2020)Volume
155Pages
11:1 - 11:21Source
23rd International Conference on Database Theory (ICDT 2020)Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl PublishingVersion
- VoR (Version of Record)
Rights holder
© Dominik D. Freydenberger and Sam M. ThompsonPublisher statement
This is an Open Access Article. It is published by Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing under the Creative Commons Attribution 3.0 Unported Licence (CC BY). Full details of this licence are available at: http://creativecommons.org/licenses/by/3.0/Acceptance date
2019-12-19Publication date
2020-03-11Copyright date
2020ISBN
9783959771399ISSN
1868-8969Publisher version
Book series
Leibniz International Proceedings in Informatics (LIPIcs)Language
- en
Editor(s)
Carsten Lutz, Jean Christoph JungLocation
Copenhagen, DenmarkEvent dates
30th March 2020 - 2nd April 2020Depositor
Dr Dominik Freydenberger. Deposit date: 10 January 2020Article number
11Usage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC