기술 요약: 앨리스와 밥의 관점에서 본 정규성 (Regularity)

1. 문제 정의

본 논문은 출력 도메인이 불리언(Boolean) 케이스를 넘어설 때, "정규성(regularity)"에 대한 통일되고 원칙적인 특징을 규명하는 작업이 결여되어 있다는 점을 다룹로다. 정규 언어(함수 $f: \Sigma^* \to \{true, false\}$)는 유한 오토마타, 정규 표현식, Myhill-Nerode 정리와 같은 동등한 모델들을 통해 잘 이해되어 있는 반면, 다른 도메인에 대해서는 상황이 파편화되어 있습니다:

• 문자열 대 문자열 함수 (String-to-String Functions): 서로 동등하지 않은 여러 클래스(rational, regular, polyregular)가 존재하며, 어떤 것이 "진정한" 정규 함수인지에 대한 합의가 없습니다.
• 문자열 대 숫자 함수 (String-to-Number Functions): 가중치 오토마타(선형 업데이트)와 다항식 오토마타(다항식 업데이트)와 같이 구별되는 모델들이 존재하며, 어떤 것이 올바른 정규성의 개념을 포착하는지에 대한 관계가 불분명합니다.
• 무한 알파벳 (Infinite Alphabets): 알파벳이 무한한 경우(글자들이 오직 등가성만을 비교할 수 있는 경우), 유한 오토마타 모델을 들어 올리면 17개의 서로 동등하지 않은 모델이 나타나며, 이를 통합하는 원리가 부족합니다.

핵심 문제는 이러한 다양한 출력 도메인과 입력 설정 전반에 걸쳐 정규성을 특징짓는 단일하고 기계 독립적인 프레임워크를 찾는 것입니다.

2. 방법론: 프로토콜 모델

저자들은 통신 복잡도(communication complexity), 특히 Hauser [Hau89]의 연구를 응용한 모델을 기반으로 하는 통합 모델을 제안합니다. 이 모델은 두 명의 협력자, **앨리스(Alice)**와 **밥(Bob)**이 임의의 출력 도메인 $D$를 갖는 함수 $f: \Sigma^* \to D$를 계산하는 과정을 포함합니다.

주요 메커니즘:

• 입력 분할 (Input Splitting): 입력 문자열 $w$는 임의로 $w = w_1w_2$로 분할됩니다. 앨리스는 $w_1$을 보유하고, 밥은 $w_2$를 보유합니다.
• 상수 통신 (Constant Communication): 당사자들은 상수 횟수의 메시지를 교환합니다 (입력 길이에 독립적임).
• 메시지 유형: 메시지는 다음으로 구성됩니다:
  1. 신호 (Signals): 유한한 집합(비트 또는 유한 심볼)의 원소들.
  2. 도메인 원소 (Domain Elements): 출력 도메인 $D$의 원소들.
• 블랙 박스 제한 (Black Box Restriction): 결정적으로, $D$의 원소를 포함하는 메시지는 직접 "읽거나" 검사할 수 없습니다. 이들은 오직 도메인의 사전 정의된 연산(예: 필드에서의 덧셈과 곱셈, 문자열에서의 연결)을 사용하여 조작될 수만 있습니다. 이는 전체 입력 문자열을 단 하나의 도메인 원소로 인코딩하는 것을 방지합니다.
• 분할 불변성 (Split Invariance): 프로토콜은 동일한 입력 문자열 $w$에 대해 임의의 분할 $w = w_1w_2$에 대해서도 동일한 출력을 생성해야 합니다.
• 비유한성 (Non-Uniformity): 앨리스와 밥은 무제한의 계산 능력을 가집니다; 제한 사항은 오직 통신 대역폭과 블랙 박스 규율에 있습니다.

본 논문은 이를 프로토콜로 공식화하고, 다양한 도메인 $D$에 대한 표현력을 조사합니다.

3. 주요 기여 및 결과

3.1 불리언 출력 ($D = \{true, false\}$)

본 논문은 기초를 다지기 위해 이미 알려진 결과(원래 Hauser [Hau89]에 의한)를 재확립합니다:

• 정리 1.1: 어떤 언어가 프로토콜에 의해 계산된다는 것은 그 언어가 **정규(regular)**하다는 것과 동치이다.
• 의의: 이는 모델이 표준적인 정규성을 포착함을 확인해주며 일반화를 위한 토대를 제공합니다. 증명은 다회차 프로토콜을 1회차 프로토콜으로 축소하고 Myhill-Nerode 정리를 적용하는 것에 기반합니다.

3.2 필드 출력 ($D$가 필드인 경우)

이는 본 논문의 주요 기여입니다.

• 정리 1.2: 함수 $f: \Sigma^* \to D$ (여기서 $D$는 필드)는 프로토콜에 의해 계산된다는 것과 $D$ 상의 **가중치 오토마타(weighted automaton)**에 의해 계산된다는 것은 동치이다.
• 방법론: 증명은 일반적인 프로토콜을 스칼라 곱 프로토콜(앨리스와 밥이 벡터 $\sigma_A(w_1)$와 $\sigma_B(w_2)$를 계산하고, 출력은 그들의 내적이 되는 방식)로 축소하는 과정에 의존합니다. 그 후, 헨켈 행렬(Hankel matrix)의 유한한 계수(rank)를 통해 가중치 오토마타를 특징짓는 Fliess 정리 [Fli74]를 인용합니다.
• 통찰: 분할 불변성 제약은 **선형성(linearity)**을 강제합니다. 비록 프로토콜이 다항식 연산(합성을 통해)을 허용하더라도, 분할 불변성 요구 사항은 표현력을 선형 사상으로 제한하여 일반적인 다항식 오토마타를 배제합니다.
• 한계: 이 동치성은 필드에서 성립합니다. 일반적인 반링(semirings, 예: 자유 아이뎀포텐트 반링)의 경우, 프로토콜은 가중치 오토마타보다 엄격히 더 강력할 수 있습니다 (예: 프로토콜은 rational relation이 아닌 문자열 역전(reversal)을 계산할 수 있음).

