✦ LIBER ✦

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

✍ Scribed by Joost Engelfriet; Heiko Vogler

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 979 KB
Volume: 56
Category: Article
ISSN: 0022-0000
DOI: 10.1006/jcss.1998.1573

No coin nor oath required. For personal study only.

✦ Synopsis

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 transducer is a jungle, i.e., a hypergraph that can be unfolded into a tree, then the tree-to-graph transducer is said to be tree-generating and naturally defines a tree-to-tree translation. We prove that bottom-up tree-to-graph transducers define the same treeto-tree translations as the previously introduced top-down tree-to-graph transducers. This is in contrast with the well-known incomparability of the usual bottom-up and top-down tree transducers.

📜 SIMILAR VOLUMES

Equivalence of two healthcare costing me

Equivalence of two healthcare costing methods: bottom-up and top-down

✍ Michael K. Chapko; Chuan-Fen Liu; Mark Perkins; Yu-Fang Li; John C. Fortney; Mat 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 230 KB

This paper compares two quite different approaches to estimating costs: a 'bottom-up' approach, represented by the US Department of Veterans Affairs' (VA) Decision Support System that uses local costs of specific inputs; and a 'top-down' approach, represented by the costing system created by the VA

Merging bottom-up and top-down approache

Merging bottom-up and top-down approaches to study prostate cancer biology

✍ The Prostate Cancer Complexity Working Group 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 295 KB

## Abstract The sequencing of the human genome has opened new areas of possibility for understanding diseases such as cancers. Sequencing has given us the necessary building blocks for identifying the components of important signaling networks, whereas new tools such as automated gene sequencing, c

A Combined Top–Down/Bottom–Up Approach t

A Combined Top–Down/Bottom–Up Approach to the Microscopic Localization of Metallic Nanodots

✍ J.P. Spatz; V.Z.-H. Chan; S. Mößmer; F.-M. Kamm; A. Plettl; P. Ziemann; M. Mölle 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB 👁 1 views

A Combined Top-Down/Bottom-Up Approach f

A Combined Top-Down/Bottom-Up Approach for the Nanoscale Patterning of Spin-Crossover Coordination Polymers

✍ G. Molnár; S. Cobo; J. A. Real; F. Carcenac; E. Daran; C. Vieu; A. Bousseksou 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 401 KB 👁 1 views

Biomineralization Nanolithography: Combi

Biomineralization Nanolithography: Combination of Bottom-Up and Top-Down Fabrication To Grow Arrays of Monodisperse Gold Nanoparticles Along Peptide Lines

✍ Nurxat Nuraje; Samia Mohammed; Linglu Yang; Hiroshi Matsui 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 350 KB

Biomineralization Nanolithography: Combi

Biomineralization Nanolithography: Combination of Bottom-Up and Top-Down Fabrication To Grow Arrays of Monodisperse Gold Nanoparticles Along Peptide Lines

✍ Nurxat Nuraje; Samia Mohammed; Linglu Yang; Hiroshi Matsui 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 350 KB

## Abstract **From top to bottom**: Peptide lines were formed in trenches in the self‐assembled monolayer (SAM) on an Au substrate. Combination of the top‐down (peptide nanolithography) and the bottom‐up fabrications (biomineralization) yielded arrays of monodisperse Au nanoparticles assembled on t