State Complexity of Shifts of the Fibonacci Word

1. 연구 문제 (Problem)

이 논문은 조합론적 문자열 (Combinatorics on Words) 과 형식 언어 이론의 교차점에 있는 **자동화 시퀀스 (Automatic Sequence)**의 **상태 복잡도 (State Complexity)**를 다룹니다. 구체적으로 다음과 같은 문제를 제기합니다.

• 피보나치 단어 (Fibonacci Word): $f = 01001010\dots$로 정의되는 가장 유명한 비주기적 무한 단어 중 하나입니다. 이 단어는 5 개의 상태로 구성된 자동기로 생성될 수 있습니다 (Zeckendorf 표현의 LSD-first 입력 기준).
• 시프트 연산 (Shift Operation): 주어진 시퀀스 $(a(i))_{i \ge 0}$를 $c$만큼 시프트하여 새로운 시퀀스 $(a(i+c))_{i \ge 0}$를 생성할 때, 이를 인식하는 최소 유한 상태 오토마톤 (DFAO) 의 상태 수는 어떻게 되는가?
• 핵심 질문: 피보나치 단어 $f$를 $c$만큼 시프트한 시퀀스를 생성하는 DFAO 의 상태 복잡도는 $c$에 대해 어떻게 증가하는가? 특히, 입력을 **최소 중요 자리수 우선 (lsd-first)**과 **최대 중요 자리수 우선 (msd-first)**으로 읽을 때 각각의 복잡도는 얼마인가?

일반적인 $k$-진법 기반 자동화 시퀀스의 경우, $c$만큼 시프트하는 데 $O(m \log c)$의 상태가 필요하지만, Zeckendorf 표현 (피보나치 기반) 에서는 덧셈을 한 번의 패스로 수행할 수 있는 결정적 트랜스듀서가 존재하지 않아 기존 기법이 적용되지 않는다는 점이 주요 난제였습니다.

2. 방법론 (Methodology)

저자들은 다음과 같은 세 가지 주요 기법을 혼합하여 문제를 해결했습니다:

1. 디오판토스 근사 (Diophantine Approximation):

   • 피보나치 단어의 $i$번째 비트 $f(i)$가 1 인 조건을 $\{i\phi\} \in (-\phi, -2\phi) \pmod 1$ (여기서 $\phi$는 황금비, $\{x\}$는 $x$의 소수부) 와 같은 실수 구간 조건으로 변환했습니다.
   • 이를 통해 시프트된 시퀀스 $f(i+c)$의 조건을 $\{i\phi\} \in (-(c+1)\phi, -(c+2)\phi) \pmod 1$로 재정의했습니다.

2. 구간 분할 (Interval Partitioning):

   • lsd-first 경우: Zeckendorf 표현의 낮은 자리수 비트들이 $i\phi$가 속하는 구간을 결정한다는 사실을 이용했습니다. $F_k < c+2 \le F_{k+1}$일 때, $k$개의 비트를 읽으면 $i\phi$가 속하는 구간이 결정되며, 이는 $c$에 비례하는 로그 수의 구간으로 나뉩니다.
   • msd-first 경우: 입력 비트를 왼쪽에서 오른쪽으로 읽을 때, 구간이 어떻게 분할되는지를 추적하는 일관된 분할 (consistent partition) 을 정의했습니다. 이는 $-(c+1)$과 $-(c+2)$를 피보나치 수로 표현한 후, 비트를 하나씩 제거 (shift right) 하며 생성되는 점들의 집합을 기반으로 합니다.

3. 자동화 정리 증명 (Automated Theorem Proving):

   • 논증의 일부 기술적인 부분 (예: 구간이 분할의 일부에 포함되는지 여부, 비트 추가/제거 시의 역관계 등) 을 자동화 정리 증명기인 Walnut을 사용하여 엄밀하게 검증했습니다.

3. 주요 기여 및 결과 (Key Contributions & Results)

주요 정리 (Main Theorems)

