CFL/Dyck Reachability: An Algorithmic Perspective
COM1 Level 3
MR1, COM1-03-19 or via Zoom (Hybrid)
Abstract:
CFL/Dyck reachability is a simple graph-theoretic notion of language-based graph reachability, that has served as the algorithmic formulation of many problems in diverse domains, such as graph databases and program static analysis. This talk takes an algorithmic perspective on CFL/Dyck reachability and overviews several recent advances concerning the decidability and complexity of the problem and some it is close variants, as realized in the areas of automata theory and program verification.
Biodata:
Andreas Pavlogiannis is an assistant professor in the Computer Science Department at the University of Aarhus, Denmark. Prior to that, he studied and worked at the University of Patras Greece, University of California Davis USA, Institute of Science and Technology Austria, and Ecole Polytechnique Federale de Lausanne (EPFL) Switzerland.