Ranked enumeration of MSO logic on words
Document type :
Communication dans un congrès avec actes
Title :
Ranked enumeration of MSO logic on words
Author(s) :
Bourhis, Pierre [Auteur]
Self-adaptation for distributed services and large software systems [SPIRALS]
Centre National de la Recherche Scientifique [CNRS]
Grez, Alejandro [Auteur]
Millennium Institute for Foundational Research on Data [IMFD]
Pontificia Universidad Católica de Chile [UC]
Jachiet, Louis [Auteur]
Institut Polytechnique de Paris [IP Paris]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Riveros, Cristian [Auteur]
Millennium Institute for Foundational Research on Data [IMFD]
Pontificia Universidad Católica de Chile [UC]

Self-adaptation for distributed services and large software systems [SPIRALS]
Centre National de la Recherche Scientifique [CNRS]
Grez, Alejandro [Auteur]
Millennium Institute for Foundational Research on Data [IMFD]
Pontificia Universidad Católica de Chile [UC]
Jachiet, Louis [Auteur]
Institut Polytechnique de Paris [IP Paris]
Data, Intelligence and Graphs [DIG]
Département Informatique et Réseaux [INFRES]
Riveros, Cristian [Auteur]
Millennium Institute for Foundational Research on Data [IMFD]
Pontificia Universidad Católica de Chile [UC]
Conference title :
24th International Conference on Database Theory, {ICDT} 2021, March 23-26, 2021, Nicosia, Cyprus
City :
Nicosia / Virtual
Country :
Chypre
Start date of the conference :
2021-03-23
Publisher :
Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik
HAL domain(s) :
Informatique [cs]
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Algorithme et structure de données [cs.DS]
Informatique [cs]/Base de données [cs.DB]
Informatique [cs]/Algorithme et structure de données [cs.DS]
English abstract : [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 ...
Show more >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.Show less >
Show more >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.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Comment :
29 pages (with appendix) presented at ICDT21 conference
Collections :
Source :
Files
- http://arxiv.org/pdf/2010.08042
- Open access
- Access the document
- 2010.08042
- Open access
- Access the document