Наредни састанак Семинара биће одржан у уторак, 2. јула 2024. године, у сали 301ф Математичког института САНУ са почетком у 14 часова. У питању је заједнички састанак са Логичким семинаром
Предавач: Michael Benedikt, Oxford University
Наслов предавања: 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
Напомена: Предавања се могу пратити на даљину преко линка:
https://miteam.mi.sanu.ac.rs/call/T9XDGChhq8aDcNqmz/qw7wIwci2jv2rdg9I9CrXkm7OJhF_LB8DfjXZp4jTFV
Регистрациона форма је доступна на линку:
https://miteam.mi.sanu.ac.rs/asset/tz97w4Hu4c3unsJ7N