June 25th (Thursday) from 14:00 to 16:00
Room 1904 (Presentation Room), 19F, NII
From 14:00
Prof. Thomas Eiter
Technische Universitaet Wien, Austria
Title
"New Results for Horn Cores and Envelopes of Horn Disjunctions"
Abstract
Abstract: Motivated by the fact that deductive inference from
propositional knowledge bases, even in clausal form, is a well-known
coNP-complete problem, Horn cores and Horn envelopes were introduced as
semantic approximations of such knowledge bases that have benign
computational properties, as inference of a clause from a Horn conjunctive
normal form (CNF) is decidable in polynomial time. Roughly, a Horn core of
a Boolean formula is a weakest Horn formula in conjunctive normal form
(Horn CNF) that implies the formula, while a Horn envelope is a strongest
Horn CNF that is implied by the formula.
In this talk, we present a characterization of Horn cores for formulas in
conjunctive normal form (CNF) and, based on it, an algorithm for computing
Horn cores of disjunctions of Horn CNFs that has appealing properties
(e.g., it is polynomial for a bounded disjunction). Furthermore, we show
that recognizing the Horn envelope of a disjunction of two Horn CNFs is
intractable, and that computing a compact Horn CNF for it (that is
irredundant and prime) is not feasible in polynomial total time unless
P=NP; this answers an open problem.
From 15:00
Prof. Alexander Bochman
Holon Institute of Technology, Israel
Title
"A Causal Theory of Abduction"
Abstract
A uniform representation of abductive reasoning is provided
in the logical framework of causal inference relations.
The representation covers in a single framework not only traditional,
'classical' forms of abduction, but also abductive reasoning in diagnosis,
theories of actions and change, and abductive logic programming.