Теорема Бюхи-Элгота-Трактенброта

Теорема формального языка

В формальной теории языков теорема Бюхи –Элгота–Трахтенброта утверждает, что язык является регулярным тогда и только тогда, когда он может быть определен в монадической логике второго порядка (MSO): для каждой формулы MSO мы можем найти конечный автомат, определяющий тот же язык, и для каждого конечного автомата мы можем найти формулу MSO, определяющую тот же язык. Теорема принадлежит Юлиусу Рихарду Бюхи ^[1] , Кэлвину Элготу ^[2] и Борису Трахтенброту ^{[3] [4} ]

Смотрите также

• Теорема Трахтенброта
• Теорема Курселя

Ссылки

1. Бючи, Юлиус Ричард (1960). «Слабая арифметика второго порядка и конечные автоматы». Zeitschrift für Mathematische Logik und Grundlagen der Mathematik . 6 (1–6): 66–92. дои : 10.1002/malq.19600060105.
2. Элгот, Кэлвин К. (1961). «Проблемы принятия решений при проектировании конечных автоматов и связанная с ними арифметика». Труды Американского математического общества . 98 : 21–52. doi : 10.1090/S0002-9947-1961-0139530-9 . hdl : 2027.42/4758 . S2CID  119721061.
3. Трахтенброт, Борис А. (1962). «Конечные автоматы и логика одноместных предикатов». Сибирский математический журнал (на русском языке). 3 : 103–131.
4. Трахтенброт, Борис А. (1966). «Конечные автоматы и логика одноместных предикатов». Переводы Американского математического общества . Переводы Американского математического общества: Серия 2. 59 : 23–55. doi :10.1090/trans2/059/02. ISBN 9780821817599.