앨리스와 밥의 관점에서 본 정규성: Nerode식 특징화의 통합 모델

도입

정규 언어는 보통 유한 오토마타, 정규표현식, Myhill–Nerode 정리와 함께 설명된다. 하지만 고전적인 논의는 대체로 어떤 단어가 언어에 속하는지 아닌지를 판정하는 불리언 문제에 초점을 둔다. 출력이 참과 거짓에 그치지 않고 더 다양한 영역의 값이라면, 정규성은 어떻게 정의되고 특징화될 수 있을까.

arXiv 논문 “Regularity as seen by Alice and Bob”은 이 질문을 통신 복잡도 관점에서 다룬다. 입력 문자열 w를 w = w1w2로 나누고, 한쪽은 앨리스에게, 다른 한쪽은 밥에게 준다. 두 참여자는 협력하며, 상수 개수의 메시지만 주고받아 주어진 함수의 값을 계산해야 한다.

핵심 내용

• 대상을 일반화: 논문은 Σ* → D 형태의 함수를 고려한다. 여기서 Σ는 유한 알파벳이고, D는 임의의 출력 영역이다. 이는 전통적인 언어 인식보다 넓은 문제 설정이다.
• 정규성을 통신 조건으로 표현: 입력을 허용된 방식으로 어떻게 나누더라도, 앨리스와 밥은 올바른 출력값을 만들어야 한다. 핵심 제약은 교환 가능한 메시지 수가 상수로 제한된다는 점이다.
• 메시지의 제한된 형태: 각 메시지는 출력 영역의 원소이거나, 유한한 신호 집합에서 선택된 신호다. 이를 통해 유한 제어의 성격을 유지하면서도 비불리언 출력을 다룰 수 있다.
• 기존 모델과의 연결: 저자들은 여러 출력 영역에서 이 모델이 알려진 계산 모델과 일치함을 보인다. 이는 제안된 모델이 단순한 재명명이 아니라 여러 정규성 개념을 묶는 추상적 틀이 될 수 있음을 시사한다.
• 무한 알파벳으로 확장: 논문은 nominal sets 환경에서 무한 알파벳으로 프레임워크를 확장하고, 원자를 가진 단어 언어에 대한 표현력도 조사한다.

의미와 영향

이 연구는 직접 사용할 수 있는 AI 제품이나 알고리즘 발표라기보다, 형식언어 이론과 계산 복잡도 사이의 접점을 넓히는 기초 이론에 가깝다. Nerode식 정리의 강점은 “유한한 장치로 인식 가능하다”는 성질을 구조적 조건으로 바꿔 말할 수 있다는 데 있다. 이 논문은 그 아이디어를 앨리스와 밥의 분산 관찰 및 제한된 통신이라는 형태로 재구성한다.

AI와 언어 기술 측면에서도 이론적 함의가 있다. 실제 기호 시스템은 이름, 변수, 프로그램 조각, 바인딩 구조처럼 단순한 유한 알파벳만으로는 자연스럽게 설명하기 어려운 대상을 포함한다. nominal sets와 원자를 가진 단어에 대한 확장은 이런 복잡한 기호 객체를 이해하는 데 필요한 수학적 기반과 연결된다.

물론 논문이 모든 출력 영역에 대해 완전한 대응을 증명한 것은 아니다. 여러 경우에 대해 기존 모델과의 일치를 보이고, 아직 Nerode식 특징화가 부족한 다른 영역에 대해서는 유사한 대응이 성립할 것이라는 추측과 근거를 제시한다. 후속 연구가 이를 더 넓게 확인한다면, 앨리스-밥 모델은 일반화된 정규성을 설명하는 중요한 관점이 될 수 있다.

출처: arXiv