返回Google圖書搜尋

Weak Second-order Arithmetic and Finite Automata

其他書名	Technical Report
出版	University of Michigan Research Institute, 1959
URL	http://books.google.com.hk/books?id=njtvHQAACAAJ&hl=&source=gbs_api

註釋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).