|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'501'711
Articles rated: 2609
20 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Non-Depth-First Search against Independent Distributions on an AND-OR Tree | | Toshio Suzuki
; | | Date: |
21 Sep 2017 | | Abstract: | Suzuki and Niida (Ann. Pure. Appl. Logic, 2015) showed the following results
on independent distributions (IDs) on an AND-OR tree, where they took only
depth-first algorithms into consideration. (1) Among IDs such that probability
of the root having value 0 is fixed as a given r such that 0 < r < 1, if d is a
maximizer of cost of the best algorithm then d is an independent and identical
distribution (IID). (2) Among all IDs, if d is a maximizer of cost of the best
algorithm then d is an IID. In the case where non-depth-first algorithms are
taken into consideration, the counter parts of (1) and (2) are left open in the
above work. Peng et al. (Inform. Process. Lett., 2017) extended (1) and (2) to
multi-branching trees, where in (2) they put an additional hypothesis on IDs
that probability of the root having value 0 is neither 0 nor 1. We give
positive answers for the two questions of Suzuki-Niida. A key to the proof is
that if ID d achieves the equilibrium among IDs then we can chose an algorithm
of the best cost against d from depth-first algorithms. In addition, we extend
the result of Peng et al. to the case where non-depth-first algorithms are
taken into consideration. | | Source: | arXiv, 1709.7358 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER