Document Open Access Logo

A Circuit-Based Approach to Efficient Enumeration

Authors Antoine Amarilli, Pierre Bourhis, Louis Jachiet, Stefan Mengel

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.111.pdf
  • Filesize: 497 kB
  • 15 pages

Document Identifiers

Author Details

Antoine Amarilli
Pierre Bourhis
Louis Jachiet
Stefan Mengel

Cite AsGet BibTex

Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A Circuit-Based Approach to Efficient Enumeration. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 111:1-111:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.ICALP.2017.111

Abstract

We study the problem of enumerating the satisfying valuations of a circuit while bounding the delay, i.e., the time needed to compute each successive valuation. We focus on the class of structured d-DNNF circuits originally introduced in knowledge compilation, a sub-area of artificial intelligence. We propose an algorithm for these circuits that enumerates valuations with linear preprocessing and delay linear in the Hamming weight of each valuation. Moreover, valuations of constant Hamming weight can be enumerated with linear preprocessing and constant delay. Our results yield a framework for efficient enumeration that applies to all problems whose solutions can be compiled to structured d-DNNFs. In particular, we use it to recapture classical results in database theory, for factorized database representations and for MSO evaluation. This gives an independent proof of constant-delay enumeration for MSO formulae with first-order free variables on bounded-treewidth structures.
Keywords
  • circuits
  • constant-delay
  • enumeration
  • d-DNNFs
  • MSO

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Serge Abiteboul, Richard Hull, and Victor Vianu. Foundations of databases. Addison-Wesley, 1995. URL: http://webdam.inria.fr/Alice/pdfs/all.pdf.
  2. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman. The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974. Google Scholar
  3. Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A circuit-based approach to efficient enumeration, 2017. URL: https://arxiv.org/abs/1702.05589, URL: http://arxiv.org/abs/1702.05589.
  4. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Provenance circuits for trees and treelike instances. In ICALP, 2015. URL: https://arxiv.org/abs/1511.08723.
  5. Antoine Amarilli, Pierre Bourhis, and Pierre Senellart. Tractable lineages on treelike instances: Limits and extensions. In PODS, 2016. URL: https://arxiv.org/abs/1604.02761.
  6. Guillaume Bagan. MSO queries on tree decomposable structures are computable with linear delay. In CSL, 2006. Google Scholar
  7. Guillaume Bagan, Arnaud Durand, Emmanuel Filiot, and Olivier Gauwin. Efficient enumeration for conjunctive queries over X-underbar structures. In CSL, 2010. URL: https://hal.inria.fr/hal-00489955.
  8. Guillaume Bagan, Arnaud Durand, and Etienne Grandjean. On acyclic conjunctive queries and constant delay enumeration. In CSL, 2007. URL: http://www.logique.jussieu.fr/~durand/webperso/papers/BDGlongversion.pdf.
  9. Guillaume Bagan, Arnaud Durand, Etienne Grandjean, and Frédéric Olive. Computing the jth solution of a first-order query. ITA, 42(1), 2008. URL: https://hal-univ-diderot.archives-ouvertes.fr/file/index/docid/221730/filename/bdgo.pdf.
  10. Nurzhan Bakibayev, Tomáš Kočiskỳ, Dan Olteanu, and Jakub Závodnỳ. Aggregation and ordering in factorised databases. PVLDB, 2013. URL: https://www.cs.ox.ac.uk/dan.olteanu/papers/bkoz-vldb13-with-response.pdf.
  11. David A. Mix Barrington, Neil Immerman, and Howard Straubing. On uniformity within NC¹. JCSS, 41(3), 1990. URL: http://www.sciencedirect.com/science/article/pii/002200009090022D.
  12. Simone Bova, Florent Capelli, Stefan Mengel, and Friedrich Slivovsky. On compiling CNFs into structured deterministic DNNFs. In SAT, 2015. URL: http://www.dcs.bbk.ac.uk/~florent/publi/cnf-to-ddnnf-upper-bound.pdf.
  13. Simone Bova and Stefan Szeider. Circuit treewidth, sentential decision, and query compilation. In PODS, 2017. URL: https://arxiv.org/abs/1701.04626.
  14. Arthur Choi and Adnan Darwiche. Dynamic minimization of sentential decision diagrams. In AAAI, 2013. URL: http://reasoning.cs.ucla.edu/fetch.php?id=128&type=pdf.
  15. Thomas Colcombet. A combinatorial theorem for trees. In ICALP, 2007. URL: https://www.irif.fr/~colcombe/Publications/ICALP07-colcombet.pdf.
  16. Bruno Courcelle. Linear delay enumeration and monadic second-order logic. Discrete Applied Mathematics, 157(12), 2009. URL: https://www.labri.fr/perso/courcell/Textes/LinDelayEnum.pdf.
  17. Adnan Darwiche. On the tractable counting of theory models and its application to truth maintenance and belief revision. J. Applied Non-Classical Logics, 11(1-2), 2001. URL: http://dx.doi.org/10.3166/jancl.11.11-34.
  18. Adnan Darwiche and Pierre Marquis. A knowledge compilation map. JAIR, 17, 2002. URL: https://www.jair.org/media/989/live-989-2063-jair.pdf.
  19. Arnaud Durand and Etienne Grandjean. First-order queries on structures of bounded degree are computable with constant delay. TOCL, 8(4), 2007. URL: https://arxiv.org/abs/cs/0507020.
  20. Arnaud Durand, Nicole Schweikardt, and Luc Segoufin. Enumerating answers to first-order queries over databases of low degree. In PODS, 2014. URL: https://hal.inria.fr/hal-01070898/en.
  21. Jinbo Huang and Adnan Darwiche. DPLL with a trace: From SAT to knowledge compilation. In IJCAI, 2005. URL: https://ijcai.org/Proceedings/05/Papers/0876.pdf.
  22. Abhay Kumar Jha and Dan Suciu. Knowledge compilation meets database theory: Compiling queries to decision diagrams. TCS, 52(3), 2013. Google Scholar
  23. Wojciech Kazana. Query evaluation with constant delay. PhD thesis, École normale supérieure de Cachan, 2013. URL: https://tel.archives-ouvertes.fr/tel-00919786/document.
  24. Wojciech Kazana and Luc Segoufin. Enumeration of first-order queries on classes of structures with bounded expansion. In PODS. ACM, 2013. URL: https://hal.inria.fr/hal-00908779/en.
  25. Wojciech Kazana and Luc Segoufin. Enumeration of monadic second-order queries on trees. TOCL, 14(4), 2013. URL: https://hal.archives-ouvertes.fr/docs/00/90/70/85/PDF/cdlin-survey.pdf.
  26. Donald E. Knuth. The Art of Computer Programming. Volume 4A: Combinatorial Algorithms, Part 1. Addison-Wesley, 2005. Google Scholar
  27. Leonid Libkin. Elements of Finite Model Theory. Springer, 2004. Google Scholar
  28. Katja Losemann and Wim Martens. MSO queries on trees: enumerating answers under updates. In CSL-LICS, 2014. URL: http://www.theoinf.uni-bayreuth.de/download/lics14-preprint.pdf.
  29. Dan Olteanu and Jakub Závodnỳ. Size bounds for factorised representations of query results. TODS, 40(1), 2015. URL: http://www.cs.ox.ac.uk/dan.olteanu/papers/oz-tods15.pdf.
  30. Umut Oztok and Adnan Darwiche. A top-down compiler for sentential decision diagrams. In IJCAI, 2015. URL: http://reasoning.cs.ucla.edu/fetch.php?id=157&type=pdf.
  31. Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based on structured decomposability. In AAAI, 2008. URL: http://aaai.org/Papers/AAAI/2008/AAAI08-082.pdf.
  32. Ran Raz, Amir Shpilka, and Amir Yehudayoff. A lower bound for the size of syntactically multilinear arithmetic circuits. SIAM J. Comput., 38(4), 2008. URL: http://dx.doi.org/10.1137/070707932.
  33. Luc Segoufin. A glimpse on constant delay enumeration (invited talk). In STACS, 2014. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2014.13.
  34. Volker Strassen. Vermeidung von divisionen. Journal für die reine und angewandte Mathematik, 264, 1973. URL: https://eudml.org/doc/151394.
  35. James W. Thatcher and Jesse B. Wright. Generalized finite automata theory with an application to a decision problem of second-order logic. Math. Systems Theory, 2(1), 1968. Google Scholar
  36. Kunihiro Wasa. Enumeration of enumeration algorithms. CoRR, abs/1605.05102, 2016. URL: https://arxiv.org/abs/1605.05102.
  37. Ingo Wegener. Branching programs and binary decision diagrams. SIAM, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact