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 descriptions 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., antichain 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 pattern structures based on the join operation and the so-called “atomic patterns”. Such atomic patterns correspond to join-irreducible descriptions 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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Atomic Patterns for Efficient Computation with Pattern Structures

  • Egor Dudyrev,
  • Miguel Couceiro,
  • Mehdi Kaytoue,
  • Sergei O. Kuznetsov,
  • Amedeo Napoli

摘要

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 descriptions 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., antichain 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 pattern structures based on the join operation and the so-called “atomic patterns”. Such atomic patterns correspond to join-irreducible descriptions 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.