Skip to Main content Skip to Navigation
New interface
Conference papers

Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates

Matthias Niewerth 1 Luc Segoufin 2 
2 VALDA - Value from Data
DI-ENS - Département d'informatique - ENS Paris, Inria de Paris
Abstract : We consider the enumeration of MSO queries over strings under updates. For each MSO query we build an index structure enjoying the following properties: The index structure can be constructed in linear time, it can be updated in logarithmic time and it allows for constant delay time enumeration. This improves from the previous known index structures allowing for constant delay enumeration that would need to be reconstructed from scratch, hence in linear time, in the presence of updates. We allow relabeling updates, insertion of individual labels and removal of individual labels.
Document type :
Conference papers
Complete list of metadata

Cited literature [21 references]  Display  Hide  Download
Contributor : Luc Segoufin Connect in order to contact the contributor
Submitted on : Tuesday, October 16, 2018 - 9:55:31 AM
Last modification on : Wednesday, June 8, 2022 - 12:50:06 PM
Long-term archiving on: : Thursday, January 17, 2019 - 12:49:19 PM


Files produced by the author(s)




Matthias Niewerth, Luc Segoufin. Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates. Principles of Databse Systems, PODS'18, Jun 2018, Houston, United States. ⟨10.1145/3196959.3196961⟩. ⟨hal-01895796⟩



Record views


Files downloads