WEAK SECOND-ORDER ARITHMETIC AND FINITE AUTOMATA.
MICHIGAN UNIV ANN ARBOR COLL OF LITERATURE SCIENCE AND THE ARTS
Pagination or Media Count:
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