Transactions of the American Mathematical Society · 1969 · 272 citations · 10 references
ComputingComputer ScienceMathematicsAlgorithmsGame TheoryTheory Of ComputationAutomata TheoryFinite AutomataFinite-state MachinesConditionsFinite Automata TheoryFinite-state ProcessesSequential ConditionsSequential GamesWinning Strategies
Our main purpose is to present an algorithm which decides whether or not a condition &(X, Y) stated in sequential calculus admits a finite automata solution, and produces one if it exists. This solves a problem stated in In an equally appealing form the result can be restated in the terminology of [7], [10], [15]: Every cu-game definable in sequential calculus is determined. Moreover the player who has a winning strategy, in fact, has a winning finite-state strategy, that is one which can effectively be played in a strong sense. The main proof, that of the central Theorem 1, will be presented at the end. We begin with a discussion of its consequences.
10
Finite Automata and Their Decision Problems
M. O. Rabin, D. Scott · IBM Journal of Research and Development · 1959 · 1.9K citations
Weak Second‐Order Arithmetic and Finite Automata
J Büchi · Mathematical logic quarterly · 1960 · 819 citations
Arithmetical predicates and function quantifiers
S. C. Kleene · Transactions of the American Mathematical Society · 1955 · 166 citations · Full text
Humanities, Mathematics, Logic +5