3.3 문자열 출력 ($D = \Gamma^*$)

본 논문은 도메인 연산이 연결(concatenation)인 문자열 대 문자열 함수를 조사합니다.

• 추측 1.3: 문자열 대 문자열 함수는 프로토콜에 의해 계산된다는 것과 출력이 있는 결정론적 양방향 오토마타(deterministic two-way automaton with output) (전통적인 정규 함수의 정의)에 의해 계산된다는 것은 동치이다.
• 제공된 근거:
  • 함의 ($\Leftarrow$): 증명됨. 결정론적 양방향 오토마타는 교차 시퀀스(crossing sequences)를 사용하여 프로토콜로 시뮬레이션될 수 있습니다.
  • 함의 ($\Rightarrow$): 완전히 증명되지는 않았으나, 강력한 근거에 의해 뒷받받됩니다:
    • 프로토콜은 선형 크기의 출력을 생성하며 선형 시간 내에 계산 가능합니다.
    • 프로토콜은 역상(inverse images) 하에서 정규성을 보존합니다 (Boolean continuity).
    • 필드 연속성 (Field Continuity): 프로토콜은 필드 상의 가중치 오토마타와의 전치 합성(precomposition)에 대해 닫혀 있습니다.
    • 단항 케이스 (Unary Case): 추측은 단항 출력 알파벳에 대해 증명되었으며, 여기서 rational 함수는 regular 함수와 일치합니다.
• 의의: 만약 이것이 참이라면, 이는 약한 rational function들과 더 강한 polyregular function들을 구분 짓는, 정규 문자열 대 문자열 함수의 기계 독립적인 특징을 제공하게 됩니다.

3.4 무한 입력 알파벳

본 논문은 글자들이 오직 등가성만을 비교할 수 있는 무한 알파벳(atoms)으로 모델을 확장하며, 이를 위해 **노미널 집합(nominal sets)**과 오빗-파이니트 집합(orbit-finite sets) 프레임워크를 사용합니다.

• 추측 6.5: 무한 알파벳 상의 언어가 오빗-파이니트 프로토콜에 의해 계산된다는 것은 unambiguous register automaton에 의해 인식된다는 것과 동치이다.
• 맥락: 결정론적 레지스터 오토마타는 너무 약하고(특정 역전을 처리할 수 없음), 비결정론적 레지스터 오토마타는 너무 강합니다(프로토콜이 할 수 없는 반복을 감지할 수 있음). 프로토콜은 이 사이의 "골디락스(Goldilocks)" 모델인 unambiguous automaton을 제안합니다.
• 결과:
  • 함의 ($\Leftarrow$): 증명됨. 저자들은 **오빗(orbits)**과 **해바라기 보조정리(sunflower lemma)**의 변형을 사용하여 가능한 중간 상태의 집합을 반복적으로 좁혀나감으로써 unambiguous automaton을 시뮬레이션하는 다회차 프로토콜을 구축합니다.
  • 함의 ($\Rightarrow$): 가중치 오빗-파이니트 오토마타를 통한 근거가 제공됩니다. 저자들은 프로토콜이 오빗-파이니트하게 스팬되는 좌측 도함수(left derivatives)를 갖는 함수를 계산함을 보여주는 Orbit-Finite Fliess 정리(정리 6.19)를 증명합니다. 이는 프로토콜이 결정 가능하며 가중치 모델과 비결정론적 모델의 교집합 내에 있음을 시사합니다.
• 참신함: 유한 알파벳의 경우와 달리, 무한 알파벳에 대한 프로토콜은 한 회차로 축소될 수 없습니다; 상호작용적 특성이 필수적입니다.

4. 의의 및 주장

본 논문은 특정 오토마타 정의를 초월하는 정규성의 통합 모델을 제공한다고 주장합니다. 그 의의는 다음과 같습니다:

1. 기계 독립성: 정규성을 특정 상태 전이 구조가 아닌 통신 제약(상수 메시지, 블랙 박스 연산)을 통해 특징짓습니다.
2. 통합: 다양한 모델들(가중치 오토마타, 결정론적 양방향 트랜스듀서, unambiguous register automata)이 모두 동일한 근본 원리, 즉 제한된 도메인 연산을 가진 상수 정보 흐름의 사례임을 시사합니다.
3. 새로운 특징 규명: 가중치 오토마타에 대한 기계 독립적 특징(정리 1.2)을 제공하며, 정규 문자열 대 문자열 함수(추측 1.3) 및 unambiguous register automata(추측 6.5)에 대한 특징을 제안합니다.
4. 계산적 속성: 모델은 다른 트랜스듀서 모델(예: polyregular functions)에서는 항상 보장되지 않는 선형 출력 크기 및 계산 가능성과 같은 바람직한 속성을 자연스럽게 강제합니다.

저자들은 문자열 대 문자열 및 무한 알파벳 케이스에 대해서는 겸손한 태도를 유지하며, 이를 완전히 해결된 정리가 아닌 상당한 근거(한 방향의 증명, 단항 케이스, 구조적 속성)에 의해 뒷받침되는 추측으로 제시합니다. 또한 "블랙 박스" 제한이 양호한 함수를 생성하지 못할 수 있는 일반적인 반링이나 임의의 출력 도메인에 대한 결과를 주장하는 것을 명시적으로 피합니다.