Succinctness and tractability of closure operator representations

From International Center for Computational Logic

Toggle side column

Succinctness and tractability of closure operator representations

Sebastian RudolphSebastian Rudolph
Succinctness and tractability of closure operator representations


Sebastian Rudolph
Succinctness and tractability of closure operator representations
Theoretical Computer Science, 658, Part B:327 - 345, January 2017
  • KurzfassungAbstract
    It is widely known that closure operators on finite sets can be represented by sets of implications (also known as inclusion dependencies) as well as by formal contexts. In this article, we consider these two representation types, as well as generalizations of them: extended implication sets and context families. We discuss the mutual succinctness of these four representations and the tractability of certain operations used to compare and modify closure operators.
  • Forschungsgruppe:Research Group: Computational Logic
@article{R2017,
  author  = {Sebastian Rudolph},
  title   = {Succinctness and tractability of closure operator representations},
  journal = {Theoretical Computer Science},
  volume  = {658, Part B},
  year    = {2017},
  month   = {January},
  pages   = {327 - 345},
  doi     = {10.1016/j.tcs.2015.12.028}
}