TY - JOUR

T1 - Ordered direct implicational basis of a finite closure system

AU - Adaricheva, K.

AU - Nation, J. B.

AU - Rand, R.

N1 - Funding Information:
We are grateful to several people who read the draft of this paper at different stages of its preparation and made valuable comments: György Turán, Vincent Duquenne, Marina Langlois, Ralph Freese, Marcel Wild and Karell Bertet, also students of Yeshiva College Joshua Blumenkopf and Jeremy Jaffe. Major advancements of this paper were done during the first author’s visits to University of Hawai’i in 2010–2011, supported by the AWM-NSF Mentor Travel grant N0839954 . The welcoming atmosphere at the Department of Mathematics at UofH is greatly appreciated. We thank our anonymous referees for making the numerous comments, pointing to a few references and fixing some of our omissions.

PY - 2013

Y1 - 2013

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

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

KW - Canonical basis

KW - Closure operator

KW - Direct basis

KW - Forward chaining

KW - Horn Boolean function

KW - Horn formula

KW - Lattice of closed sets

KW - Linclosure

KW - System of implications

UR - http://www.scopus.com/inward/record.url?scp=84875440265&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84875440265&partnerID=8YFLogxK

U2 - 10.1016/j.dam.2012.08.031

DO - 10.1016/j.dam.2012.08.031

M3 - Article

AN - SCOPUS:84875440265

VL - 161

SP - 707

EP - 723

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 6

ER -