Membership Constraints in Formal Concept Analysis

Sebastian RudolphSebastian Rudolph, Christian SacareaChristian Sacarea, Diana TroancăDiana Troancă

ISBN: 978-1-57735-738-4
Download
Slides

Sebastian Rudolph, Christian Sacarea, Diana Troancă
Membership Constraints in Formal Concept Analysis
In Qiang Yang, Michael Wooldridge, eds., Proc. 24th International Joint Conference on Artificial Intelligence (IJCAI'15), 3186-3192, July 2015. AAAI Press

Details
Bibtex

KurzfassungAbstract
Formal Concept Analysis (FCA) is a prominent field of applied mathematics using object-attribute relationships to define formal concepts — groups of objects with common attributes — which can be ordered into conceptual hierarchies, so-called concept lattices. We consider the problem of satisfiability of membership constraints, i.e., to determine if a formal concept exists whose object and attribute set include certain elements and exclude others. We analyze the computational complexity of this problem in general and for restricted forms of membership constraints. We perform the same analysis for generalizations of FCA to incidence structures of arity three (objects, attributes and conditions) and higher. We present a generic answer set programming (ASP) encoding of the membership constraint satisfaction problem, which allows for deploying available highly optimized ASP tools for its solution. Finally, we discuss the importance of membership constraints in the context of navigational approaches to data analysis.
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@inproceedings{RST2015,
  author    = {Sebastian Rudolph and Christian Sacarea and Diana Troanc{\u{a}}},
  title     = {Membership Constraints in Formal Concept Analysis},
  editor    = {Qiang Yang and Michael Wooldridge},
  booktitle = {Proc. 24th International Joint Conference on Artificial
               Intelligence (IJCAI'15)},
  publisher = {AAAI Press},
  year      = {2015},
  month     = {July},
  pages     = {3186-3192}
}