"On the Effectiveness of Logic in Algorithmic Graph Theory and Temporal Reasoning"

The interaction between logic and graph theory has had an important impact on applications in computer science, from database query optimization to temporal reasoning and verification. This has been especially true for identifying tractable cases of their relevant constraint satisfaction problems and developing efficient algorithms.

Logic and graph theory form the basis of a fascinating interplay between combinatorial structures and their algorithmic properties. Some of the most important examples of this are relations between logic, hypergraphs and constraint satisfaction problems, graph width parameters, and connections with monadic second-order logic.

In this talk, we will explore a number of themes in which logic and algorithmic graph theory have influenced each other, with a focus on their applications in temporal reasoning.

Bio: Martin Charles Golumbic is an emeritus professor of computer science at the University of Haifa and founder of the Caesarea Edmond Benjamin de Rothschild Institute for Interdisciplinary Applications of Computer Science. He received his Ph.D. degree in mathematics from Columbia University in 1975, under the direction of Samuel Eilenberg, and is the founding Editor-in-Chief of the journal Annals of Mathematics and Artificial Intelligence. His authored books include Algorithmic Graph Theory and Perfect Graphs, Tolerance Graphs (with Ann Trenk), Fighting Terror Online: The Convergence of Security, Technology, and the Law, and The Zeroth Book of Graph Theory: An Annotated Translation of Les Réseaux (ou Graphes) by André Sainte-Laguë. He is a foundation fellow of the Institute of Combinatorics and its Applications, a fellow of the European Artificial Intelligence society EurAI, and a member of the Academia Europaea, honoris causa.