Sam VAN GOOL (Université Paris Cité) will give a talk on
Unification, duality, and de Bruijn graphs
Abstract:
Unification problems in modal and description logics may be usefully studied via Stone duality, following ideas that were first put forward by S. Ghilardi since the 1990s. In this talk, I will focus in particular on the general unifiability problem for the modal logic of deterministic Kripke frames; or, in algebraic terms, the equational theory of free Boolean algebras equipped with an endomorphism and an arbitrary number of constants. Through an application of duality, we show that this problem is effectively equivalent to a problem about the existence of homomorphisms out of a sequence of graphs, called de Bruijn graphs. These graphs can also be seen as automata with a bounded memory, and our duality result thus establishes a new connection between unifiability problems and finite-word-automata. Finally, we give a solution to the de Bruijn graph problem, thus also deciding unifiability for deterministic modal logic. We conjecture that a similar method could lead to unification results for other non-transitive logics. This is joint work with J. Marti and M. Sweering.