Open for all UnRAVeL Members: Research Seminar by RTG QuantLA: Robin Hirsch: Relation algebra, games, representations, constraints

Tuesday, February 02, 2021, 1:00pm

Location: Online Session

Speaker: Robin Hirsch



An introduction to games for solving constraints.  I will mainly focus on binary constraints and the binary constraint satisfaction problem. We devise games to test consistency of binary constraints. We also introduce algebras for binary constraints — Relation Algebra — and use the game to test the representability of an algebra, as a concrete algebra of binary relations.  These games can be used to find a recursively enumerable axiomatisation of the representation class, and can also be used to prove that a finite axiomatisation is not possible.