Ordered direct implication basis of a finite closure system
Loading...
Date
2012
Authors
Adaricheva, Kira
Nation, J.B.
Rand, R.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Closure system on a nite set is a unifying concept in logic programming,
relational data bases and knowledge systems. It can also be presented
in the terms of nite lattices, and the tools of economic description of a
nite lattice have long existed in 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
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
Description
Keywords
Research Subject Categories::MATHEMATICS, finite closure system
Citation
Adaricheva Kira, Nation J.B., Rand R.; 2012; Ordered direct implication basis of a finite closure system; arXiv.org