2026-08-17T17:39:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22967 2025-10-02T12:19:49Z ddc:004 open_access

Dynamic Direct Access of MSO Query Evaluation over Strings Bourhis, Pierre Capelli, Florent Mengel, Stefan Riveros, Cristian Query evaluation direct access MSO queries We study the problem of evaluating a Monadic Second Order (MSO) query over strings under updates in the setting of direct access. We present an algorithm that, given an MSO query with first-order free variables represented by an unambiguous variable-set automaton 𝒜 with state set Q and variables X and a string s, computes a data structure in time 𝒪(|Q|^ω⋅ |X|² ⋅ |s|) and, then, given an index i retrieves, using the data structure, the i-th output of the evaluation of 𝒜 over s in time 𝒪(|Q|^ω ⋅ |X|³ ⋅ log(|s|)²) where ω is the exponent for matrix multiplication. Ours is the first efficient direct access algorithm for MSO query evaluation over strings; such algorithms so far had only been studied for first-order queries and conjunctive queries over relational data. Our algorithm gives the answers in lexicographic order where, in contrast to the setting of conjunctive queries, the order between variables can be freely chosen by the user without degrading the runtime. Moreover, our data structure can be updated efficiently after changes to the input string, allowing more powerful updates than in the enumeration literature, e.g. efficient deletion of substrings, concatenation and splitting of strings, and cut-and-paste operations. Our approach combines a matrix representation of MSO queries and a novel data structure for dynamic word problems over semi-groups which yields an overall algorithm that is elegant and easy to formulate. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pierre Bourhis and Florent Capelli and Stefan Mengel and Cristian Riveros 2025 Is Part Of LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICDT.2025.26 urn:nbn:de:0030-drops-229675 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.26 eng https://creativecommons.org/licenses/by/4.0/legalcode