License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2017.111
URN: urn:nbn:de:0030-drops-74626
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7462/
Go to the corresponding LIPIcs Volume Portal

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

A Circuit-Based Approach to Efficient Enumeration

pdf-format:
LIPIcs-ICALP-2017-111.pdf (0.5 MB)

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.

BibTeX - Entry

@InProceedings{amarilli_et_al:LIPIcs:2017:7462,
  author =	{Antoine Amarilli and Pierre Bourhis and Louis Jachiet and Stefan Mengel},
  title =	{{A Circuit-Based Approach to Efficient Enumeration}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{111:1--111:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Ioannis Chatzigiannakis and Piotr Indyk and Fabian Kuhn and Anca Muscholl},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7462},
  URN =		{urn:nbn:de:0030-drops-74626},
  doi =		{10.4230/LIPIcs.ICALP.2017.111},
  annote =	{Keywords: circuits, constant-delay, enumeration, d-DNNFs, MSO}
}

Keywords: circuits, constant-delay, enumeration, d-DNNFs, MSO
Collection: 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Issue Date: 2017
Date of publication: 07.07.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI