Modular Systems: Semantics, Logic, Algorithms, Complexity - Eugenia Ternovska (Simon Fraser Univ)
With the development of declarative programming, more and more programs
that solve practical problems are available online. Ideally, we should be able
to reuse them by first finding suitable components on the web, and then combining
them, in order to solve new more complex problems.
The main challenge is that the programs may be written in different languages
(even legacy languages), and rely on different solving technologies.
Our goal is to develop foundations for combining such programs (or agents)
and, eventually, provide practical algorithms for finding solutions.
Towards this goal, we developed a framework of Modular Systems (MS),
where individual modules can be specified in any language that admits model-theoretic semantics. For example, modules can be specified in first-order logic,
Answer Set Programming, Integer Liner Programming, sometimes even in C or Java.
In the MS framework, such modules are combined using the
algebraic operations of sequence, union, loop, projection, etc.
In this talk, I will introduce the algebra of MSs and present its
model-theoretic, inferential and structural operational semantics (SOS).
I will define a multi-logic logic of MSs, which is a logic counterpart
of the algebra. This logic can be called the Logic of Information Flow
because the direction of information propagation from agent to agent
is always clear. I will describe a high-level algorithm for solving MSs.
The algorithm was inspired by Satisfiability Modular Theory (SMT) solvers.
Finally, I will discuss the complexity of the formalism and
the descriptive complexity of modular systems, as a function
of expressiveness of individual modules. Such analysis is important because
we want our formalism to be expressive enough to represent all problems
in a class of interest, but we don't want it be too expressive
to construct practical solvers.
If there is time, I will explain an extension of MSs with preferences.
Joint work with Shahab Tasharrofi.
bio: Eugenia Ternovska is an Associate Professor at Simon
Fraser University, Vancouver, Canada. She received her PhD
in Computer Science at the University of Toronto, and
diploma at Moscow State University. Her research interests
are in Artificial Intelligence and Computational Logic.