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

Summary: For every MSO query on strings, builds a linear-time index supporting relabeling and single-symbol insertions/deletions in logarithmic time. Enumeration retains constant delay, avoiding the linear-time reconstruction required by prior dynamic indexes. (summarized by gpt-5.6-luna on Jul 26 2026)

Paper ID: 1740
Venue: PODS
Year: 2018
Pagerank: 6.9038261e-05
Overall Rank: 4,097 | 71.90%
DOI: 10.1145/3196959.3196961

Incoming Non-self Citations Over Time

Authors

1. Matthias Niewerth (University of Bayreuth)
2. Luc Segoufin (INRIA; École Normale Supérieure)

BibTeX Citation

@inproceedings{niewerth_pods18,
        address = {New York, NY, USA},
        series = {{PODS} '18},
        title = {{Enumeration of MSO Queries on Strings with Constant Delay and Logarithmic Updates}},
        url = {https://dl.acm.org/doi/10.1145/3196959.3196961},
        doi = {10.1145/3196959.3196961},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Niewerth, Matthias and Segoufin, Luc},
        year = {2018}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,468	On the Enumeration Complexity of Unions of Conjunctive Queries	2019	PODS	8.5358494e-05
4,063	Enumeration for FO Queries over Nowhere Dense Graphs	2018	PODS	6.9307541e-05
5,123	Complexity Bounds for Relational Algebra over Document Spanners	2019	PODS	6.3571407e-05
5,579	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS	6.1637419e-05
9,819	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS	5.214913e-05
10,163	Optimal Enumeration of Regular Pattern Matches	2026	PODS	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
636	Answering Conjunctive Queries under Updates	2017	PODS	0.0001551856
5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS	6.3897022e-05
13,596	Enumerating Answers to First-Order Queries over Databases of Low Degree	2014	PODS	-

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,003	Indexing for Data Models with Constraints and Classes (Extended Abstract)	1993	PODS
2	2,777	Answering (Unions of) Conjunctive Queries using Random Access and Random-Order Enumeration	2020	PODS
3	6,753	Optimal Indexing Using Near-Minimal Space [Extended Abstract]	2003	PODS
4	1,611	Indexing Moving Points (Extended Abstract)	2000	PODS
5	12,490	Secondary Indexing in One Dimension: Beyond B-trees and Bitmap Indexes	2009	PODS
6	9,819	Probabilistic Databases under Updates: Boolean Query Evaluation and Ranked Enumeration	2021	PODS
7	5,041	Enumeration of First-Order Queries on Classes of Structures With Bounded Expansion	2013	PODS
8	8,937	Dynamic Indexability and Lower Bounds for Dynamic One-Dimensional Range Query Indexes	2009	PODS
9	5,579	Enumeration on Trees with Tractable Combined Complexity and Efficient Updates	2019	PODS
10	8,909	Enumeration for MSO-Queries on Compressed Trees	2024	PODS