Research Seminar - August 20, 2004

Algebras of Relations

Time: 11am Friday 20 August

Computer Science & Software Engineering

Seminar Room 1.24

Speaker:
Dr Szabolcs Mikulas

Computer Science Department Birkbeck College,

University of London

Abstract:

Algebras of relations have been successfully applied in various branches of computer science. Examples include cylindric algebras in relational databases, Kleene algebras in software and hardware verification, sequential and fork algebras
in software specification.

In this talk, we will concentrate on the computational behavior of algebras of binary relations. Traditional versions like Tarski's (representable) relation algebras have some undesirable features, e.g., undecidable equational theory, non-finite axiomatizability. We will look at two techniques for obtaining well-behaved versions. Relativization amounts to including non-standard models as well, while taking reducts restricts the language without changing the meaning of the operations. In general, relativization yields decidable and finitely axiomatizable versions, but their applications are limited because of the non-standard semantics. Taking reducts seems a more fruitful approach, since the resulting algebras are often decidable while retaining enough expressive power for applications (e.g., access control in computer security, situation theory, language theory).

Brief Bio:
Dr Szabolcs Mikulas obtained his PhD at the University of Amsterdam (UvA) in Mathematical Logic. He worked at King's College London from 1996, as a research fellow, on the EPSRC projects "Relation algebras of action and indeterminacy" and "Efficient systems of dynamic interaction". Early in 2000 he took up a research fellow post at Birkbeck College and worked on the EPSRC research project "Formalisation and Optimisation of Active Databases" until he was appointed as a lecturer.Dr Mikulas is visiting CSSE for one month and working with Mark Reynolds and Tim French on combinations of temporal and epistemic logic for reasoning about distributed reactive systems. He also does research in more theoretical algebraic approaches to logic which nevertheless have helped identify restricted versions of logics which are more amenable computationally.