Complexity of Linear Subsequences of $k$-Automatic Sequences

이 논문은 $k$-자동화 수열의 선형 부분열과 내부 수열의 복잡성 간의 관계를 규명하고, Zantema 와 Bosma 의 최근 질문을 해결하며, Büchi 산술을 기반으로 한 자동화 구성의 상태 및 실행 시간 복잡성을 분석합니다.

핵심

🏭 핵심 비유: 거대한 숫자 공장

이 논문의 세계를 상상해 보세요. 거대한 숫자 공장이 있습니다.

• 입력: 공장에 들어오는 숫자들은 k 진법 (예: 2 진법, 10 진법) 으로 쓰인 레고 블록 덩어리입니다.
• 작업자 (DFAO): 이 레고 블록을 보고 특정 규칙에 따라 결과물 (0 이나 1 같은 출력) 을 만들어내는 작은 로봇들이 있습니다.
• 상태 (State): 로봇이 현재 어떤 작업을 하고 있는지 나타내는 **'기억 모드'**입니다. 로봇이 기억할 수 있는 모드가 많을수록 더 복잡한 일을 할 수 있지만, 로봇이 너무 크면 비효율적입니다.

이 연구는 **"이 로봇들이 특정 규칙을 따르거나, 숫자를 변형할 때, 로봇을 얼마나 작게 만들 수 있을까?"**를 탐구합니다.

---

🧩 주요 발견 1: 숫자 더하기와 곱하기 (관계 인식)

우리가 흔히 하는 **더하기 (+)**나 곱하기 (×) 연산을 이 로봇들이 어떻게 처리하는지 연구했습니다.

• 더하기: 두 숫자를 더할 때, 로봇은 **'올림 (Carry)'**이라는 작은 메모리만 2 개 정도 가지고 있으면 됩니다. (예: 1+1=2 일 때 1 을 넘겨주는 것) 그래서 로봇의 크기는 매우 작습니다.
• 상수 더하기: "어떤 숫자에 100 을 더하기" 같은 작업은, 100 이라는 숫자가 얼마나 큰지에 따라 로봇의 크기가 달라집니다. 숫자가 크면 로봇의 '기억 모드'가 조금 더 필요하지만, 숫자의 크기에 비례해서만 커집니다.
• 곱하기: "어떤 숫자에 5 를 곱하기"는 5 개의 기억 모드가 필요합니다.

👉 결론: 기본적인 사칙연산은 로봇을 아주 효율적으로 설계할 수 있습니다.

---

🚂 주요 발견 2: 열차의 특정 칸만 뽑아내기 (선형 부분 수열)

이게 이 논문의 가장 중요한 발견입니다.

원래 로봇이 만들어내는 숫자 열 (시퀀스) 이 있다고 칩시다. 예를 들어: A, B, C, D, E, F, G...
이제 우리는 매 3 칸마다 있는 숫자만 뽑아내서 새로운 열을 만들고 싶다고 해봅시다. (A, D, G... 즉, $h(3i)$)

• 기존의 생각: 원래 로봇이 100 개 모드를 가진다면, 새로운 로봇도 100 개 정도만 있으면 될 거라 생각했습니다.
• 이 논문의 발견: 아니요! 새로운 로봇의 크기는 **원래 로봇이 만들어낸 숫자 패턴의 '다양성 (서브워드 복잡도)'**에 비례합니다.
  • 비유: 원래 로봇이 만들어낸 숫자 열이 "1, 2, 1, 2, 1, 2..."처럼 단순하다면, 새로운 로봇도 아주 작게 만들 수 있습니다. 하지만 "1, 2, 3, 1, 4, 2, 5..."처럼 패턴이 복잡하고 다양하다면, 새로운 로봇은 훨씬 더 큰 기억 공간이 필요합니다.
  • 핵심: "원래 로봇의 크기"가 아니라, **"원래 로봇이 만들어낸 결과물의 복잡도"**가 새로운 로봇의 크기를 결정합니다.

