KLAP Seminar Home Page
Fall 2004
This is a weekly seminar which discusses issues related to
the areas of logic and constraint programming, knowledge representation,
and parallel processing.
It is organized by members of the
The Laboratory for Logic, DBs, and Advanced Programming.
KLAP stands for
Knowledge representation, Logic, and Advanced Programming.
The seminar is open to everyone.
Time: Monday, 12 pm (noon)
Location: SH 124
Upcoming Seminar
There will be no more seminars this semester.
Schedule of talks
|
Date | Speaker | Title
|
|---|
| September 27
| Islam Elkabani
| Intensional sets in CLP
|
| October 4
| Yu Pan
| Web Service Choreography Description Language Model
|
| October 11
| Tu Phan
| Ramifications with Incomplete Information
|
| October 18
| Chongbing Liu
| The Foundations of Inductive Logic Programming
|
| October 25
| Hung Viet Le
| The parallelism of stable model computing on Distributed Memory Machines
|
| November 1
| no seminar
|
|
November10,
Wednesday
| Mirek Truszczynski
| Logic programs with abstract constraints
|
| November 15
| Omar Nabil El Khatib
| "On the Existence of Stable Models of Non-Stratified Logic Programs" by Stefania Costantini, 2003
|
| November 22
| no seminar
|
|
| November 29
| Chongbing Liu
| ILP Systems: A Review
|
Previous Seminars
November 29
Chongbing Liu
spoke on
ILP Systems: A Review
(
Talk Slides)
Abstract
This talk reviews the ILP systems and discusses the
issue of parallelizing the ILP learning process.
First we take the view of ILP problem as a search problem
and summarize the main features of the major systems.
Different aspects such as search space, search strategies,
search heuristics and acceptance criteria, are covered
for MIS, FOIL, GOLEM and PROGOL.
Second we take the view of ILP problem as the inversion of
deduction and present a series of systems which are based
directly on the inverse techniques. These systems are
DUCE, CIGOL, GOLEM and PROGOL.
Lastly we touch the problem of parallelizing the ILP.
After a little bit review of the work done on this issue,
I will show my proposal that we need to find a way to
partition and distribute the background knowledge in order
to better realize parallelization.
November 15
Omar Nabil El Khatib
spoke on
On the Existence of Stable Models of Non-stratified Logic Programs
By: Stefania Constantini
Abstract
In this paper we analyze the relationship between cyclic definitions and
consistency in Gelfond- Lifschitz's answer sets semantics (initially
defined as `stable model semantics'). This paper introduces a
fundamental result, which is very relevant for Answer Set programming,
and planning. For the first time since the definition of the stable
model semantics, the class of logic programs for which a stable model
exists is given a syntactic characterization. This condition may have a
practical importance both for defining new algorithms for checking
consistency and computing answer sets, and for improving the existing
systems. The approach of this paper is to introduce a new canonical form
(to which any logic program can be reduced to), to focus the attention
on cyclic dependencies. The technical result is then given in terms of
programs in canonical form (canonical programs), without loss of
generality: the stable models of any general logic program coincide (up
to the language) to those of the corresponding canonical program. The
result is based on identifying the cycles contained in the program,
showing that stable models of the overall program are composed of stable
models of suitable sub-programs, corresponding to the cycles, and on
defining the cycle graph. Each vertex of this graph corresponds to one
cycle, and each edge corresponds to one handle, which is a literal
containing an atom that, occurring in both cycles, actually determines a
connection between them. In fact, the truth value of the handle in the
cycle where it appears as the head of a rule, influences the truth value
of the atoms of the cycle(s) where it occurs in the body. We can
therefore introduce the concept of a handle path, connecting different
cycles. Cycles can be even, if they consist of an even number of rules,
or vice versa they can be odd. Problems for consistency, as it is
well-known, originate in the odd cycles. If for every odd cycle we can
find a handle path with certain properties, then the existence of stable
model is guaranteed. We will show that based on this results new classes
of consistent programs can be defined, and that cycles and cycle graphs
can be generalized to components and component graphs.
November 10
Mirek Truszczynski (University of Kentucky)
spoke on
Logic programs with abstract constraints
Abstract
We will discuss extensions of logic programming with constraints
represented as generalized atoms of the form C(X), where X is a
finite set of atoms and C is an abstract constraint (formally,
a collection of sets of atoms). We focus primarily on monotone
and convex constraints. They include, in particular, weight (or
pseudo-boolean) constraints studied both by the logic programming
and SAT communities. We show that key concepts of the theory of normal
logic programs such as the one-step provability operator, program
completion, semantics of supported and stable models, as well as
several properties of these concepts including complexity results,
and characterizations of strong and uniform equivalence of programs
lift to the case of programs with abstract constraints.
(with contributions by Lengning Liu and Victor Marek)
October 25
Hung Viet Le
spoke on
The parallelism of stable model computing on Distributed Memory Machines
Abstract
In the late 80s, there have been raising interests in stable model semantic
in an effort to provide an understanding of programs with negation. The
stable semantic, proposed by Gelfond and Lifschitz, has the inherent
features that naturally lead to a logic programming system that offers an
interesting alternative to more traditional logic programming styles. The
programmers encode the stable models as the solutions to the constraint
satisfaction problem and use the solver to find the stable models. This
novel paradigm of programming is known as Answer Set Programming (ASP).
However, computing answer sets is computationally expensive. It has been
shown that the problem of deciding whether a program has an answer set is
NP-complete. In the significant ASP programs, the computations of stable
models remains as a big challenging in term of time consuming and limits
the
applicability of real-life ASP applications. In this talk, we will present
our research in parallelization of stable models computing.
October 18
Chongbing Liu
spoke on
The Foundations of Inductive Logic Programming
(
Talk Slides)
Abstract
Inductive Logic Programming (ILP) could be viewed as an application
of logic theory on inductive learning, or as a way of inductive
learning using logic. In this talk, I will present the foundations
of ILP, in terms of first-order logic.
Firstly, I will briefly talk about some very basic logic stuff,
focusing on Herbrand model and resolution based proof procedures.
The specification of the ILP problem using first-order logic and
a general scheme used to solve the ILP problem, will be presented
in the second part of my talk. It shows that the ILP problem is a
problem of searching the ordered clause space for a correct theory,
and specialization and generalization are two key operations needed
by the searching process. In the third part, I will introduce
different orders defined on the clause space without and with
background knowledge, and discuss their properties. Also I will talk
about refinement operators which are used to perform the specialization
and generalization operations during the searching process.
Lastly I may mention some of the existing ILP systems and show
how the foundations I talked are used by them.
October 11
Tu Phan
spoke on
Ramifications with Incomplete Information
Abstract
McCain and Turner propose
a simple fixpoint condition defining the possible next states
after the execution of an action, given specific direct
effects and background knowledge in the form of causal laws.
Implementing this semantics directly in a planner is
inefficient since determining next possible states
according to the fixpoint condition is not easy. Moreover,
the problem becomes harder when the agent does not have complete
information about the world. One of the simplest approaches is
to consider all possible worlds, and then for each of which,
determine all the possible next states according to the fixpoint
condition. This approach, however, is inefficient for implementation
since the number of possible worlds may be very large.
We propose several approximate solutions to the ramification
problem when the agent has incomplete information about
the world. These approximations are proved to be sound (sometimes)
with respect to McCain and Turner's complete semantics. We argue
that they are very efficient for implementation.
October 4
Yu Pan
spoke on
Web Service Choreography Description Language Model
Abstract
A Web service is a software system designed to support interoperable
machine-to-machine interaction over a network. Current standards for web service
related activity include: WSDL, SOAP, and UDDI.While current protocols lack the ability to compose web services in a structured
and
secured manner that is needed badly by future e-business development, W3C is initiating an effort to define a web service composing language that will be use
d to control the message flow between endpoints in a cross-platform and
cross-language manner.
For more information about WSCDL, please refer to the Web Services Choreography
Working Group main page:
http://www.w3c.org/2002/ws/chor/
September 27
Islam Elkabani
spoke on
Intensional Sets in CLP
Abstract
This work proposes a parametric introduction of
intensionally defined sets into any CLP(D) language. The result is a
language CLP({D}), where constraints over sets of elements of D and over
sets of sets of elements, and so on, can be expressed. The semantics of
CLP({D}) is based on the semantics of logic programs with aggregates and the
semantics of CLP over sets. This work investigate the problem of constraint
resolution in CLP({D}) and propose algorithms for constraints
simplification.
KLAP seminar in the Fall 2003.
This page is maintained by
Inna Pivkina
