  Models of a generalized nondeterminism are defined by limitations on nonde-
terministic behavior of a computing device. A regular realizability problem is
a problem of verifying existence of a special sort word in a regular language.
These notions are closely connected. In this paper we consider regular
realizability problems for languages consist- ing of all prefixes of an
infinite word. These problems are related to the automata on infinite words and
to the decidability of monadic second-order theories. The main contribution is
a new decidability condition for regular realizability problems and for
monadic-second order theories. We also show that decidability of a regular
realizability problem is equivalent to decidability of some prefix
realizability problem.
