2011/05/30 by Alexander A. Rubtsov, A. Rubtsov, Rubtsov, A. +2 · 1 citation
Computer Science · #Computability, Logic, AI Algorithms #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL) #Rough Sets and Fuzzy Logic #cs.DM #cs.FL #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1105.5894
13 pages
arxiv created 2011/05/30 · openalex publication_date 2011/05/30 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.