검색 기능은 준비 중입니다.
검색 기능은 준비 중입니다.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Self-Verifying Nondeterministic and Las Vegas Multihead Finite Automata 자체 검증 비결정적 및 라스베가스 멀티헤드 유한 오토마타

Katsushi INOUE, Yasunori TANAKA, Akira ITO, Yue WANG

  • 조회수

    0

  • 이것을 인용

요약 :

이 논문은 결정론적, 라스베거스, 자체 검증 비결정론적, 비결정론적(단순) 다중 헤드 유한 오토마타의 수용 능력에 대한 비교 연구에 관한 것입니다. 우리는 각각에 대해 (1)을 보여줍니다. k 2, 단방향 결정적 k-head (관련, 단순 k-머리) 유한 오토마타는 단방향 라스베거스보다 덜 강력합니다. k-head (관련, 단순 k-머리) 유한 오토마타, (2) 단방향 자체 검증 비결정적 단순 2헤드 유한 오토마타에서는 허용되지만 단방향 결정적 단순 다중 헤드 유한 오토마타에서는 허용되지 않는 언어가 있습니다. (3) 단방향 비결정적 2헤드(각각, 단순 2헤드) 유한 오토마톤에서는 허용되는 언어이지만 단방향 자체 검증 비결정적 다중 헤드(각각, 단순 다중 헤드) 유한 오토마톤에서는 허용되지 않는 언어, (4) 각 k 1, 양방향 라스베가스 k-head (관련, 단순 k-head) 유한 오토마타는 양방향 자체 검증 비결정론과 동일한 수용 능력을 가집니다. k-head (관련, 단순 k-머리) 유한 오토마타 및 (5) 양방향 라스베거스 단순 2헤드 유한 오토마타는 양방향 결정론적 단순 2헤드 유한 오토마타보다 더 강력합니다.

발행
IEICE TRANSACTIONS on Fundamentals Vol.E84-A No.5 pp.1094-1101
발행일
2001/05/01
공개일
온라인 ISSN
DOI
원고의 종류
Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
범주

작성자

키워드