크론-로즈 이론
Krohn–Rhodes theory수학과 컴퓨터 과학에서 Krohn-Rodes 이론(또는 대수학 오토마타 이론)은 기초 구성 요소 측면에서 그것들을 분해하려는 유한한 세미그룹과 오토마타 연구에 대한 접근법이다.이러한 구성요소는 피드백이 없는 방식("호흡기 제품" 또는 "캐스케이드"라고 함)으로 결합되는 유한한 주기적 세미그룹과 유한 단순 그룹에 해당한다.
Krohn과 Rodes는 유한한 오토마타에 대한 일반적인 부패를 발견했다.그러나 저자들은 연구를 하면서 유한한 세미그룹 이론에서 예상치 못한 중대한 결과를 발견하고 증명하여 유한한 오토마타와 세미그룹 사이의 깊은 연관성을 밝혀냈다.
크론-로즈 정리 정의 및 설명
T를 세미그룹으로 하자.T의 서브그룹에 대한 동형상 이미지인 세미그룹 S는 T의 디비저라고 한다.
유한한 세미그룹에 대한 Krohn-Rodes 정리에서는 모든 유한한 세미그룹 S는 유한한 단순집단의 유한한 교대 화환 생산물의 구분자이며, 각각은 S의 구분자, 유한한 주기적 세미그룹(비경쟁적 하위집단을 포함하지 않음)의 구분자임을 명시하고 있다.[1]
오토마타 공식에서, 유한한 오토마타에 대한 Krohn-Rodes 정리에서는 상태 Q와 입력 집합 I, 출력 알파벳 U를 가진 유한한 오토마톤 A를 부여한 다음, 새로운 오토마톤 A가 "단순", 무reducable aomata의 계단식으로 포함되도록 상태를 Q'로 확장할 수 있다.특히 A는 전환 세미그룹이 유한단순군인 (1)오토마타와 병렬로 운영되는 플립플롭스 뱅크인 (2)오토마타의 피드-포워드 캐스케이드에 의해 에뮬레이션된다.[nb 1]새로운 오토매틱 A'는 입출력 기호가 A와 동일하다.여기서 계단식 오토마타의 상태와 입력 모두 매우 특별한 계층적 좌표 형태를 가지고 있다.
더욱이 A의 변환 세미그룹을 나누는 각 단순그룹(프라임) 또는 비그룹(플립플롭모노이드의 서브그룹)은 계단식 일부 요소의 전환 세미그룹을 분할해야 하며, 구성요소의 구분자로 발생해야 하는 프리타임만 A의 전환 세미그룹을 분할하는 것이다.
그룹 복잡성
유한한 세미그룹 S의 Krohn-Rodes 복잡성(집단 복잡성 또는 단지 복잡성이라고도 함)은 유한한 그룹과 유한한 주기적 세미그룹으로 이루어진 화환 제품에서 S가 분할자인 최소 수의 그룹이다.
모든 유한한 주기적 의미집단은 복잡성이 0인 반면, 비삼각적 유한집단은 복잡성이 1이다.사실, 모든 비-음수 정수 복잡성의 세미그룹들이 있다.예를 들어, n이 1보다 큰 경우, 모든 (n+1) × (n+1) 상삼각형 행렬의 곱셈형 세미그룹은 고정 유한 필드에 대한 복잡성 n을 가진다(Kambites, 2007).
유한한 세미그룹 이론의 주요한 개방적 문제는 복잡성의 결정 가능성이다: 유한한 세미그룹의 곱셈표를 고려할 때 Krohn-Rodes 복잡성을 계산할 알고리즘이 있는가?복잡성에 대한 상한과 보다 정확한 하한을 얻었다(예: Rodes & Steinberg, 2009 참조).Rodes는 그 문제를 해결할 수 없다고 추측했다.[2]
기록 및 응용 프로그램
1962년 회의에서 케네스 크론(Kenneth Krohn)과 존 로즈(John Rodes)는 (결정론적) 유한 자동화를 그 자체로 유한한 "단순한" 구성요소로 분해하는 방법을 발표했다.어떤 철학을 포함한다 이 공동 작품은 하버드 대학에서 둘 다 Krohn의 박사 학위 논문과 MIT.[3]Simpler 교정에서 로즈의 학위 논문, 그리고 정리 구조물은 무한정의 일반화로 구성되어, 그 때 이후로( 보게재됐다 스타인 버그와 로즈의 2009년 책의 4장 유한 Semigroups까지 항의라도의 q-Theory.r개요).
1965년 Krohn과 Rodes에 의한 논문에서 유한한 오토마타(또는 동등하게 순차적인 기계)의 분해에 관한 정리의 증명은 대수적 세미그룹 구조를 광범위하게 이용했다.이후 증거에는 유한변환 세미그룹의 유한 화환 제품을 사용한 주요 단순화가 포함되었다.그 정리는 요르단-을 일반화한다.유한 그룹(프리미엄이 유한한 단순 그룹인 경우), 모든 유한 변환 세미그룹(프리미엄이 다시 유한한 단순 그룹과 "플립 플롭(flip-flop)"의 모든 하위 그룹(위 참조)에 대한 쾰더 분해.그룹과 보다 일반적인 유한 자동 분해 모두 일반의 상태 세트를 확장해야 하지만 동일한 수의 입력 기호가 허용된다.일반적인 경우, 이것들은 계층적 "조정 체계"를 가진 더 큰 구조에 내장되어 있다.
크론(Krohn)과 로도스(Rodes)가 명시적으로 그들의 정리를 오토마타(Automata)에 대한 "프라임 분해 정리"라고 언급하는 것처럼 '프라임'의 개념을 이해하는데 신중해야 한다.그러나 분해의 성분은 원시 자동이 아니다. 오히려 원시 개념은 더 정교하고 대수적이다. 분해의 구성 자동화와 관련된 세미그룹과 그룹은 화환과 관련하여 엄격하고 자연적인 대수적 의미에서 원시(또는 불가해한)이다.h 제품(Eilenberg, 1976년).또한, 이전의 분해 이론과는 달리, 크론-로이드 분해는 대개 주 세트의 확장이 필요하며, 확장된 자동화가 분해되는 것을 커버(에뮬레이션)한다.이러한 사실들은 컴퓨터 구현을 이용할 수 있게 된 최근까지(Egri-Nagy & Nehaniv 2005, 2008) 정리를 이해하기 어렵게 하고 실용적으로 적용하기 어렵게 만들었다.
H.P. 자이거(1967)는 홀로노미 분해(Holonomy discovery,[nb 2] Eilenberg 1976년)라는 중요한 변종을 증명했다.홀로노미 방법은 비교적 효율적인 것으로 보이며 A에 의해 계산적으로 구현되었다.에그리-나기(Egri-Nagy & Nehaniv 2005).
마이어와 톰슨(1969)은 하르트마니스와 스턴스가 이전에 개발한 분해와 동등한 유한 오토마타에 대한 Krohn-Rodes 분해 버전을 주지만, 유용한 분해에 대해서는 (비퍼뮬레이션 오토마타 사례에 대해서는) 원래 오토마톤의 상태 세트를 확장하는 개념이 필수적이다.
현재 Krohn-Rodes 분해(예: [Krohn, Rodes & Tilson 1968], [ésiki 2000], [Diekert et al. 2012])에 대한 많은 증거와 구축이 존재하며, 홀노노미 방법은 일반적으로 가장 대중적이고 효율적이다(모든 경우는 아니지만).모노이드와 범주의 밀접한 관계 때문에 Krohn-Rodes 정리 버전이 범주 이론에 적용된다.이러한 관찰과 유사한 결과의 증거는 웰스(1980)에 의해 제시되었다.[nb 3]
세미그룹/모노이드에 대한 Krohn-Rodes 정리는 요르단-모노이드와 유사하다.유한집단에 대한 쾰더 정리(집단보다는 세미그룹/모노이드에 대한)이와 같이 정리는 세미그룹/모노이드 이론에서 깊고 중요한 결과물이다.이후가 이전에 따라 앞으로semigroup/monoid 공리 너무 힘의 구조체를 정리, 그리고 이전의 작업(Hartmanis&스턴스)은 핑크 위해서 훨씬 더 적고 일반적인 엄격한 분해 결과를 보여 줄 수 있었다 너무 약하로 여겨졌던 그 정리 또한 많은 수학자 및 컴퓨터 scientists[nb 4]에 놀라운 일이었다.eautomata
Egri-Nagy와 Nehaniv(2005, 2008–)의 작업은 컴퓨터 대수 시스템 GAP를 사용하여 유한 집단에 대한 관련 분해와 함께 확장된 Krohn-Rodes 분해의 홀로노미 버전을 더욱 자동화한다.
세미그룹과 단일 이론 이외의 애플리케이션은 이제 계산적으로 실현 가능하다.생물학 및 생화학적 시스템(예: Egri-Nagy & Nehaniv 2008), 인공지능, 유한 상태 물리학, 심리학 및 게임 이론(예: Rodes 2009 참조)의 연산이 포함된다.
참고 항목
메모들
- ^ 플립플롭(flip-flop)은 세 가지 입력 연산이 있는 2개 상태 자동이다. 즉, ID(상태 변경 안 함)와 두 개의 재설정 연산이 있다(두 상태 중 특정 상태로 리셋하여 현재 상태를 덮어쓴다).이는 1비트 읽기-쓰기 저장 장치로 간주할 수 있다. ID는 비트 판독에 해당하며(그 값은 변경되지 않은 채로), 두 가지는 비트 값을 0 또는 1로 설정하도록 재설정된다.재설정은 현재 저장된 비트 값을 파괴하므로 되돌릴 수 없는 연산자라는 점에 유의하십시오.NB: 플립플롭의 세미그룹과 모든 서브그룹들은 수정할 수 없다.
- ^ 에일렌베르크 1976년과 뒤뫼시, 네하니브, 2005년에는 자이거의 논문에서 오류를 바로잡는 증거를 제시한다.
- ^ 참고 항목(Tilson 1989년)
- ^ C.L. Nehaniv, 서문 (Rodes, 2009)
참조
- Barrington, David A. Mix (1992). "Some problems involving Razborov-Smolensky polynomials". In Paterson, M.S. (ed.). Boolean function complexity, Sel. Pap. Symp., Durham/UK 1990. London Mathematical Society Lecture Notes Series. Vol. 169. pp. 109–128. ISBN 978-0-521-40826-4. Zbl 0769.68041.
- Diekert, Volker; Kufleitner, Manfred; Steinberg, Benjamin (2012). "The Krohn-Rhodes Theorem and Local Divisors". Fundamenta Informaticae. 116 (1–4): 65–77. arXiv:1111.1585. doi:10.3233/FI-2012-669. ISSN 0169-2968.
- Pál Dömösi; Chrystopher L. Nehaniv (2005). Algebraic Theory of Automata Networks: An Introduction. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics. ISBN 978-0-89871-569-9.
- Egri-Nagy, A. 및 Nehaniv, C. L.(2005) "유한 상태 오토마타의 위계적 분해:제9회 오토마타 국제회의(CIAA 2004), 캐나다 킹스턴, 2004년 7월 22-24일(CIAA 2004)에서 열린 "Krohn-Rodes 이론의 구현 비교"에서, Revision Selected Papers, Editor: Domaratzki, M.; Okhotin, A.; Salomaaaa, K. et et et et.; et et et et et.; et.; et.; et.; et. et. et. et. et. et.; et.;Springer 강의 노트 컴퓨터 과학, Vol. 3317, 페이지 315–316, 2005
- Egri-Nagy, Attila; Nehaniv, Chrystopher L. (Summer 2008). "Hierarchical Coordinate Systems for Understanding Complexity and its Evolution with Applications to Genetic Regulatory Networks" (PDF). Artificial Life. 14 (3): 299–312. doi:10.1162/artl.2008.14.3.14305. hdl:2299/16600. ISSN 1064-5462. PMID 18489252.
- Eilenberg, Samuel (1976). Automata, Languages and Machines. Pure and applied mathematics, Lecture notes in mathematics. New York: Academic Press. ISBN 978-0-12-234001-7. 두 장은 Bret Tilson에 의해 쓰여진다.
- Ésik, Z. (March 2000). "A proof of the Krohn–Rhodes decomposition theorem". Theoretical Computer Science. 234 (1–2): 287–300. doi:10.1016/s0304-3975(99)00315-1. ISSN 0304-3975.
- Hartmanis, Juris; Stearns, R. E. (1966). Algebraic structure theory of sequential machines. Prentice–Hall. ASIN B0006BNWTE.
- Holcombe, W.M.L. (1982). Algebraic automata theory. Cambridge Studies in Advanced Mathematics. Vol. 1. Cambridge University Press. ISBN 978-0-521-60492-5. Zbl 0489.68046.
- Kambites, Mark (2007). "On the Krohn–Rhodes complexity of semigroups of upper triangular matrices". International Journal of Algebra and Computation. 17 (1): 187–201. CiteSeerX 10.1.1.657.4000. doi:10.1142/S0218196707003548. ISSN 0218-1967.
- Krohn, K. R.; 그리고 Rodes, J. L. (1962), "기계의 Algebraic 이론", 오토마타 수학적 이론 심포지엄 진행 (편집자:폭스, J), (와일리-인터사이언스)
- Krohn, Kenneth; Rhodes, John (April 1965). "Algebraic Theory of Machines. I. Prime Decomposition Theorem for Finite Semigroups and Machines" (PDF). Transactions of the American Mathematical Society. 116: 450–464. doi:10.2307/1994127. ISSN 0002-9947. JSTOR 1994127. Retrieved September 18, 2010.
- Krohn, Kenneth; Rhodes, John L. (August 1968). Arbib, Michael A. (ed.). Algebraic Theory of Machines, Languages and Semigroups. Academic Press. ISBN 978-0-12-059050-6.
- Lallement, Gerard (1971-03-01). "On the prime decomposition theorem for finite monoids". Theory of Computing Systems. 5 (1): 8–12. doi:10.1007/BF01691462. ISSN 1433-0490.
- Meyer, A. R.; Thompson, C. (1969-06-01). "Remarks on algebraic decomposition of automata" (PDF). Theory of Computing Systems. 3 (2): 110–118. CiteSeerX 10.1.1.649.4716. doi:10.1007/BF01746516. ISSN 1432-4350.
- John Rhodes; Benjamin Steinberg (2008-12-17). The q-theory of finite semigroups. Springer Verlag. ISBN 978-0-387-09780-0.
- Straubing, Howard; Thérien, Denis (2002). "Weakly iterated block products of finite monoids". In Raisbaum, Sergio (ed.). Lecture Notes in Computer Science. LATIN 2002: Theoretical Informatics. Vol. 2286. Berlin: Springer. pp. 91–104. doi:10.1007/3-540-45995-2_13. ISBN 978-3-540-43400-9. Retrieved September 18, 2010.
- Rhodes, John L. (September 3, 2009). Nehaniv, Chrystopher L. (ed.). Applications of Automata Theory and Algebra via the Mathematical Theory of Complexity to Finite-State Physics, Biology, Philosophy, and Games. Singapore: World Scientific Publishing Company. ISBN 978-981-283-696-0.
- Tilson, Bret (September 1987). "Categories as algebra: an essential ingredient in the theory of monoids". Journal of Pure and Applied Algebra. 48 (1–2): 83–198. doi:10.1016/0022-4049(87)90108-3. ISSN 0022-4049.
- Wells, C. (1980). "A Krohn–Rhodes theorem for categories". Journal of Algebra. 64: 37–45. doi:10.1016/0021-8693(80)90130-1. ISSN 0021-8693.
- Zeiger, H. P. (April 1967). "Cascade synthesis of finite state machines". Information and Control. 10 (4): 419–433. doi:10.1016/S0019-9958(67)90228-8. ISSN 1462-3889. 에라타:정보 및 제어 11(4): 471(1967), 에라타 추가.
추가 읽기
- Rhodes, John L. (2010). Chrystopher L. Nehaniv (ed.). Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. World Scientific Pub Co Inc. ISBN 978-981-283-696-0.
- Rhodes, John; Steinberg, Benjamin (2008-12-17). The q-theory of finite semigroups. Springer Verlag. ISBN 978-0-387-09780-0.
- Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. ISBN 978-3-7643-3719-3. Zbl 0816.68086.
외부 링크
- 버클리 캘리포니아 대학교의 John L. Rodes 교수 웹페이지
- SgpDec: A가 개발한 순열 그룹과 변환 세미그룹의 계층적 구성과 분해. 에그리-나기와 C. L. 네하니브.GAP 컴퓨터 대수 시스템을 위한 오픈 소스 소프트웨어 패키지.
- John L. Rhodes (2010). Chrystopher L. Nehaniv (ed.). Applications of automata theory and algebra: via the mathematical theory of complexity to biology, physics, psychology, philosophy, and games. World Scientific Pub Co Inc. ISBN 978-981-283-696-0.
- Simon DeDeo에 의한 Crohn-Rodes Organization (제5장); Santa Fe Institute Complex Explorer MOC Renovation to Reonormalization의 일부.
