[Date Prev][Date Next][Date Index]

talk announcement - Research seminar @ KBS



The next session of our research seminar is coming up to which we like to 
invite you:

Date: 	Tuesday, November 18, 2008
Time: 	17:00 s.t.
Place: 	Seminarraum 184/3
       	HE 03 40. 3. Stock, roter Bereich

Speaker: Joerg Puehrer

Title: 	Elimination of Disjunction and Negation in Answer-Set Programs 
	under Hyperequivalence


Abstract:

The study of different notions of equivalence is one of the cornerstones of
current research in answer-set programming. This is mainly motivated by the
needs of program simplification and modular programming, for which ordinary
equivalence is insufficient. A recently introduced equivalence notion in 
this context is hyperequivalence, which includes as special cases strong, 
uniform, and ordinary equivalence. This talk deals with replacing programs by
syntactically simpler ones preserving hyperequivalence. In particular, we
provide necessary and sufficient semantic conditions under which elimination
of disjunction, negation, or both, from programs is possible, preserving
hyperequivalence. Furthermore, complexity results are presented for the tasks
of deciding whether a disjunctive logic program can be replaced by a
hyperequivalent normal, positive, or Horn program, respectively. Moreover,
besides deciding whether a hyperequivalent program of a simpler class exists,
we also provide methods for constructing it.