✦ LIBER ✦

The suffix tree of a tree and minimizing sequential transducers

✍ Scribed by Dany Breslauer

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 1013 KB
Volume: 191
Category: Article
ISSN: 0304-3975
DOI: 10.1016/s0304-3975(96)00319-2

No coin nor oath required. For personal study only.

✦ Synopsis

This paper gives a linear-time algorithm for the construction of the suffix tree of a tree, which was introduced by Kosaraju, as a natural generalization of the suffix tree of a string. The suffix tree of a tree is used to obtain an efficient algorithm for the minimization of sequential transducers.

📜 SIMILAR VOLUMES

The Equivalence of Bottom-Up and Top-Dow

The Equivalence of Bottom-Up and Top-Down Tree-to-Graph Transducers

✍ Joost Engelfriet; Heiko Vogler 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 979 KB

We introduce the bottom-up tree-to-graph transducer, which is very similar to the usual (total deterministic) bottom-up tree transducer except that it translates trees into hypergraphs rather than trees, using hypergraph substitution instead of tree substitution. If every output hypergraph of the tr

Ordering of the trees with a perfect mat

Ordering of the trees with a perfect matching by minimal energies

✍ Wen-Huan Wang; Li-Ying Kang 📂 Article 📅 2009 🏛 Elsevier Science 🌐 English ⚖ 276 KB

Minimal spanning trees with a constraint

Minimal spanning trees with a constraint on the number of leaves

✍ Lucinda Matos Fernandes; Luis Gouveia 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 845 KB

Tail bound for the minimal spanning tree

Tail bound for the minimal spanning tree of a complete graph

✍ Jeong Han Kim; Sungchul Lee 📂 Article 📅 2003 🏛 Elsevier Science 🌐 English ⚖ 202 KB

Suppose each edge of the complete graph K n is assigned a random weight chosen independently and uniformly from the unit interval [0; 1]. A minimal spanning tree is a spanning tree of K n with the minimum weight. It is easy to show that such a tree is unique almost surely. This paper concerns the nu

The optimal location of a path or tree i

The optimal location of a path or tree in a tree network

✍ Edward Minieka 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 610 KB

This article describes methods for finding an optimal location for a path-shaped or tree-shaped facility of a specified size in a tree network. Four optimization criteria are examined: minimizing distancesum, minimizing eccentricity, maximizing distancesum, and maximizing eccentricity.

The subtree center of a tree

✍ Nieminen, Juhani; Peltola, Matti 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 107 KB 👁 2 views

A method to determine the least central subtree of a tree is given. The structure of the trees having a single point as a least central subtree is described, and the relation of a least central subtree of a tree to the centroid as well as to the center of that tree is given.