Ordered direct implicational basis of a finite closure system

K. Adaricheva, J. B. Nation, R. Rand

Research output: Contribution to journalArticlepeer-review

18 Citations (Scopus)

Abstract

The closure system on a finite set is a unifying concept in logic programming, relational databases and knowledge systems. It can also be presented in the terms of finite lattices, and the tools of economic description of a finite lattice have long existed in lattice theory. We present this approach by defining the D-basis and introducing the concept of an ordered direct basis of an implicational system. A direct basis of a closure operator, or an implicational system, is a set of implications that allows one to compute the closure of an arbitrary set by a single iteration. This property is preserved by the D-basis at the cost of following a prescribed order in which implications will be attended. In particular, using an ordered direct basis allows to optimize the forward chaining procedure in logic programming that uses the Horn fragment of propositional logic. One can extract the D-basis from any direct unit basis Σ in time polynomial in the size s(Σ), and it takes only linear time of the cardinality of the D-basis to put it into a proper order. We produce examples of closure systems on a 6-element set, for which the canonical basis of Duquenne and Guigues is not ordered direct.

Original languageEnglish
Pages (from-to)707-723
Number of pages17
JournalDiscrete Applied Mathematics
Volume161
Issue number6
DOIs
Publication statusPublished - 2013

Keywords

  • Canonical basis
  • Closure operator
  • Direct basis
  • Forward chaining
  • Horn Boolean function
  • Horn formula
  • Lattice of closed sets
  • Linclosure
  • System of implications

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Ordered direct implicational basis of a finite closure system'. Together they form a unique fingerprint.

Cite this