2026-07-21T11:55:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8690 2024-03-06T10:43:02Z ddc:004 open_access

Dualities in Tree Representations Chikhi, Rayan Schönhuth, Alexander Data Structures Succinct Tree Representation Balanced Parenthesis Representation Isomorphisms A characterization of the tree T^* such that BP(T^*)=ova{DFUDS(T)}, the reversal of DFUDS(T) is given. An immediate consequence is a rigorous characterization of the tree T^ such that BP(T^)=DFUDS(T). In summary, BP and DFUDS are unified within an encompassing framework, which might have the potential to imply future simplifications with regard to queries in BP and/or DFUDS. Immediate benefits displayed here are to identify so far unnoted commonalities in most recent work on the Range Minimum Query problem, and to provide improvements for the Minimum Length Interval Query problem. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Rayan Chikhi and Alexander Schönhuth 2018 Is Part Of LIPIcs, Volume 105, 29th Annual Symposium on Combinatorial Pattern Matching (CPM 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2018.18 urn:nbn:de:0030-drops-86901 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2018.18 eng https://creativecommons.org/licenses/by/3.0/legalcode