Hellenic-Romanian Logic and Computation Seminar

http://imar.ro/~diacon/HRLogComp/HRLogicComputSeminar.ht 

Monday 24th of November at 18.00 GR/RO time  

link: https://meet.jit.si/HRLogicComputSeminar

Title: Shadowy institutions

Speaker: Prof. Siddarth Bhaskar 

Abstract: In finite model theory, we are interested in logics which make use of some additional structure (such as a linear ordering of the universe), but whose semantics are invariant with respect to which linear order is chosen. (Such logics capture several important complexity classes.) While these logics generally have badly behaved (undecidable) syntax, there is no in-principle obstruction to doing model theory with them. However, progress is “notoriously difficult” due to lack of logical tools.

After many years of thinking about how to lift (finitary) order-invariance to arbitrary infinite structures, I discovered that institution-independent model theory was exactly the right level of generality to couch the basic definitions and results. I will describe the fundamental object, which I am now calling a “shadow,” and describe how to construct a new institution out of a given one where shadows play the role of signatures. This is still very preliminary work, but it holds the promise that we can make progress in finite model theory and perhaps ultimately computational complexity by developing the model theory of shadowy institutions. 

Bio: Siddharth Bhaskar is an assistant professor in the Department of Mathematics and Computer Science at the University of Southern Denmark. His research focuses on the interaction of logic with foundational aspects of computer science, such as in finite model theory and implicit computational complexity. His interests also extend to broader topics such as mathematical phonology and CS education. He received his PhD in mathematical logic from UCLA in 2015.