Ordered Monoids: Languages and Relations
- Speaker: Dr. Szabolcs Mikulas, Department of Computer Science and Information Systems, Birkbeck, University of London
- Date: Wednesday, 11 May 2016 from 16:00 to 17:00
- Location: Room 151, Auxiliary building
Kleene algebras provide an algebraic treatment of regular expressions (REs).
Language Kleene Algebras (LKAs) interpret REs as (regular) languages and
Relational Kleene Algebras (RKAs) interpret REs as binary relations.
The traditional similarity type consists of concatenation/relation composition,
union, Kleene star/reflexive-transitive closure, and the two interpretations
in this case are equivalent: the equational theories of LKAs and RKAs coincide,
i.e., the same equations between REs are valid in the language and relational
In this talk we look at the situation when we expand the similarity type.
In particular, we include intersection into the similarity type and look at
the differences between language and relational interpretations.