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]
- ^ 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. hdl: 2027.42/4758. S2CID 119721061.
- ^ 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 expanding it. |
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]
- ^ 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. hdl: 2027.42/4758. S2CID 119721061.
- ^ 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 expanding it. |