TY - CONF

T1 - Ordered direct implicational basis of a finite closure system

AU - Adaricheva, Kira

AU - Nation, J. B.

AU - Rand, Robert

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.
Copyright:
Copyright 2013 Elsevier B.V., All rights reserved.

PY - 2012

Y1 - 2012

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

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

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

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

M3 - Paper

AN - SCOPUS:84885753092

T2 - International Symposium on Artificial Intelligence and Mathematics, ISAIM 2012

Y2 - 9 January 2012 through 11 January 2012

ER -