Alice와 Bob 모델이 Nerode 스타일의 정규성 특징을 통합

새로운 논문은 서로 다른 출력 도메인을 가진 함수에 걸친 Nerode 스타일의 정규성 특징에 대한 통합 모델을 제안하며, 통신 복잡성 분야에서 Hauser의 연구를 일반화합니다. 이 모델은 계산 가능성 가정을 완화하여 비부울 출력 도메인을 허용하며, 여기서 입력 문자열은 Alice와 Bob 두 당사자 간에 분할되어 함수 값을 계산하기 위해 상수 개의 메시지를 교환합니다.

저자들은 여러 도메인에 대해 이 모델이 알려진 계산 모델과 일치함을 보이며, 명명 집합을 사용하여 무한 알파벳으로 프레임워크를 확장했습니다.

이 연구는 Nerode 스타일의 정규성 특징이 없는 다른 도메인에서도 유사한 대응 관계가 성립한다는 추측에 충분한 지지 증거를 제공합니다.