Misplaced Pages

Büchi-Elgot-Trakhtenbrot theorem

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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, Calvin Elgot, and Boris Trakhtenbrot.

See also

References

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

Categories: