Ordered direct implicational basis of a finite closure system

Kira Adaricheva, J. B. Nation, Robert Rand

Research output: Contribution to conferencePaper

2 Citations (Scopus)

Abstract

Closure system on a finite set is a unifying concept in logic programming, relational data bases 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 existedin lattice theory.We present this approach by describing the so-called D-basis and introducing the concept of 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 D-basis at the cost of following a prescribed order in which implications will be attended. In particular, this allows us to optimize the forward chaining procedure in logic programming that uses the Horn fragment of propositional logic. It turns out that running the D-basis in one iteration is more efficient than running a shorter, but un-ordered, canonical basis of J. Guigues and V. Duquenne, and examples demonstrate that the canonical basis cannot always be ordered. We show that one can extract the D-basis from any direct unit basis σ in time polynomial of |σ| and it takes only linear time of the size of the D-basis to put it into a proper order.

Original languageEnglish
Publication statusPublished - Dec 1 2012
EventInternational Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 - Fort Lauderdale, FL, United States
Duration: Jan 9 2012Jan 11 2012

Other

OtherInternational Symposium on Artificial Intelligence and Mathematics, ISAIM 2012
CountryUnited States
CityFort Lauderdale, FL
Period1/9/121/11/12

    Fingerprint

ASJC Scopus subject areas

  • Artificial Intelligence
  • Applied Mathematics

Cite this

Adaricheva, K., Nation, J. B., & Rand, R. (2012). Ordered direct implicational basis of a finite closure system. Paper presented at International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012, Fort Lauderdale, FL, United States.