Displaying similar documents to “Morphospace: Measurement, Modeling, Mathematics, and Meaning”

The triangles method to build -trees from incomplete distance matrices

Alain Guénoche, Bruno Leclerc (2010)

RAIRO - Operations Research

Similarity:

A method to infer -trees (valued trees having as set of leaves) from incomplete distance arrays (where some entries are uncertain or unknown) is described. It allows us to build an unrooted tree using only 2-3 distance values between the elements of , if they fulfill some explicit conditions. This construction is based on the mapping between -tree and a weighted generalized 2-tree spanning .

Tree inclusion problems

Patrick Cégielski, Irène Guessarian, Yuri Matiyasevich (2008)

RAIRO - Theoretical Informatics and Applications

Similarity:

Given two trees (a target and a pattern ) and a natural number , consist in deciding whether occurs as an embedded subtree of and/or finding the number of size (at most) windows of which contain pattern as an embedded subtree. is an embedded subtree of if can be obtained by deleting some nodes from (if a node is deleted, all edges adjacent to are also deleted, and outgoing edges are replaced by edges going from the parent of (if it exists) to the children of ). Deciding...

Dislocation measure of the fragmentation of a general Lévy tree

Guillaume Voisin (2011)

ESAIM: Probability and Statistics

Similarity:

Given a general critical or sub-critical branching mechanism and its associated Lévy continuum random tree, we consider a pruning procedure on this tree using a Poisson snake. It defines a fragmentation process on the tree. We compute the family of dislocation measures associated with this fragmentation. This work generalizes the work made for a Brownian tree [R. Abraham and L. Serlet, 7 (2002) 1–15] and for a tree without Brownian part [R. Abraham and J.-F. Delmas, 141 (2008) 113–154]. ...

On the Stack-Size of General Tries

Jérémie Bourdon, Markus Nebel, Brigitte Vallée (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

Digital trees or tries are a general purpose flexible data structure that implements dictionaries built on words. The present paper is focussed on the average-case analysis of an important parameter of this tree-structure, , the stack-size. The stack-size of a tree is the memory needed by a storage-optimal preorder traversal. The analysis is carried out under a general model in which words are produced by a source (in the information-theoretic sense) that emits symbols. Under...

Hopcroft's algorithm and tree-like automata

G. Castiglione, A. Restivo, M. Sciortino (2011)

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

Similarity:

Minimizing a deterministic finite automata (DFA) is a very important problem in theory of automata and formal languages. Hopcroft's algorithm represents the fastest known solution to the such a problem. In this paper we analyze the behavior of this algorithm on a family binary automata, called tree-like automata, associated to binary labeled trees constructed by words. We prove that all the executions of the algorithm on tree-like automata associated to trees, constructed by standard...