We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Eigen Distribution of an AND-OR Tree under Directional Algorithms.
- Authors
Suzuki, Toshio; Nakamura, Ryota
- Abstract
Consider a probability distribution d on the truth assignments to a perfect binary AND-OR tree. Liu and Tanaka (2007) extends the work of Saks and Wigderson (1986), and they characterize the eigen-distribution, the distribution achieving the equilibrium, as the uniform distribution on the 1-set (the set of all reluctant assignments for which the root has the value 1). We show that the uniqueness of the eigen-distribution fails provided that we restrict ourselves to directional algorithms. An alpha-beta pruning algorithm is said to be directional (Pearl, 1980) if for some linear ordering of the leaves (Boolean variables) it never selects for examination a leaf situated to the left of a previously examined leaf. We also show that the following weak version of the Liu-Tanaka result holds for the situation where only directional algorithms are considered; a distribution is eigen if and only if it is a distribution on the 1-set such that the cost does not depend on an associated deterministic algorithm.
- Subjects
ALGORITHMS; PROBABILITY theory; DATA structures; LINEAR orderings; COMPUTATIONAL complexity; DISTRIBUTION (Probability theory)
- Publication
IAENG International Journal of Applied Mathematics, 2012, Vol 42, Issue 2, p122
- ISSN
1992-9978
- Publication type
Article