Position Spaces and Graphs
This work provides a formal logical layer for position-based constraints, but its contribution is primarily theoretical and incremental, with no concrete applications or performance numbers.
The paper introduces position graphs, a graph-based framework for modeling relative positions of discrete tokens using two strict partial orders, and provides a theoretical analysis including consistency conditions and NP-completeness of induced subgraph isomorphism. The work focuses on mathematical properties rather than empirical results.
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.