这篇论文提出了位置图框架，用图结构建模离散token的空间关系，并证明了模式发现是NP完全问题，适合对图推理或文档分析感兴趣的研究者。
本文提出位置图（position graphs），一种基于位置空间形式化的图推理框架。该框架使用两个严格偏序关系（分别表示水平和垂直对齐与优先）来建模离散标记的相对位置。与通用定性空间演算不同，位置图受到链条件和兼容性约束，重点聚焦行与列。文章提供了位置图一致性的充要条件，并证明在该类图上诱导子图同构问题（用于结构模式发现）是NP完全的。该工作源于文档处理，但独立于具体提取技术，专注位置约束的数学性质。
Position Spaces and Graphs
In this paper, we introduce position graphs, a graph-based reasoning framework based on the formalization of position spaces. This framework utilizes two strict partial orders, representing horizontal and vertical alignment and precedence, to model the relative positions of discrete tokens. Unlike general qualitative spatial calculi, position graphs are constrained by a chain condition and compatibility requirements that focus on rows and columns. We provide a comprehensive theoretical analysis of this representation, beginning with a characterization of graph consistency. Conditions to ensure the consistency of position graphs are established. Furthermore, we investigate the computational complexity of structural pattern discovery, modeled as the induced subgraph isomorphism problem. We demonstrate that this problem remains NP-complete even within the restricted class of position graphs. While initially motivated by document processing, this work focuses on the underlying mathematical properties and algebraic consistency of position-based constraints, providing a formal logical layer that is independent of specific data extraction techniques.