• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Dualities in Tree Representations
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Pré-publication ou Document de travail
Title :
Dualities in Tree Representations
Author(s) :
Chikhi, Rayan [Auteur] refId
Bioinformatics and Sequence Analysis [BONSAI]
Schönhuth, Alexander [Auteur]
Equipe de recherche européenne en algorithmique et biologie formelle et expérimentale [ERABLE]
Life Sciences [Amsterdam] [MAC4]
English keyword(s) :
Succinct Tree Representation
Balanced Parenthesis Representation
Isomorphisms
Data Structures
HAL domain(s) :
Informatique [cs]/Bio-informatique [q-bio.QM]
Informatique [cs]/Mathématique discrète [cs.DM]
English abstract : [en]
A characterization of the tree $T^*$ such that $\mathrm{BP}(T^*)=\overleftrightarrow{\mathrm{DFUDS}(T)}$, the reversal of $\mathrm{DFUDS}(T)$ is given. An immediate consequence is a rigorous characterization of the tree ...
Show more >
A characterization of the tree $T^*$ such that $\mathrm{BP}(T^*)=\overleftrightarrow{\mathrm{DFUDS}(T)}$, the reversal of $\mathrm{DFUDS}(T)$ is given. An immediate consequence is a rigorous characterization of the tree $\hat{T}$ such that $\mathrm{BP}(\hat{T})=\mathrm{DFUDS}(T)$. In summary, $\mathrm{BP}$ and $\mathrm{DFUDS}$ are unified within an encompassing framework, which might have the potential to imply future simplifications with regard to queries in $\mathrm{BP}$ and/or $\mathrm{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.Show less >
Language :
Anglais
Comment :
CPM 2018, extended version
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • http://arxiv.org/pdf/1804.04263
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017