위치 공간과 그래프

본 논문에서는 위치 공간 (position spaces)의 형식화에 기반한 그래프 기반 추론 프레임워크인 위치 그래프 (position graphs)를 소개합니다. 이 프레임워크는 수평 및 수직 정렬과 선후 관계를 나타내는 두 개의 엄격한 부분 순서 (strict partial orders)를 활용하여 이산 토큰 (discrete tokens)의 상대적 위치를 모델링합니다. 일반적인 정성적 공간 계산법 (qualitative spatial calculi)과 달리, 위치 그래프는 행과 열에 집중하는 체인 조건 (chain condition) 및 호환성 요구 사항 (compatibility requirements)에 의해 제약됩니다. 우리는 그래프 일관성 (graph consistency)의 특성 정의를 시작으로, 이 표현 방식에 대한 포괄적인 이론적 분석을 제공합니다. 위치 그래프의 일관성을 보장하기 위한 조건들이 수립됩니다. 나아가, 우리는 유도된 부분 그래프 동형 문제 (induced subgraph isomorphism problem)로 모델링된 구조적 패턴 발견의 계산 복잡도 (computational complexity)를 조사합니다. 우리는 이 문제가 제한된 클래스인 위치 그래프 내에서도 NP-완전 (NP-complete) 상태로 남아 있음을 입증합니다. 초기 동기는 문서 처리 (document processing)였으나, 본 연구는 위치 기반 제약 조건의 근본적인 수학적 속성과 대수적 일관성 (algebraic consistency)에 초점을 맞추어, 특정 데이터 추출 기술과는 독립적인 공식적인 논리 계층을 제공합니다.