Büchi-Elgot-Trakhtenbrot 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 (FSA) defining the same language, and for every FSA, we can find an MSO formula defining the same language. The theorem is due to Julius Richard Büchi,[1] ,[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). "Конечные автоматы и логика одноместных предикатов" [Finite automata and the logic of one-place predicates]. Siberian Mathematical Journal (in Russian). 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.
 | This logic-related article is a stub. You can help Wikipedia by . |
Categories:
- Formal languages
- Mathematical logic
- Logic stubs