On Bounded Exploration and Bounded Nondeterminism - Yuri Gurevich; Tatiana Yavorskaya (Microsoft Research, 2006)
This report consists of two separate parts, essentially two oversized footnotes to the article "Sequential Abstract State Machines Capture Sequential Algorithms" by Yuri Gurevich. In Chapter I, Yuri Gurevich and Tatiana Yavorskaya present and study a more abstract version of the bounded exploration postulate. In Chapter II, Tatiana Yavorskaya gives a complete form of the characterization, sketched in the original paper, of bounded-choice sequential algorithms. – – , "Sequential Abstract State Machines Capture Sequential Algorithms" . I, . II, , .
Keywords: 330; Bounded Nondeterminism; Bounded Exploration