Odeljenje za matematiku, 2. jul 2024.

• 02. Jul,  2024
• Komentari (0)

Naredni sastanak Seminara biće održan u utorak, 2. jula 2024. godine, u sali 301f Matematičkog instituta SANU sa početkom u 14 časova. U pitanju je zajednički sastanak sa Logičkim seminarom

Predavač: Michael Benedikt, Oxford University
 
Naslov predavanja: DECIDABILITY OF ARITHMETIC

Apstrakt: 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

Napomena: Predavanja se mogu pratiti na daljinu preko linka:
https://miteam.mi.sanu.ac.rs/call/T9XDGChhq8aDcNqmz/qw7wIwci2jv2rdg9I9CrXkm7OJhF_LB8DfjXZp4jTFV
 
Registraciona forma je dostupna na linku:
https://miteam.mi.sanu.ac.rs/asset/tz97w4Hu4c3unsJ7N

---