Tata Institute of Fundamental Research
Extension Preservation in the Finite and Prefix Classes of First Order Logic
STCS Seminar
Speaker:
Abhisekh Sankaran (University of Cambridge)
Organiser:
Shibashis Guha
Date:
Tuesday, 22 Feb 2022, 16:00 to 17:00
Venue:
Via Zoom
(Scan to add to calendar)
Abstract:
It is well known that the classic Los-Tarski preservation theorem fails in the finite: there are first order definable classes of finite structures closed under extensions which are not definable in the existential fragment of first order logic. We strengthen this [1] by constructing for every n, first order definable classes of finite structures closed under extensions which are not definable with n quantifier alternations. The classes we construct are definable in the extension of Datalog with negation. This answers negatively an open question posed by Rosen and Weinstein [2].
[1] Anuj Dawar and Abhisekh Sankaran. Extension preservation in the finite and prefix classes of first order logic. Proceedings of the 31st Computer Science Logic (CSL), Ljubljana, Slovenia, January 25 -- 28, 2021, pp. 18:1 -- 18:13.
[2] Eric Rosen and Scott Weinstein. Preservation theorems in finite model theory. In the International Workshop on Logic and Computational Complexity, pages 480âEUR"502. Springer,1994.
Bio: Abhisekh Sankaran is a post-doctoral research associate at the Department of Computer Science and Technology of the University of Cambridge, UK. He works with Prof. Anuj Dawar and has been at Cambridge since September 2018. Prior to that, he was a post-doctoral fellow for a year in the Theoretical Computer Science Wing of the Institute of Mathematical Sciences Chennai. He completed his Ph.D. and also his Bachelors and Masters from the Computer Science department of IIT Bombay. His research interests lie in mathematical logic, particularly classical and finite model theory, and parameterized algorithms, particularly algorithmic metatheorems. For the present seminar, he will be speaking on a classical model theoretic result in the context of finite structures.
| Speaker: | Abhisekh Sankaran (University of Cambridge) |
| Organiser: | Shibashis Guha |
| Date: | Tuesday, 22 Feb 2022, 16:00 to 17:00 |
| Venue: | Via Zoom |
(Scan to add to calendar)
Abstract:
It is well known that the classic Los-Tarski preservation theorem fails in the finite: there are first order definable classes of finite structures closed under extensions which are not definable in the existential fragment of first order logic. We strengthen this [1] by constructing for every n, first order definable classes of finite structures closed under extensions which are not definable with n quantifier alternations. The classes we construct are definable in the extension of Datalog with negation. This answers negatively an open question posed by Rosen and Weinstein [2].
[1] Anuj Dawar and Abhisekh Sankaran. Extension preservation in the finite and prefix classes of first order logic. Proceedings of the 31st Computer Science Logic (CSL), Ljubljana, Slovenia, January 25 -- 28, 2021, pp. 18:1 -- 18:13.
[2] Eric Rosen and Scott Weinstein. Preservation theorems in finite model theory. In the International Workshop on Logic and Computational Complexity, pages 480âEUR"502. Springer,1994.
Bio: Abhisekh Sankaran is a post-doctoral research associate at the Department of Computer Science and Technology of the University of Cambridge, UK. He works with Prof. Anuj Dawar and has been at Cambridge since September 2018. Prior to that, he was a post-doctoral fellow for a year in the Theoretical Computer Science Wing of the Institute of Mathematical Sciences Chennai. He completed his Ph.D. and also his Bachelors and Masters from the Computer Science department of IIT Bombay. His research interests lie in mathematical logic, particularly classical and finite model theory, and parameterized algorithms, particularly algorithmic metatheorems. For the present seminar, he will be speaking on a classical model theoretic result in the context of finite structures.
[1] Anuj Dawar and Abhisekh Sankaran. Extension preservation in the finite and prefix classes of first order logic. Proceedings of the 31st Computer Science Logic (CSL), Ljubljana, Slovenia, January 25 -- 28, 2021, pp. 18:1 -- 18:13.
[2] Eric Rosen and Scott Weinstein. Preservation theorems in finite model theory. In the International Workshop on Logic and Computational Complexity, pages 480âEUR"502. Springer,1994.
Bio: Abhisekh Sankaran is a post-doctoral research associate at the Department of Computer Science and Technology of the University of Cambridge, UK. He works with Prof. Anuj Dawar and has been at Cambridge since September 2018. Prior to that, he was a post-doctoral fellow for a year in the Theoretical Computer Science Wing of the Institute of Mathematical Sciences Chennai. He completed his Ph.D. and also his Bachelors and Masters from the Computer Science department of IIT Bombay. His research interests lie in mathematical logic, particularly classical and finite model theory, and parameterized algorithms, particularly algorithmic metatheorems. For the present seminar, he will be speaking on a classical model theoretic result in the context of finite structures.