• Theorem 1 (lsd-first 경우): 피보나치 단어 $f$를 $c$만큼 시프트한 시퀀스 $(f(i+c))_{i \ge 0}$는 $O(\log c)$개의 상태를 가진 lsd-first DFAO 로 생성 가능합니다.
• Theorem 3 (msd-first 경우): 동일한 시프트된 시퀀스는 $O(\log c)$개의 상태를 가진 msd-first DFAO 로도 생성 가능합니다.
  • 의미: 일반적으로 msd-first 입력은 더 큰 상태 복잡도를 요구할 수 있지만 (예: Thue-Morse 시퀀스의 경우 $O(c)$), 피보나치 단어의 경우 두 입력 방식 모두에서 로그arithmic 한 복잡도를 가집니다.

정밀한 상태 수 공식 (Theorem 2)

• lsd-first DFAO 의 최소 상태 수는 $c \ge 5$일 때 다음과 같은 정확한 공식으로 주어집니다:
  $$2(|(c)_F| + 1) + 1 - g(c)$$
  여기서 $|(c)_F|$는 $c$의 Zeckendorf 표현의 길이 (비트 수) 이고, $g(c)$는 $f(c-1)=f(c-2)=0$일 때 1, 그렇지 않을 때 0 입니다.
• 이 결과는 상한 $O(\log c)$가 최적 (optimal) 임을 보여줍니다.

기술적 세부 사항

• Zeckendorf 표현의 확장: 음수 $-n$을 표현하기 위해 새로운 Zeckendorf 표현 방식을 도입했습니다. 이는 Rockett 와 Szűsz의 일반화 표현의 특수한 경우로, $-n = -F_k + m$ 형태를 사용하여 $\{-1, 0, 1\}$ 알파벳으로 표현합니다.
• 구간 분할의 일관성: msd-first 입력에 대해, 입력 비트가 추가될 때 구간이 어떻게 분할되는지 보장하는 '일관된 분할 (consistent partition)' 개념을 정의하고 증명했습니다.

4. 의의 및 중요성 (Significance)

1. 정보 이론적 하한에 근접: 비주기적 시퀀스의 시프트에 대한 상태 복잡도 증가량은 이론적으로 $\Omega(\frac{\log c}{\log \log c})$ 이상이어야 합니다. 피보나치 단어의 경우 $O(\log c)$라는 결과는 이 이론적 하한에 매우 근접한 것으로, 가장 효율적인 시프트 가능한 비주기적 시퀀스 중 하나임을 보여줍니다.
2. 기존 결과와의 대비:
   • Thue-Morse 시퀀스의 msd-first 시프트 복잡도는 $O(c)$로 알려져 있어 피보나치 단어와 대조적입니다.
   • $2$의 거듭제곱의 특성 시퀀스 ($p_2$) 의 경우에도$O(\log c)$가 성립하지만, 피보나치 단어는 비주기적이고 더 복잡한 구조를 가지면서도 동일한 효율성을 가진다는 점에서 주목할 만합니다.
3. 방법론적 발전: 상태 복잡도 분석에 디오판토스 근사 이론과 Walnut 과 같은 자동화 증명 도구를 결합한 새로운 접근 방식을 제시했습니다. 이는 자동화 시퀀스 이론의 다른 문제 (예: Tribonacci 단어, 이차 무리수 기반 시퀀스 등) 로 확장 가능한 틀을 제공합니다.

5. 결론

이 논문은 피보나치 단어의 시프트 연산이 가지는 놀라운 효율성을 증명했습니다. 입력 방식 (lsd-first 또는 msd-first) 에 상관없이, 시프트 양 $c$에 대해 로그arithmic 한 상태 수만으로 새로운 시퀀스를 생성할 수 있음을 보였습니다. 이는 자동화 시퀀스 이론에서 상태 복잡도의 하한과 상한을 이해하는 데 중요한 이정표가 되며, 수론과 형식 언어 이론의 깊은 연결을 보여줍니다.