Titre :

Ranked enumeration of MSO logic on words

Auteur(s) :

Bourhis, Pierre [Auteur]
Centre National de la Recherche Scientifique [CNRS]
Self-adaptation for distributed services and large software systems [SPIRALS]
Grez, Alejandro [Auteur]
Pontificia Universidad Católica de Chile [UC]
Millennium Institute for Foundational Research on Data [IMFD]
Jachiet, Louis [Auteur]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Institut Polytechnique de Paris [IP Paris]
Riveros, Cristian [Auteur]
Pontificia Universidad Católica de Chile [UC]
Millennium Institute for Foundational Research on Data [IMFD]

Titre de la manifestation scientifique :

24th International Conference on Database Theory, {ICDT} 2021, March 23-26, 2021, Nicosia, Cyprus

Ville :

Nicosia / Virtual

Pays :

Chypre

Date de début de la manifestation scientifique :

2021-03-23

Éditeur :

Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik

Discipline(s) HAL :

Informatique [cs]
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Algorithme et structure de données [cs.DS]

Résumé en anglais : [en]

In the last years, enumeration algorithms with bounded delay have attracted a lot of attention for several data management tasks. Given a query and the data, the task is to preprocess the data and then enumerate all the ...
Lire la suite >In the last years, enumeration algorithms with bounded delay have attracted a lot of attention for several data management tasks. Given a query and the data, the task is to preprocess the data and then enumerate all the answers to the query one by one and without repetitions. This enumeration scheme is typically useful when the solutions are treated on the fly or when we want to stop the enumeration once the pertinent solutions have been found. However, with the current schemes, there is no restriction on the order how the solutions are given and this order usually depends on the techniques used and not on the relevance for the user. In this paper we study the enumeration of monadic second order logic (MSO) over words when the solutions are ranked. We present a framework based on MSO cost functions that allows to express MSO formulae on words with a cost associated with each solution. We then demonstrate the generality of our framework which subsumes, for instance, document spanners and regular complex event processing queries and adds ranking to them. The main technical result of the paper is an algorithm for enumerating all the solutions of formulae in increasing order of cost efficiently, namely, with a linear preprocessing phase and logarithmic delay between solutions. The novelty of this algorithm is based on using functional data structures, in particular, by extending functional Brodal queues to suit with the ranked enumeration of MSO on words.Lire moins >

Langue :

Anglais

Comité de lecture :

Oui

Audience :

Internationale

Vulgarisation :

Non

Commentaire :

29 pages (with appendix) presented at ICDT21 conference

Collections :

• Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189

Source :

Harvested from HAL