Seminar for Mathematical Logic

PROGRAM

Predavanja na Logičkom seminaru možete uživo pratiti preko linka
https://miteam.mi.sanu.ac.rs/asset/iYxPidYtFqBC9sT7a.
Ukoliko želite i da učestvujete u diskusiji, to možete preko linka
https://miteam.mi.sanu.ac.rs/asset/oaqCm4EyPhHR6kM6N
na kome prethodno treba napraviti nalog, t.j. popuniti registracioni formular koji se pojavi nakon klika.
Neulogovani korisnici mogu pratiti prenos predavanja na ovom linku (ali ne mogu postavljati pitanja osim putem chata):
https://miteam.mi.sanu.ac.rs/call/8HX5pHW3fhfr2vFnF/Sud4M5nyx6-CCpaW4etWS1ZEM4wCvSsPuSxPAQ9Yfs6

Utorak, 02.07.2024. u 14:00, Kneza Mihaila 36, sala 301f i On-line
Michael Benedikt, Oxford
DECIDABILITY OF ARITHMETIC
This talk will be about algorithms for deciding whether a formula in first-order logic with arithmetic operators holds in the integers. In particular, we focus on addition, inequality, and exponentiation with base 2, known to be decidable from work of Semenov several decades ago. The seminar will be mostly based on a paper at ICALP 2023, joint with Dmitry Chistikov and Alessio Mansutti, which provides the first complexity bounds for this theory: https://drops.dagstuhl.de/opus/volltexte/2023/18164/.
I will include some background on decision procedures, and I am hoping to make the talk accessible to people who know nothing about this area. If time permits, I may also say a few words about related decidability results and periodic spectra for counting logics with arithmetic, joint work with Tony Tan and Egor Kostylev: https://arxiv.org/html/2006.01193v2.
Zajednički sastanak sa Odeljenjem za matematiku.

OBAVEŠTENJA:

Ukoliko zelite mesecne programe ovog Seminara u elektronskom obliku, obratite se: tane@mi.sanu.ac.rs. Programi svih seminara Matematickog instituta SANU nalaze se na sajtu: www.mi.sanu.ac.rs

Beograd,
Srdacan pozdrav,
Predrag Tanovic
rukovodilac seminara