Trees in Coalgebra from Generalized Reachability

문제 정의
본 논문은 코알제브라(coalgebra)로 모델링된 상태 기반 시스템의 근본적인 구조적 속성을 다룬다. 모든 상태가 초기 상태로부터 접근 가능하다는 개념인 '도달 가능성(reachability)'은 보편 성질(진부분 코알제브라의 부재)과 반복적 구성(후속 상태들의 합집합)을 통해 코알제브라적으로 잘 규명되어 왔으나, '트리 구조(tree structure)'에 대한 상응하는 코알제브라적 특징 규명은 부족한 상태였다. 구체적으로, 저자들은 모든 상태가 초기 상태로부터 유일한 경로를 통해 도달 가능하다는 그래프 이론의 직관적인 개념을 일반화하여, 어떤 코알제브라가 "트리"인지 정의하고자 한다. 여기서의 과제는 전이가 부분적이거나, 비결정론적이거나, 혹은 공유(sharing)를 포함할 수 있는 시스템을 다루면서, 모노모피즘(monomorphism)을 보존하지 않는 함수자(예: bag functor)를 포함한 광범위한 클래스에 대해 작동하는 특징을 제공하는 것이다.

방법론
저자들은 인수 분해 시스템(factorization systems)과 코알제브라 이론에 기반한 범주론적 접근 방식을 채택한다. 이들의 방법론은 세 가지 주요 단계로 진행된다:

1. 최소성의 일반화: 저자들은 범주에서의 "최소성(minimality)" 개념을 먼저 일반화한다. 최소 객체가 진부분 대상(proper subobject)을 갖지 않는다(사상이 동형 사상이어야 함)는 고전적 정의를 넘어, $M$-최소성($M$-minimality) (정의 4.1)을 도입한다. 어떤 대상이 $M$-최소하다는 것은 $M$으로부터 해당 대상으로의 모든 사상이 *분할 에피모피즘(split epimorphism)*임을 의미한다. 이러한 일반화를 통해 $M$은 모노모피즘뿐만 아니라 모든 사상의 클래스가 될 수 있다.
2. 투영성과 도달 가능성의 연결: 저자들은 이 일반화된 최소성과 $M$-투영성($M$-projectivity) (정리 4.7) 사이의 연결 고리를 확립한다. 이후 이 이론을 점이 있는 코알제브라(pointed coalgebra) 범주에 적용하여 일반화된 도달 가능성(generalized reachability) (정의 5.1)을 정의한다. 코알제브라가 $M$-도달 가능하다는 것은 모든 점이 있는 $M$-부분 코알제브라가 분할 에피모피즘이라는 것을 의미한다.
3. 정밀한 사상을 통한 반복적 구성: 도달 가능하거나 트리로 풀려난(unravelled) 버전의 코알제브라를 구성하기 위해, 저자들은 정밀한 사상(precise morphisms) (정의 3.1)을 활용한다. 공유를 피하기 위해 모노모피즘에 의존하는 "최소 상계(least bounds, bases)"와 달리, 정밀한 사상은 공역의 원소들이 사상의 정의에 정확히 한 번씩만 사용되도록 보장한다. 저자들은 해석적 함수자(analytic functors)에 대해 정밀한 인수 분해가 존재하며, 모노모피즘으로 제한될 경우 최소 상계와 일치함을 증명한다 (명제 3.27, 따름정리 3.22).

핵심 기여
본 논문은 도달 가능성의 이중적 특징 규명과 대칭을 이루는, 코알제브라가 트리인지 여부에 대한 두 가지 동등한 특징 규명을 제공한다:

