### 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 language | English |
---|---|

Publication status | Published - Dec 1 2012 |

Event | International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 - Fort Lauderdale, FL, United States Duration: Jan 9 2012 → Jan 11 2012 |

### Other

Other | International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012 |
---|---|

Country | United States |

City | Fort Lauderdale, FL |

Period | 1/9/12 → 1/11/12 |

### Fingerprint

### ASJC Scopus subject areas

- Artificial Intelligence
- Applied Mathematics

### Cite this

*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.