Supratik Chakraborty is Bajaj Group Chair Professor in the Department of Computer Science and Engineering at IIT Bombay. His research interests include applications of formal methods to the  verification, synthesis and analysis of complex systems, including hardware, software and machine-learning enabled systems.  He also works on constrained sampling and counting and their applications, and on automata theory and logic. Supratik is a Distinguished Member of ACM, a Fellow of Indian National Academy of Engineering and a recipient of the Distinguished Alumnus Award of IIT Kharagpur.

AG 1, AG 2, AG 3, INET, AG 4, AG 5, D6, SWS, RG1, MMCI   Info

AG Audience

English

60 Minutes

Kaiserslautern

Given a sentence $\forall X \exists Y \varphi(X, Y)$ in a first-order theory, it is well-known that there exists a function $F(X)$ for $Y$ in $\varphi$ such that $\exists Y \varphi(X, Y)\leftrightarrow \varphi(X, F(X))$ holds for all values of the universal variables X. Such a function is also called a Skolem function, in honour of Thoralf Skolem who first made us of this in proving what are now known as the Lowenheim-Skolem theorems. The existence of a Skolem function for a given formula is technically analogous to the Axiom of Choice -- it doesn't give us any any hint about how to compute the function, although we know such a function exists. Nevertheless, since Skolem functions are often very useful in practical applications (like finding a strategy for a reactive controller), we investigate when is it possible to algorithmically construct a Turing machine that computes a Skolem function for a given first-order formula. We show that under fairly relaxed conditions, this cannot be done. Does this mean the end of the road for automatic synthesis of Skolem functions? Fortunately, no. We show model-theoretic necessary and sufficient condition for the existence and algorithmic synthesizability of Turing machines implementing Skolem functions. We show that several useful first-order theories satisfy these conditions, and hence admit algorithms that can synthesize Turing machines implementing Skolem functions. We conclude by presenting several open problems in this area.

Susanne Girard

+49 631 9303 9605

--email hidden

Yes

Saarbrücken

E1 5

029

passcode not visible

logged in users only