이 발견은 Zantema 와 Bosma라는 학자들이 오랫동안 풀지 못했던 난제를 해결해 주었습니다.

---

🎭 주요 발견 3: 유명한 '튀에 - 모르 (Thue-Morse)' 열

연구진은 유명한 '튀에 - 모르'라는 숫자 열을 실험대에 올렸습니다. 이 열은 수학적으로 매우 흥미로운 패턴을 가집니다.

• 이 열을 2 배, 3 배, 4 배... 간격으로 잘라냈을 때, 각각의 새로운 로봇이 얼마나 큰지 정확한 공식을 찾아냈습니다.
• 예를 들어, 2 의 거듭제곱 간격으로 잘라내면 로봇 크기가 변하지 않지만, 다른 간격으로 자르면 로봇 크기가 급격히 변하는 패턴을 발견했습니다.

---

⏱️ 주요 발견 4: 로봇을 만드는 시간 (실행 시간)

이제 실제 컴퓨터 프로그램 (Walnut 같은 도구) 이 이 로봇들을 설계하는 데 얼마나 시간이 걸리는지 분석했습니다.

• 비유: 로봇을 설계하는 공장이 있다고 칩시다.
  • 간단한 더하기 로봇을 만드는 데는 순간이 걸립니다.
  • 하지만 "1000 을 곱하고 50 을 더하는" 복잡한 로봇을 만들려면, 공장은 로그 (Log) 함수에 비례하는 시간이 걸립니다. 숫자가 아무리 커도, 로그 함수는 천천히 커지기 때문에 실제로는 매우 효율적입니다.
• 결론: 우리가 연구한 이 방법들은 이론적으로만 가능한 것이 아니라, 실제로 컴퓨터로 구현했을 때도 빠르고 효율적입니다.

---

🌟 요약: 이 연구가 왜 중요한가요?

1. 효율성: 복잡한 숫자 패턴을 처리하는 로봇을 최소한의 크기로 만들 수 있는 방법을 찾았습니다. (컴퓨터 메모리 절약)
2. 예측 가능성: 어떤 규칙을 적용했을 때 로봇이 얼마나 커질지 정확히 예측할 수 있는 공식을 제시했습니다.
3. 난제 해결: 수학자들이 오랫동안 풀지 못했던 "선형 부분 수열의 크기 문제"를 해결했습니다.

한 줄 요약:

"숫자를 다루는 작은 로봇들이 복잡한 작업을 할 때, 그 로봇의 크기는 작업의 난이도보다 **'결과물의 패턴이 얼마나 다양한지'**에 따라 결정된다는 놀라운 사실을 발견하고, 그 로봇을 빠르고 작게 만드는 방법을 찾아냈습니다."

이 연구는 암호학, 데이터 압축, 그리고 인공지능의 기초가 되는 '자동화 이론' 분야에서 더 빠르고 효율적인 시스템을 만드는 데 큰 기여를 할 것입니다.

기술 요약

이 논문은 $k$-자동화 시퀀스 (k-automatic sequences) 의 선형 부분열 (linear subsequences) 과 관련된 상태 복잡도 (state complexity) 및 런타임 복잡도 (runtime complexity) 를 연구한 학술지입니다. 저자들은 Delaram Moradi, Narad Rampersad, Jeffrey Shallit 이며, 베이스 $k$ 입력을 사용하는 오토마타의 구조적 특성과 Büchi 산술 (Büchi arithmetic) 을 통한 자동화 구성의 효율성을 분석했습니다.

다음은 논문의 주요 내용, 방법론, 기여도 및 결과에 대한 상세한 기술적 요약입니다.

---

1. 연구 배경 및 문제 정의

