Displaying similar documents to “The triangles method to build X-trees from incomplete distance matrices”

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah (2012)

ESAIM: Probability and Statistics

Similarity:

We prove for simple hierarchical structures (modelled as ) and networked structures (modelled as ). For example, for large , a networked data structure consisting of units connected by an average number of links of order   log  can be coded by about  ×  bits, where is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.

Asymptotic equipartition properties for simple hierarchical and networked structures

Kwabena Doku-Amponsah (2012)

ESAIM: Probability and Statistics

Similarity:

We prove for simple hierarchical structures (modelled as ) and networked structures (modelled as ). For example, for large , a networked data structure consisting of units connected by an average number of links of order   log  can be coded by about  ×  bits, where is an explicitly defined entropy. The main technique in our proofs are large deviation principles for suitably defined empirical measures.

A Note on Negative Tagging for Least Fixed-Point Formulae

Dilian Gurov, Bruce Kapron (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Proof systems with sequents of the form ⊢ Φ for proving validity of a propositional modal -calculus formula Φ over a set of states in a given model usually handle fixed-point formulae through unfolding, thus allowing such formulae to reappear in a proof. Tagging is a technique originated by Winskel for annotating fixed-point formulae with information about the proof states at which these are unfolded. This information is used later in the proof to avoid unnecessary unfolding,...

New applications of the wreath product of forest algebras

Howard Straubing (2013)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

We give several new applications of the wreath product of forest algebras to the study of logics on trees. These include new simplified proofs of necessary conditions for definability in and first-order logic with the ancestor relation; a sequence of identities satisfied by all forest languages definable in ; and new examples of languages outside along with an application to the question of what properties are definable in both and

Repetition thresholds for subdivided graphs and trees

Pascal Ochem, Elise Vaslet (2012)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

The introduced by Dejean and Brandenburg is the smallest real number such that there exists an infinite word over a -letter alphabet that avoids -powers for all   . We extend this notion to colored graphs and obtain the value of the repetition thresholds of trees and “large enough” subdivisions of graphs for every alphabet size.