부치 엘고트 트라크텐브로트 정리
Büchi-Elgot-Trakhtenbrot theorem공식언어이론에서, Büchi-Elgot-Trakhenbrot 정리에서는 언어가 단색 2차 순서 논리(MSO)로 정의될 수 있는 경우에만 정규어라고 기술하고 있다: 모든 MSO 공식에 대해 동일한 언어를 정의하는 유한 상태 오토매틱(FSA)을 찾을 수 있고, 모든 FSA에 대해 동일한 언어를 정의하는 MSO 공식을 찾을 수 있다.이 정리는 율리우스 리차드 [1]부치, 칼빈 엘고, 보리스 트라크텐브로트 덕분이다.[2][3][4]
참고 항목
참조
- ^ 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.
- ^ 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.
- ^ Trakhtenbrot, Boris A. (1962). "Конечные автоматы и логика одноместных предикатов" [Finite automata and the logic of one-place predicates]. Siberian Mathematical Journal (in Russian). 3: 103–131.
- ^ 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.
