?
Atomic Patterns for Efficient Computation with Pattern Structures
Pattern Structures is a framework in FCA allowing objects to have complex descriptions, only requiring that the set of descriptions forms a complete meet-semi-lattice. However, some particular descrip tions or patterns, such as subgraphs and subsequences, do not necessarily ensure that every pair of descriptions has a unique infimum and ask for additional operations, e.g., anti-chain completion. Moreover, meet-based approaches struggle to generate non-trivial implications for complex data since, in general, they only output closed descriptions. For overcoming such limitations, we introduce in this paper an alternative view of pat tern structures based on the join operation and the so-called “atomic patterns”. Such atomic patterns correspond to join-irreducible descrip tions in the join-semi-lattice of all possible descriptions. They enable an efficient traversal of the description space and the computation of closures, minimal generators, pseudo-intents, implications among others, while showing very good computational performance.