경계 방문 비 결정적 선형 경계 오토마타는 일반 언어 만 인식합니까?
비결정론 적 선형 경계 오토 마톤 (nLBA)은 입력이 양 끝에 엔드 마커로 “채워져”덮어 쓰여질 수없는 단일 테이프 비결정론 적 튜링 머신을 의미하며, 헤드가 입력 영역 밖으로 이동할 수 없도록합니다. endmarkers “외부”.
숫자가있는 경우 LBA는 경계 방문입니다 있도록 모두 에서 실행 하는 모든 입력을 종료하고 대부분의 테이프의 모든 세포를 방문 번.
그러한 기계는 일반 언어 만 인식합니까? Hennie의 결과 는 내가 올바르게 읽는다면 결정 론적 기계에 대해서만 이것을 말하는 것 같습니다. 비 결정적 기계에서도 결과가 유지됩니까? 그렇다면 참조를 부탁드립니다.
답변
약간 과잉이지만,
이 논문 은 비결정론 적 Hennie 변환기가 비결정론 적 MSO- 정의 가능한 변환의 클래스를 정확히 실현한다는 것을 보여줍니다. 후자는 규칙적인 도메인을 가지고 있습니다.