Büchi-Elgot-Trakhtenbrot theorem
From HandWiki
Short description: Formal language theorem
In formal language theory, the Büchi–Elgot–Trakhtenbrot theorem states that a language is regular if and only if it can be defined in monadic second-order logic (MSO): for every MSO formula, we can find a finite-state automaton defining the same language, and for every finite-state automaton, we can find an MSO formula defining the same language. The theorem is due to Julius Richard Büchi,[1] Calvin Elgot,[2] and Boris Trakhtenbrot.[3][4]
See also
References
- ↑ Büchi, Julius Richard (1960). "Weak second order arithmetic and finite automata". Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 6 (1–6): 66–92. doi:10.1002/malq.19600060105.
- ↑ Elgot, Calvin C. (1961). "Decision problems of finite automata design and related arithmetics". Transactions of the American Mathematical Society 98: 21–52. doi:10.1090/S0002-9947-1961-0139530-9.
- ↑ Trakhtenbrot, Boris A. (1962). "Конечные автоматы и логика одноместных предикатов" (in Russian). Siberian Mathematical Journal 3: 103–131.
- ↑ Trakhtenbrot, Boris A. (1966). "Finite automata and the logic of one-place predicates". American Mathematical Society Translations. American Mathematical Society Translations: Series 2 59: 23–55. doi:10.1090/trans2/059/02. ISBN 9780821817599.
 |  |
