Büchi-Elgot-Trakhtenbrot_theorem

Büchi-Elgot-Trakhtenbrot theorem

Büchi-Elgot-Trakhtenbrot theorem

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

  1. [1]
    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.
  2. [2]
    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.
  3. [3]
    Trakhtenbrot, Boris A. (1962). "Конечные автоматы и логика одноместных предикатов" [Finite automata and the logic of one-place predicates]. Siberian Mathematical Journal (in Russian). 3: 103–131.
  4. [4]
    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.
Stub icon

This logic-related article is a stub. You can help Wikipedia by expanding it.
Share this article:

This article uses material from the Wikipedia article Büchi-Elgot-Trakhtenbrot_theorem, and is written by contributors. Text is available under a CC BY-SA 4.0 International License; additional terms may apply. Images, videos and audio are available under their respective licenses.