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
Abstract:
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.