• 주제: $k$-자동화 시퀀스 $(h(i))_{i \ge 0}$의 선형 부분열 $(h(ni + c))_{i \ge 0}$를 생성하는 최소 결정적 유한 오토마타 출력기 (DFAO) 의 상태 수 (상태 복잡도) 를 규명하는 것.
• 배경:
  • Cobham 의 정리에 따르면 $k$-자동화 시퀀스의 선형 부분열 또한 $k$-자동화됩니다.
  • Zantema 와 Bosma 는 이전 연구에서 LSD-First (최소 중요 자리수 우선) 입력에 대한 상태 복잡도 상한을 제시했으나, MSD-First (최대 중요 자리수 우선) 입력에 대한 정확한 상한과 하한, 그리고 내부 시퀀스 (interior sequence) 의 부분단어 복잡도 (subword complexity) 와의 관계를 명확히 하지 못했습니다.
  • 또한, Walnut 과 같은 소프트웨어 시스템에서 Büchi 산술을 사용하여 이러한 오토마타를 구성할 때의 계산 비용 (런타임) 에 대한 분석이 부족했습니다.
• 핵심 질문:
  1. MSD-First 입력을 사용할 때, 선형 부분열을 생성하는 DFAO 의 상태 복잡도는 얼마인가?
  2. 이 복잡도는 원래 시퀀스의 내부 시퀀스 부분단어 복잡도와 어떤 관계가 있는가?
  3. Büchi 산술 해석을 통해 이러한 오토마타를 구성하는 데 소요되는 시간은 얼마인가?

2. 방법론

• 오토마타 구성 및 분석:
  • DFAO (Deterministic Finite Automaton with Output): 입력을 베이스 $k$로 받아 시퀀스의 $i$번째 항을 출력하는 오토마타를 정의.
  • 내부 시퀀스 (Interior Sequence): DFAO 의 출력 함수를 항등 함수로 바꾼 오토마타가 생성하는 시퀀스. 이는 원래 시퀀스의 상태 전이 구조를 직접 반영.
  • 부분단어 복잡도 (Subword Complexity): 시퀀스에서 길이 $n$인 연속된 부분열 (factor) 의 개수를 나타내는 함수 $\rho_x(n)$.
• Büchi 산술 해석:
  • 자연수, 덧셈, 그리고 $k$-진법에서의 $k$-adic valuation ($V_k(n)$) 을 포함하는 논리계를 사용.
  • Walnut 소프트웨어 시스템과 유사한 방식으로 논리식을 오토마타로 변환하는 과정을 시뮬레이션하여, 중간 오토마타의 크기 증가와 런타임 복잡도를 분석.
• 구체적 기법:
  • Myhill-Nerode 정리 적응: DFAO 에 적용하여 구별 가능한 입력 문자열의 수를 세어 최소 상태 수의 하한을 증명.
  • 곱셈 오토마타 (Product Construction) 및 투영 (Projection): 관계식 (예: $n[x]_k + c = [z]_k$) 을 인식하는 오토마타를 구성하기 위해 기존 오토마타를 결합하고 불필요한 변수를 제거하는 과정 분석.

3. 주요 기여 및 결과

A. 상태 복잡도 (State Complexity)

