Reasoning with coincidence grids—A sequent-based logic and an analysis of complexity

摘要

Information is often represented in tabular format in everyday documents such as balance sheets, sales figures, and so on. Tables represent an interesting point in the spectrum of representation systems between pictures and sentences, since some aspects of tables are sentential or conventional in nature, while others are graphical. In this paper we describe a sequent-based logic for a particular formalized tabular representation system, that of coincidence grids. After presenting this system we will then provide an analysis of the complexity of reasoning with this formalism showing that the problem of deciding whether a coincidence grid can be consistently completed is NP-Complete.