Metraipolis › archive › dc_8dc77c5ddcd5

Restructuring Tree Decision Diagrams — arXiv:2609.21842

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.21842
License (as archived)
CC0-1.0
Archived
2026-10-10T02:51:55.148Z
SHA-256 of the archived text
0d9369fd52717a42783a019763ea8e9c39d11657f815d46c2e809bc3603bc151
Stable URL of this page
https://metraipolis.com/documento/dc_8dc77c5ddcd5

How to cite

Restructuring Tree Decision Diagrams — arXiv:2609.21842 — arXiv (en), https://arxiv.org/abs/2609.21842 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8dc77c5ddcd5 (Metraipolis archive dc_8dc77c5ddcd5, sha256 0d9369fd52717a42783a019763ea8e9c39d11657f815d46c2e809bc3603bc151)
BibTeX
@misc{dc8dc77c5ddcd5,
  title = {Restructuring Tree Decision Diagrams — arXiv:2609.21842},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.21842},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8dc77c5ddcd5; sha256 0d9369fd52717a42783a019763ea8e9c39d11657f815d46c2e809bc3603bc151},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.21842. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Tree Decision Diagrams (TDDs) are a data structure recently introduced by Capelli et al. (SAT 2026). They are structured along a vtree and the size of their canonical form lies between Ordered Binary Decision Diagrams (OBDDs) and deterministic structured DNNF circuits (d-SDNNFs). While the succinctness gap between TDD and d-SDNNF is exponential, only a quasipolynomial separation between OBDD and TDD has been shown and it was left as open question whether this is optimal. We answer this question affirmatively by showing that every TDD can be transformed to an equivalent OBDD of quasipolynomial size. Although this might be seen as a weakness, our second result shows that TDDs share another desirable property with OBDDs that is not known to hold for d-SDNNF: Given a TDD and another target vtree, it is possible to construct the minimal and canonical TDD respecting the new vtree in time polynomial in the input and output. As a result we also obtain that the equivalence test between TDDs over different vtrees can be done in polynomial time.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-21 in cs.CC).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.21842 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T02:30:12.544Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-21?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).