1. 선형 부분열과 부분단어 복잡도의 관계 (Theorem 10):

   • 주요 발견: MSD-First 입력을 가진 $m$-상태 DFAO 로 생성된 자동화 시퀀스 $h$에 대해, 선형 부분열 $(h(ni+c))$을 생성하는 DFAO 의 상태 수는 내부 시퀀스 $h'$의 부분단어 복잡도와 직접적인 관계가 있음을 증명했습니다.
   • 결과:
     • $c < n$인 경우: 최대 $\rho_{h'}(n)$개의 상태로 생성 가능.
     • $c \ge n$인 경우: 최대 $\rho_{h'}(c+1)$개의 상태로 생성 가능.
   • 의미: 이는 Zantema 와 Bosma 가 제기한 MSD-First 입력에 대한 상한 문제 (Open Question) 를 해결한 것으로, 상태 복잡도가 시퀀스의 구조적 복잡도 (부분단어 수) 에 의해 결정됨을 보여줍니다.

2. Thue-Morse 시퀀스 적용 (Theorem 15, Corollary 18):

   • Thue-Morse 시퀀스 $t$의 선형 부분열 $(t(ni))$에 대해, 최소 DFAO 의 상태 수가 $\rho_t(n/\nu_2(n))$임을 정확히 계산했습니다. 여기서 $\nu_2(n)$은 $n$을 나누는 2 의 최대 거듭제곱입니다.
   • 이를 통해 $n$에 따른 상태 수의 정확한 공식을 유도했습니다.

3. 시프트 (Shift) 된 시퀀스의 복잡도:

   • $(h(i+c))$를 생성하는 DFAO 의 상태 복잡도에 대해, Thue-Morse 시퀀스의 경우 $c^{0.694}$보다 큰 하한을 가짐을 증명했습니다 (Theorem 21).
   • 또한, $P_2(i)$ (2 의 거듭제곱일 때 1, 아니면 0) 와 같은 특정 시퀀스는 $O(\log c)$의 상태 복잡도를 가짐을 보였습니다.

4. LSD-First vs MSD-First 비교:

   • LSD-First 입력의 경우 $(h(i+1))$을 생성하는 DFAO 의 상태 수가 $2m-1$까지 증가할 수 있음을 보였습니다 (Theorem 8).
   • MSD-First 입력의 경우 $(h(i+j))$와 같은 2 차원 시퀀스를 생성할 때 $O(m^2)$ 상태가 필요함을 증명했습니다 (Theorem 9).

B. 런타임 복잡도 (Runtime Complexity)

• Büchi 산술을 통한 오토마타 구성 시간 분석 (Section 5):
  • 상수 $c$에 대한 관계식 $[x]_k = c$를 인식하는 오토마타 구성 시간은 $O((\log^2 c)(\log \log c))$임을 보였습니다 (Theorem 24).
  • 선형 관계 $n[x]_k + c = [z]_k$를 인식하는 오토마타 구성 시간은 $O(\log^2 c \log \log c + n \log^2 n + n \log c \log(n \log c))$임을 증명했습니다 (Theorem 28).
  • 자동화 시퀀스 $(h(ni+c))$를 생성하는 DFAO 구성 시간은 $O(m^2(n+c) \log(m^2(n+c)))$ 항이 지배적임을 보였습니다 (Theorem 29).
  • 이는 실제 도구 (Walnut 등) 에서 오토마타를 생성할 때 발생할 수 있는 중간 오토마타의 크기 증가와 계산 비용을 정량화한 것입니다.

4. 의의 및 결론

• 이론적 기여: 자동화 시퀀스의 선형 부분열에 대한 상태 복잡도 문제를 해결하고, 이를 시퀀스의 부분단어 복잡도와 연결하는 새로운 관계를 제시했습니다. 특히 MSD-First 입력에 대한 Zantema 와 Bosma 의 미해결 문제를 해결했습니다.
• 실용적 기여: Büchi 산술 기반의 자동화 생성 도구 (예: Walnut) 를 사용할 때, 입력 매개변수 ($n, c$) 와 시퀀스 크기 ($m$) 에 따라 오토마타 생성에 소요되는 시간과 메모리 (상태 수) 를 예측할 수 있는 이론적 기준을 마련했습니다.
• 향후 과제:
  • Thue-Morse 시퀀스의 시프트된 부분열 $(t(i+c))$에 대한 정확한 상태 수 공식을 찾는 것 (Open Problem 2).
  • 두 위치에서 시작하는 부분열의 동일성을 판별하는 오토마타 $M'$의 상태 복잡도 하한 및 상한을 찾는 것 (Open Problem 3).
  • 다른 수 체계 (numeration systems) 로의 확장 연구.

이 논문은 자동화 이론과 조합론적 단어 이론 (combinatorics on words) 의 교차점에서, 시퀀스 변환의 계산적 복잡성을 체계적으로 규명한 중요한 연구로 평가됩니다.