Enumeration on Trees with Tractable Combined Complexity and Efficient Updates
| Autor: | Antoine Amarilli, Matthias Niewerth, Pierre Bourhis, Stefan Mengel |
|---|---|
| Přispěvatelé: | Data, Intelligence and Graphs (DIG), Laboratoire Traitement et Communication de l'Information (LTCI), Institut Mines-Télécom [Paris] (IMT)-Télécom Paris-Institut Mines-Télécom [Paris] (IMT)-Télécom Paris, Département Informatique et Réseaux (INFRES), Télécom ParisTech, Self-adaptation for distributed services and large software systems (SPIRALS), Inria Lille - Nord Europe, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS)-Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 (CRIStAL), Centrale Lille-Université de Lille-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria), Centre de Recherche en Informatique de Lens (CRIL), Université d'Artois (UA)-Centre National de la Recherche Scientifique (CNRS), Universität Bayreuth, ANR-16-CE40-0007,DELTA,DÉfis pour la Logique, les Transducteurs et les Automates(2016) |
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Polynomial Computer Science - Logic in Computer Science Theoretical computer science Formal Languages and Automata Theory (cs.FL) Computer science Context (language use) Computer Science - Formal Languages and Automata Theory 0102 computer and information sciences 02 engineering and technology 01 natural sciences Computer Science - Databases 020204 information systems Computer Science - Data Structures and Algorithms 0202 electrical engineering electronic engineering information engineering Enumeration Data Structures and Algorithms (cs.DS) [INFO]Computer Science [cs] Time complexity ComputingMilieux_MISCELLANEOUS [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB] Databases (cs.DB) Data structure Logic in Computer Science (cs.LO) Automaton Nondeterministic algorithm Tree (data structure) 010201 computation theory & mathematics Node (circuits) Computer Science::Formal Languages and Automata Theory |
| Zdroj: | PODS PODS, Jun 2019, Amsterdam, France. pp.89-103, ⟨10.1145/3294052.3319702⟩ |
| Popis: | We give an algorithm to enumerate the results on trees of monadic second-order (MSO) queries represented by nondeterministic tree automata. After linear time preprocessing (in the input tree), we can enumerate answers with linear delay (in each answer). We allow updates on the tree to take place at any time, and we can then restart the enumeration after logarithmic time in the tree. Further, all our combined complexities are polynomial in the automaton. Our result follows our previous circuit-based enumeration algorithms based on deterministic tree automata, and is also inspired by our earlier result on words and nondeterministic sequential extended variable-set automata in the context of document spanners. We extend these results and combine them with a recent tree balancing scheme by Niewerth, so that our enumeration structure supports updates to the underlying tree in logarithmic time (with leaf insertions, leaf deletions, and node relabelings). Our result implies that, for MSO queries with free first-order variables, we can enumerate the results with linear preprocessing and constant-delay and update the underlying tree in logarithmic time, which improves on several known results for words and trees. Building on lower bounds from data structure research, we also show unconditionally that up to a doubly logarithmic factor the update time of our algorithm is optimal. Thus, unlike other settings, there can be no algorithm with constant update time. 16 pages of main material, 37 references, 11 pages of appendix. This is the extended version with proofs of the PODS'19 paper. Except for minor rephrasings and formatting differences, the contents are exactly the same as the version published in the PODS'19 proceedings |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|