WEAK SECOND-ORDER ARITHMETIC AND FINITE AUTOMATA.
Abstract
The formalism of regular expressions was introduced to obtain the following basic theorems: Synthesis - To every regular expression E one can effectively obtain a finite automata A with binary output U such that E denotes the behavior of <A,U>; Analysis - To every finite automaton A with binary output U one can effectively construct a regular expression E such that the behavior of <A,U> is denoted by E. It is shown that a more conventional formalism, a weak second-order arithmetic, can be used in place of the formalism of regular expressions. This result is of interest for automata theory because formulas of weak second-order arithmetic seem to be more convenient than regular expressions for formalizing conditions on the behavior of automata. In addition, our synthesis and analysis theorems yield rather complete information on the strength of weak second-order arithmetic, thus providing an example of applying automata theory to logic. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 01, 1959
- Accession Number
- AD0420498
Entities
People
- J. Richard Buchi
Organizations
- University of Michigan