FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras

Author: Matthias Niewerth

Paper Information

Title:MSO Queries on Trees: Enumerating Answers under Updates Using Forest Algebras
Authors:Matthias Niewerth
Proceedings:LICS PDF files
Editors: Anuj Dawar and Erich Gr├Ądel
Keywords:Query Enumeration, Trees, MSO, Forest Algebra
Abstract:

ABSTRACT. We investigate efficient view maintenance for MSO-definable queries over trees or, more precisely, efficient enumeration of answers to MSO-definable queries over trees which are subject to local updates.

We exhibit an algorithm that uses an O(n) preprocessing phase and enumerates answers with O(log(n)) delay between them. When the tree is updated, the algorithm can avoid repeating expensive preprocessing and restart the enumeration phase within O(log(n)) time. This improves over previous results that require O(log^2(n)) time after updates and have O(log^2(n)) delay.

Our algorithms and complexity results in the paper are presented in terms of node-selecting tree automata representing the MSO queries. To present our algorithm, we introduce a balancing scheme for parse trees of forest algebra formulas that is of its own interest.

Pages:10
Talk:Jul 10 12:20 (Session 54D)
Paper: