In
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet".
The alphabet of a formal language consists of symbol ...
, 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
In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important in the logic of graphs, because of Courcelle's ...
(MSO): for every MSO formula, we can find a
finite-state automaton
A finite-state machine (FSM) or finite-state automaton (FSA, plural: ''automata''), finite automaton, or simply a state machine, is a mathematical model of computation. It is an abstract machine that can be in exactly one of a finite number o ...
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
Julius Richard Büchi (1924–1984) was a Swiss logician and mathematician.
He received his Dr. sc. nat. in 1950 at ETH Zurich under the supervision of Paul Bernays and Ferdinand Gonseth. Shortly afterwards he went to Purdue University in Laf ...
,
Calvin Elgot Calvin may refer to:
Names
* Calvin (given name)
** Particularly Calvin Coolidge, 30th President of the United States
* Calvin (surname)
** Particularly John Calvin, theologian
Places
In the United States
* Calvin, Arkansas, a hamlet
* Calvin ...
, and
Boris Trakhtenbrot
Boris (Boaz) Abramovich Trakhtenbrot (, ; 19 February 1921 – 19 September 2016) was a Russian-Israeli mathematician in logic, algorithms, theory of computation, and cybernetics.
Biography
Trakhtenbrot was born into a Jewish family in Brichevo, ...
.
See also
*
Trakhtenbrot's theorem In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable. In fact, the class of valid se ...
*
Courcelle's theorem In the study of graph algorithms, Courcelle's theorem is the statement that every graph property definable in the monadic second-order logic of graphs can be decided in linear time on graphs of bounded treewidth. The result was first proved by B ...
References
Formal languages
Mathematical logic
Theorems in the foundations of mathematics
{{logic-stub