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

talk announcement March 3, 2009 - Research seminar @ KBS -Korrektur!



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

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

Speaker: Mantas Simkus

Title: Bidirectional Answer Set Programs with Function Symbols

Abstract:
Current Answer Set Programming (ASP) solvers largely build on Datalog, 
which, unlike general logic programming, lacks function symbols. This 
limitation makes ASP decidable, but greatly complicates the modeling of 
indefinite time, recursive data structures (e.g., lists), and infinite 
processes and objects in general.  Recent research thus aims at finding 
decidable fragments of ASP with function symbols and studying their
complexity. We identify _bidirectional_ ASP programs as an expressive, but 
yet decidable, language that is useful, e.g., for reasoning about actions 
involving both the future and the past. We tightly characterize the
computational complexity of bidirectional programs and some of their 
subclasses, addressing the main reasoning tasks. Our results also show 
that the recently introduced FDNC programs can be extended by _inverse 
rules_ while retaining decidability, but computational costs are 
unavoidably higher.

Keywords: Logic Programming, Nonmonotonic Reasoning, Computational
Complexity.