DROPS

Document

DOI: 10.4230/LIPIcs.SAT.2026.10

A Canonical Generalization of OBDD

Authors: Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, and Guy Van den Broeck

Published in: LIPIcs, Volume 377, 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)

Abstract

We introduce Tree Decision Diagrams (TDD) as a model for Boolean functions that generalizes OBDD. They can be seen as a restriction of structured d-DNNF; that is, d-DNNF that respect a vtree T. We show that TDDs enjoy the same tractability properties as OBDD, such as model counting, enumeration, conditioning, and apply, and are more succinct. In particular, we show that CNF formulas of treewidth k can be represented by TDDs of FPT size, which is known to be impossible for OBDD. We study the complexity of compiling CNF formulas into deterministic TDDs via bottom-up compilation and relate the complexity of this approach with the notion of factor width introduced by Bova and Szeider.

Cite as

Florent Capelli, YooJung Choi, Stefan Mengel, Martín Muñoz, and Guy Van den Broeck. A Canonical Generalization of OBDD. In 29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 377, pp. 10:1-10:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{capelli_et_al:LIPIcs.SAT.2026.10,
  author =	{Capelli, Florent and Choi, YooJung and Mengel, Stefan and Mu\~{n}oz, Mart{\'\i}n and Van den Broeck, Guy},
  title =	{{A Canonical Generalization of OBDD}},
  booktitle =	{29th International Conference on Theory and Applications of Satisfiability Testing (SAT 2026)},
  pages =	{10:1--10:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-431-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{377},
  editor =	{Ignatiev, Alexey and Szeider, Stefan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAT.2026.10},
  URN =		{urn:nbn:de:0030-drops-263167},
  doi =		{10.4230/LIPIcs.SAT.2026.10},
  annote =	{Keywords: Boolean functions, Model counting, Knowledge Compilation}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2023.7

Constant-Delay Enumeration for SLP-Compressed Documents

Authors: Martín Muñoz and Cristian Riveros

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract

We study the problem of enumerating results from a query over a compressed document. The model we use for compression are straight-line programs (SLPs), which are defined by a context-free grammar that produces a single string. For our queries we use a model called Annotated Automata, an extension of regular automata that allows annotations on letters. This model extends the notion of Regular Spanners as it allows arbitrarily long outputs. Our main result is an algorithm which evaluates such a query by enumerating all results with output-linear delay after a preprocessing phase which takes linear time on the size of the SLP, and cubic time over the size of the automaton. This is an improvement over Schmid and Schweikardt’s result [Markus L. Schmid and Nicole Schweikardt, 2021], which, with the same preprocessing time, enumerates with a delay which is logarithmic on the size of the uncompressed document. We achieve this through a persistent data structure named Enumerable Compact Sets with Shifts which guarantees output-linear delay under certain restrictions. These results imply constant-delay enumeration algorithms in the context of regular spanners. Further, we use an extension of annotated automata which utilizes succinctly encoded annotations to save an exponential factor from previous results that dealt with constant-delay enumeration over vset automata. Lastly, we extend our results in the same fashion Schmid and Schweikardt did [Markus L. Schmid and Nicole Schweikardt, 2022] to allow complex document editing while maintaining the constant-delay guarantee.

Cite as

Martín Muñoz and Cristian Riveros. Constant-Delay Enumeration for SLP-Compressed Documents. In 26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{munoz_et_al:LIPIcs.ICDT.2023.7,
  author =	{Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
  title =	{{Constant-Delay Enumeration for SLP-Compressed Documents}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{7:1--7:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.7},
  URN =		{urn:nbn:de:0030-drops-177495},
  doi =		{10.4230/LIPIcs.ICDT.2023.7},
  annote =	{Keywords: SLP compression, query evaluation, enumeration algorithms}
}

Document

DOI: 10.4230/LIPIcs.ICDT.2022.19

Streaming Enumeration on Nested Documents

Authors: Martín Muñoz and Cristian Riveros

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract

Some of the most relevant document schemas used online, such as XML and JSON, have a nested format. In the last decade, the task of extracting data from nested documents over streams has become especially relevant. We focus on the streaming evaluation of queries with outputs of varied sizes over nested documents. We model queries of this kind as Visibly Pushdown Transducers (VPT), a computational model that extends visibly pushdown automata with outputs and has the same expressive power as MSO over nested documents. Since processing a document through a VPT can generate a massive number of results, we are interested in reading the input in a streaming fashion and enumerating the outputs one after another as efficiently as possible, namely, with constant-delay. This paper presents an algorithm that enumerates these elements with constant-delay after processing the document stream in a single pass. Furthermore, we show that this algorithm is worst-case optimal in terms of update-time per symbol and memory usage.

Cite as

Martín Muñoz and Cristian Riveros. Streaming Enumeration on Nested Documents. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 19:1-19:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{munoz_et_al:LIPIcs.ICDT.2022.19,
  author =	{Mu\~{n}oz, Mart{\'\i}n and Riveros, Cristian},
  title =	{{Streaming Enumeration on Nested Documents}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{19:1--19:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.19},
  URN =		{urn:nbn:de:0030-drops-158935},
  doi =		{10.4230/LIPIcs.ICDT.2022.19},
  annote =	{Keywords: Streaming, nested documents, query evaluation, enumeration algorithms}
}

Search Results

Documents authored by Muñoz, Martín

A Canonical Generalization of OBDD

Abstract

Cite as

Constant-Delay Enumeration for SLP-Compressed Documents

Abstract

Cite as

Streaming Enumeration on Nested Documents

Abstract

Cite as

Thanks for your feedback!

Could not send message