MSO Queries on Trees: Enumerating Answers under Updates

We investigate efficient view maintenance for MSO-definable queries over trees or, more precisely, efficient enumeration of answers to MSO-definable queries over words and trees which are subject to local updates. For words we exhibit an algorithm that uses an O ( n ) preprocessing phase and enumerates answers with O (log n ) delay between them. When the word is updated, the algorithm can avoid repeating expensive preprocessing and restart the enumeration phase within O (log n ) time. For trees, our algorithm uses O ( n ) preprocessing time, enumerates answers with O (log 2 n ) delay, and can restart enumeration within O (log 2 n ) time after receiving an update to the tree. This significantly improves the cost of recomputing the answers of a query from scratch. Our algorithms and complexity results in the paper are presented in terms of node-selecting automata representing the MSO queries.

Authors

• Katja Losemann

Keywords

No keywords are indexed for this paper.