Twierdzenie Büchiego-Elgota-Trachtenbrota

W teorii języka formalnego twierdzenie Büchiego -Elgota-Trakhtenbrota stwierdza, że ​​język jest regularny wtedy i tylko wtedy, gdy można go zdefiniować w monadycznej logice drugiego rzędu (MSO): dla każdej formuły MSO możemy znaleźć automat skończony ( FSA) definiujące ten sam język, a dla każdego FSA możemy znaleźć formułę MSO definiującą ten sam język. Twierdzenie pochodzi od Juliusa Richarda Büchiego , Calvina Elgota i Borisa Trakhtenbrota .

Zobacz też

• Twierdzenie Trachtenbrota
• Twierdzenie Courcelle'a