Ranked Enumeration for MSO on Trees via ...
Document type :
Pré-publication ou Document de travail
DOI :
Title :
Ranked Enumeration for MSO on Trees via Knowledge Compilation
Author(s) :
Amarilli, Antoine [Auteur]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Bourhis, Pierre [Auteur]
Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Self-adaptation for distributed services and large software systems [SPIRALS]
Capelli, Florent [Auteur]
Centre de Recherche en Informatique de Lens [CRIL]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Département Informatique et Réseaux [INFRES]
Data, Intelligence and Graphs [DIG]
Bourhis, Pierre [Auteur]

Centre de Recherche en Informatique, Signal et Automatique de Lille - UMR 9189 [CRIStAL]
Self-adaptation for distributed services and large software systems [SPIRALS]
Capelli, Florent [Auteur]

Centre de Recherche en Informatique de Lens [CRIL]
Monet, Mikaël [Auteur]
Linking Dynamic Data [LINKS]
Publication date :
2023-10-01
English keyword(s) :
knowledge compilation
monadic second-order logic
2012 ACM Subject Classification Information systems → Relational database model phrases Enumeration knowledge compilation monadic second-order logic Digital Object Identifier 10.4230/LIPIcs
2012 ACM Subject Classification Information systems → Relational database model phrases Enumeration
monadic second-order logic
2012 ACM Subject Classification Information systems → Relational database model phrases Enumeration knowledge compilation monadic second-order logic Digital Object Identifier 10.4230/LIPIcs
2012 ACM Subject Classification Information systems → Relational database model phrases Enumeration
HAL domain(s) :
Informatique [cs]
English abstract : [en]
We study the problem of enumerating the satisfying assignments for circuit classes from knowledge compilation, where assignments are ranked in a specific order. In particular, we show how this problem can be used to ...
Show more >We study the problem of enumerating the satisfying assignments for circuit classes from knowledge compilation, where assignments are ranked in a specific order. In particular, we show how this problem can be used to efficiently perform ranked enumeration of the answers to MSO queries over trees, with the order being given by a ranking function satisfying a subset-monotonicity property. Assuming that the number of variables is constant, we show that we can enumerate the satisfying assignments in ranked order for so-called multivalued circuits that are smooth, decomposable, and in negation normal form (smooth multivalued DNNF). There is no preprocessing and the enumeration delay is linear in the size of the circuit times the number of values, plus a logarithmic term in the number of assignments produced so far. If we further assume that the circuit is deterministic (smooth multivalued d-DNNF), we can achieve linear-time preprocessing in the circuit, and the delay only features the logarithmic term.Show less >
Show more >We study the problem of enumerating the satisfying assignments for circuit classes from knowledge compilation, where assignments are ranked in a specific order. In particular, we show how this problem can be used to efficiently perform ranked enumeration of the answers to MSO queries over trees, with the order being given by a ranking function satisfying a subset-monotonicity property. Assuming that the number of variables is constant, we show that we can enumerate the satisfying assignments in ranked order for so-called multivalued circuits that are smooth, decomposable, and in negation normal form (smooth multivalued DNNF). There is no preprocessing and the enumeration delay is linear in the size of the circuit times the number of values, plus a logarithmic term in the number of assignments produced so far. If we further assume that the circuit is deterministic (smooth multivalued d-DNNF), we can achieve linear-time preprocessing in the circuit, and the delay only features the logarithmic term.Show less >
Language :
Anglais
ANR Project :
Comment :
25 pages; submitted
Collections :
Source :
Files
- document
- Open access
- Access the document
- 2310.00731.pdf
- Open access
- Access the document
- 2310.00731
- Open access
- Access the document