An Algebra of Modular Systems

VCLA and WPI will host a talk by Evgenia Ternovska on March 3, 2016.

ABSTRACT

I will describe a project aiming at developing formal foundations of reasoning about modular systems. The basis for integration of different formalisms is the classic model theory. Each atomic module is a class of structures. It can represent an agent or a business enterprise, and can be given, e.g., by a set of constraints in a constraint formalism that has an associated solver. Atomic modules are combined using the same algebraic operations as in Codd's relational algebra that is in the foundation of database management systems, and we also add recursion. Just as Codd's algebra, our algebra has a natural counterpart in logic. Since problem solving often involves finding solutions for given inputs, we add a direction of information propagation to the modules. Our algebra with information flow is interpreted over a transition system and gives rise to a modal temporal logic. The well-known Propositional Dynamic Logic is a fragment of the algebra with information flow. I will show how to use the algebra for a high-level encoding of problem solving on graphs using Dynamic Programming on tree decompositions, and demonstrate that situation calculus with the cognitive robotics language Golog is an axiomatic representation of a rich fragment of the algebra. If there is time, I will explain algorithms for finding solutions to modular systems. ---------------------------------------------------------------------------------------------------------------------------------------------------------- Bio: Evgenia (Eugenia) Ternovska is an associate professor at Simon Fraser University, Vancouver, Canada. She obtained her PhD under the supervision of Ray Reiter at the University of Toronto in 2002. Her research interests are in Knowledge Representation and Reasoning, in applications of Logic to Computer Science.