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).