2
$\begingroup$

There are several natural Büchi-Elgot-Trakhtenbrot-style theorems:

  • The equivalence of various finite automata on finite words and the weak monadic second order theory of 1 successor

  • The equivalence of various finite automata on binary trees and the weak monadic second order theory of 2 successors (there's also an equivalence for unranked tree automata)

  • The equivalence of various finite automata (e.g. Büchi automata) on infinite words and the full monadic second order theory of 1 successor

  • The equivalence of various finite automata on infinite binary trees and the monadic second order theory of 2 successors

Along with notions of regular expression and various other equivalences for each.

My main reference for these has been Grädel, Thomas, and Wilke's "Automata, Logics, and Infinite Games", which has most of them, but is missing discussion of the first case and doesn't seem to talk about regular expressions at all. Is there a single text that covers all four? Bonus points if it covers other monadic second order logic results like Courcelle's theorem.

$\endgroup$

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.