Ordinal Motifs in Lattices
This work addresses the challenge of understanding complex lattice structures in formal concept analysis, which is incremental as it builds on existing scale-measure techniques.
The paper tackles the problem of decomposing large, high-dimensional lattices for relational and ontological knowledge analysis by proposing ordinal motifs as analytical units, showing that the underlying decision problems are NP-complete and providing incremental identification methods to save computational effort.
Lattices are a commonly used structure for the representation and analysis of relational and ontological knowledge. In particular, the analysis of these requires a decomposition of a large and high-dimensional lattice into a set of understandably large parts. With the present work we propose /ordinal motifs/ as analytical units of meaning. We study these ordinal substructures (or standard scales) through (full) scale-measures of formal contexts from the field of formal concept analysis. We show that the underlying decision problems are NP-complete and provide results on how one can incrementally identify ordinal motifs to save computational effort. Accompanying our theoretical results, we demonstrate how ordinal motifs can be leveraged to retrieve basic meaning from a medium sized ordinal data set.