• 보편 성질 (트리 정의): 점이 있는 코알제브라가 **트리(tree)**라는 것은 진부분 *풀림(unravelings)*을 갖지 않음을 의미한다. 형식적으로, 코알제브라가 트리라는 것은 모든 풀림(그것으로의 점이 있는 코알제브라 준동형 사상)이 분할 에피모피즘임을 의미한다 (정의 6.1). 이는 $M$을 모노모피즘 클래스가 아닌 모든 사상의 클래스로 허용함으로써 도달 가능성 조건을 일반화한다.
• 반복적 구성 (트리 언래벌링): 저자들은 임의의 점이 있는 코알제브라를 트리로 변환하는 반복적 구성(구성 6.23)을 제시한다. 이 구성은 각 레벨을 전이 사상의 정밀한 인수 분해를 통해 계산하는 레벨들의 코프로덕트(coproduct)를 취하는 과정을 포함한다. 결과물인 코알제브라는 원래 시스템의 "트리 언래벌링(tree unravelling)"이 된다.
• 통합: 저자들은 도달 가능성과 트리 성질 모두가 동일한 일반화된 개념인 $M$-최소성의 사례임을 보여준다. 도달 가능성은 $M$이 모노모피즘 클래스인 경우에 해당하며, 트리 성질은 $M$이 모든 사상의 클래스인 경우에 해당한다.

결과
저자들은 다양한 표준 예시들에 대해 기대되는 트리의 개념을 회복함으로써 이론을 검증한다:

• 부분 결정적 오토마타(Partial Deterministic Automata): 트리 언래벌링은 "정의된 입력들의 코알제브라"에 대응한다 (여기서 상태는 그 상태로 이끄는 유일한 단어들과 동일시된다) (레마 6.11, 따름정리 6.12).
• 멀티그래프 (Bag Functor): 멀티그래프를 모델링하는 bag functor 상의 코알제브라에 대해, 트리 언래벌링은 "뿌리로부터의 경로들의 코알제브라"이다. bag-코알제브라가 트리이기 위한 필요충분조건은 루트에서 모든 정점으로 가는 유일한 경로가 존재하는 것이다 (정리 6.18).
• 파워셋 함수자 (Powerset Functor): 본 논문은 한계를 지적한다. 단순 그래프를 모델링하는 파워셋 함수자의 경우, 이 특징 규명은 거의 모든 코알제브라가 트리가 아님을 시사한다. 이는 파워셋 함수자가 "복제(copying)"(예: $\{x\} = \{x, x\}$)를 허용하여, 공집합이 아닌 집합에 대해 정밀한 사상의 존재를 방해하기 때문이다 (명제 3.3). 결과적으로, 이 설정에서의 트리는 자명하다 (단일 정점, 엣지 없음).

의의
본 논문은 도달 가능한 코알제브라 이론을 트리 구조로 확장하는 통합된 이론적 프레임워크를 제공함으로써 그 의의를 주장한다.

• 일반화: 모노(mono)라는 적절한 인수 분해 시스템에서 임의의 인수 분해 시스템으로 도달 가능성 개념을 성공적으로 일반화하여, 사상이 반드시 단사(injective)일 필요가 없는 트리 구조를 다룰 수 있게 하였다.
• 해석적 함수자: 반복적 구성은 다양한 계산 시스템의 중심이 되는 다항 함수자(polynomial functors) 및 bag 함수자를 포함하는 광범리한 클래스인 **해석적 집합 함수자(analytic set functors)**에 대해 작동함이 입증되었다 (따름정리 3.22).
• 개념적 명확성: 최소성을 투영성과 연결하고 보편적 및 반복적 특징 규명을 모두 제공함으로써, 상태 기반 시스템에서 트리와 유사한 동작을 이해하기 위한 견고한 범주론적 토대를 제공하며, 이를 파워셋 함수자에 의해 모델링되는 시스템의 동작과 명확히 구분한다.

저자들은 본 연구가 컨퍼런스 논문의 확장판이며, 특히 최소성과 투영성 사이의 연결 관계와 정밀한 인수 분해에 대한 상세한 분석을 더하여 완전한 증명과 추가적인 일반화를 제공한다고 밝히고 있다.