Edit Distance of Finite-Valued Transducers

기술적 요약: 유한값 전이기의 편집 거리

문제 제기
본 논문은 두 유한상태 전이기 간의 편집 거리의 계산 가능성에 대해 다룬다. 함수적 전이기 (각 입력이 최대 하나의 출력에 매핑됨) 간의 편집 거리는 계산 가능한 것으로 알려져 있지만, 일반적인 전이기에 대해서는 이 문제가 일반적으로 계산 불가능하다. 저자들은 이 계산 가능성이 각 입력 단어가 고정된 상수 $k$에 대해 최대 $k$개의 출력 단어로 매핑되는 유한값 전이기의 클래스로 확장되는지 여부를 조사한다. 이 클래스는 함수적 전이기보다 엄격하게 더 표현력이 뛰어나지만, 일반적인 경우에서는 결정 불가능한 많은 근본적인 문제들 (포함 및 동치 등) 에 대해 결정 가능성을 유지한다.

방법론
제안된 해결책은 유한값 전이기 간의 거리를 계산하는 문제를 시퀀셜 전이기와 새로 도입된 거리 개념을 포함하는 일련의 계산 가능한 하위 문제로 변환하는 축소 전략을 통해 진행된다.

1. 다중 시퀀셜 전이기로의 축소:
   저자들은 임의의 유한값 전이기가 효과적으로 불확실성 없는 (따라서 함수적인) 전이기의 유한 합집합으로 분해될 수 있다는 알려진 결과를 활용한다. 그들은 두 개의 주어진 유한값 전이기 $T$와 $S$의 구성 요소 전이기들의 실행을 동기화하는 곱 자동기를 구성한다. 이 구성은 두 개의 다중 시퀀셜 전이기 $T'$와 $S'$ (시퀀셜/결정적 전이기의 유한 합집합) 를 산출하며, 이때 편집 거리 $d(T, S)$는 보존되어 $d(T', S')$와 같아진다.

2. 상대 거리의 도입:
   다중 시퀀셜 관계 (시퀀셜 함수들의 합집합) 간의 거리를 계산하기 위해 저자들은 상대 거리 개념을 도입한다. 함수 $f$에서 관계 $R$로의 상대 거리, 기호 $\vec{d}(f, R)$는 모든 입력 $u$에 대한 $f(u)$와 $R(u)$의 어떤 $v$ 사이의 최소 편집 거리의 상한으로 정의된다.
   두 다중 시퀀셜 관계 $R = \bigcup f_i$와 $S = \bigcup g_j$ 사이의 거리는 각 구성 요소 함수와 반대쪽 관계 간의 상대 거리들의 최댓값으로 나타나는 것으로 보인다:
   $$d(R, S) = \max \left( \max_i \vec{d}(f_i, S), \max_j \vec{d}(g_j, R) \right)$$

3. 상대 거리의 결정 가능성:
   상대 거리 $\vec{d}(f, R)$의 계산 가능성은 두 가지 유한성 문제로 축소함으로써 확립된다:

   • 유한성: $\vec{d}(f, R) < \infty$인지 결정.

   • $k$-유한성: 주어진 정수 $k$에 대해 $\vec{d}(f, R) \leq k$인지 결정.

   • 유한성 확인: 저자들은 $f$와 $R$의 구성 요소들의 동기식 실행을 나타내는 곱 전이기 $T$를 구성한다. 그들은 $R$의 어떤 구성 요소가 입력을 수락하는지에 따라 $f$의 도메인을 분할한다. 각 분할에 대해 그들은 곱 전이기의 강하게 연결된 성분 (SCC) 을 분석한다. 단어 켤레성 (특히, 무한히 유계인 편집 거리는 루프 출력의 켤레성을 함의함) 의 성질을 사용하여, 곱에서의 SCC 경로마다 함수의 출력 루프와 켤레 관계에 있는 출력 루프를 가진 적어도 하나의 구성 요소 관계가 존재할 때에만 상대 거리가 유한함을 증명한다. 이는 시퀀셜 전이기 간의 거리 유한성 확인 문제로 축소되며, 이는 결정 가능하다.

   • $k$-유한성 확인: 거리가 $k$로 제한되는지 결정하기 위해 저자들은 함수의 출력과 관계의 출력 사이의 편집 예산과 "남은" 매칭되지 않은 접미사를 추적하는 비결정적 유한 자동기 (NFA) $A_{C,k}$를 구성한다. $A_{C,k}$가 수락하는 언어가 곱 전이기의 도메인과 동일할 때에만 상대 거리가 $\leq k$이다.

주요 기여 및 결과

• 주요 정리: 두 유한값 유리 관계 간의 편집 거리는 Levenshtein 계열 (Levenshtein, 최장 공통 부분 수열, Damerau-Levenshtein) 의 거리 척도에 대해 계산 가능하다.
• 알고리즘적 프레임워크: 본 논문은 유한값 경우를 다중 시퀀셜 경우로, 그리고 이후 시퀀셜 함수와 다중 시퀀셜 관계 간의 상대 거리로 축소하여 이 거리를 계산하는 구성적 절차를 제공한다.
• 복잡도 분석: 저자들은 그들의 절차가 3-EXPSPACE 상한을 초래한다고 지적한다. 이는 유한값 전이기를 다중 시퀀셜 전이기로 변환하는 데 필요한 지수적 공간과, 이후 상대 거리 계산에 필요한 지수적 및 이중 지수적 공간 요구 사항에서 비롯된다. 하한은 비결정적 자동기의 동치 문제를 포함하므로 적어도 PSPACE-hard이다.

의의 및 주장
본 논문은 편집 거리의 알려진 결정 가능성을 함수적 전이기를 넘어 더 넓은 클래스인 유한값 전이기로 확장한다고 주장한다. 이는 유한값 전이기가 표현력과 알고리즘적 처리 가능성 사이의 균형을 이루며, 단일 입력이 작은 유계 집합의 유효한 출력들을 생성하는 많은 실제 시나리오 (자연어 처리나 프로그램 합성 등) 를 포착하기 때문에 중요하다.

저자들은 그들의 작업이 반응형 시스템에서의 근사 추론을 위한 기초를 제공한다고 강조한다. 고전적 검증에서 시스템은 명세에 대한 정확한 준수를 검사받는다. 상대 거리의 개념은 명세에 "가까운" 시스템에 대한 추론을 가능하게 하여 사소한 편차를 수용한다. 본 논문은 알고리즘의 효율성을 최적화한다고 주장하지는 않으며 높은 복잡도를 인정하지만, 그 결과가 실용적으로 동기 부여된 표현력 있는 전이기 클래스에서 이러한 거리들을 계산할 수 있는 이론적 가능성을 확립한다고 주장한다. 또한 이 기법들은 햄밍 거리와 같은 다른 편집 거리 척도에도 약간의 수정으로 적용 가능하다고 언급된다.