Skew Heaps 및 Leftist Heaps의 자동화된 분할 상환 분석 (확장 버전)

요약

본 연구는 Skew Heaps와 Leftist Heaps와 같은 데이터 구조에 대해 자동화된 분할 상환 분석(amortized analysis)을 수행하는 새로운 타입 추론 기반 접근 방식을 제안합니다. 기존 ATLAS 시스템을 확장하여 범용 타입 시스템을 도입함으로써, 하드코딩된 방식 대신 임의의 포텐셜 함수를 사용할 수 있도록 구현하였으며 Haskell을 통해 모듈식으로 구현되었습니다.

핵심 포인트

• Skew Heaps 및 Leftist Heaps를 위한 자동화된 분할 상환 자원 분석 방법론 개발
• 범용 타입 시스템 도입을 통해 임의의 클래스 형태 포텐셜 함수 사용 가능
• 경로 민감 추론(path-sensitive reasoning) 및 데이터 구조 불변량 분석 기능 강화
• Haskell을 이용한 모듈식 구현 및 기존 ATLAS 시스템의 한계 극복