✦ LIBER ✦

Recursive reconstruction on periodic trees

✍ Scribed by Elchanan Mossel

Publisher: John Wiley and Sons
Year: 1998
Tongue: English
Weight: 216 KB
Volume: 13
Category: Article
ISSN: 1042-9832
DOI: 10.1002/(sici)1098-2418(199808)13:1<81::aid-rsa5>3.0.co;2-o

No coin nor oath required. For personal study only.

✦ Synopsis

A periodic tree T consists of full n-level copies of a finite tree T. The tree T n n is labeled by random bits. The root label is chosen randomly, and the probability of two adjacent vertices to have the same label is 1 y ⑀. This model simulates noisy propagation of a bit from the root, and has significance both in communication theory and in biology. Our aim is to find an algorithm which decides for every set of values of the boundary bits of T, if the root is more probable to be 0 or 1. We want to use this algorithm recursively to 1 reconstruct the value of the root of T with a probability bounded away from for all n. In n 2 this paper we find for all T, the values of ⑀ for which such a reconstruction is possible. We then compare the ⑀ values for recursive and nonrecursive algorithms. Finally, we discuss some problems concerning generalizations of this model.

📜 SIMILAR VOLUMES

Recursion on Homogeneous Trees

✍ Herman Ruge Jervell 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 201 KB

On Reconstructing Rooted Trees

✍ T. Andreae 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 667 KB

A probably very difficult question of Nash-Williams asks whether any two hypomorphic trees are isomorphic. In the present paper, we consider rooted trees rather than trees and give an affirmative answer to the corresponding version of Nash-Williams' question, i.e., we show that any two hypomorphic r

On the reconstruction of locally finite

On the reconstruction of locally finite trees

✍ Thomas Andreae 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 676 KB

## Abstract We prove a theorem saying, when taken together with previous results of Bondy, Hemminger, and Thomassen, that every locally finite, infinite tree not containing a subdivision of the dyadic tree (i. e., the regular tree of degree 3) is uniquely determined, up to isomorphism, from its col

Annual precipitation reconstruction sinc

Annual precipitation reconstruction since AD 775 based on tree rings from the Qilian Mountains, northwestern China

✍ Yong Zhang; Qinhua Tian; Xiaohua Gou; Fahu Chen; Steven W. Leavitt; Yousheng Wan 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 899 KB

## Abstract A millennium‐long tree‐ring‐width chronology from the middle Qilian Mountains in northwestern China has been used to reconstruct annual precipitation variation (from the prior August to current July) since AD 775. The reconstruction explains 37.8% of variance of the observed data. Based

Influence of regulated deficit irrigatio

Influence of regulated deficit irrigation strategies applied to olive trees (Arbequina cultivar) on oil yield and oil composition during the fruit ripening period

✍ M José Motilva; M Jesús Tovar; M Paz Romero; Simón Alegre; Joan Girona 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 101 KB 👁 2 views

This study evaluated the effect of regulated de®cit irrigation (RDI) strategies applied to olive trees (Arbequina cv) during the fruit ripening and harvest periods on oil yield and oil composition. Fatty acid composition, pigments, colour, polyphenol content and stability of oils were evaluated. The