Speaker:

Alexander Zapryagaev (University of Electronic Science and Technology of China)

Time:

• 16:20-17:20 (Time in Beijing)
• April 12, 2024 (Friday)

Venue:

518, Research Building 4

Abstract:

The talk introduces Presburger arithmetic PrA, the theory of natural numbers with addition, and Büchi arithmetics BA_n, a series of algorithmically decidable extensions of PrA. The main logical and algorithmic properties of these theories and their fragments are explored, both classical and recently obtained. Various expressibility results are introduced as well as some data on the structure of the non-standard models of PrA and BA_n. We discuss the Büchi-Bruyère theorem, establishing the direct connection between interpretations in Büchi arithmetics and automatic structures, as well as the Cobham-Semënov theorem, allowing to compare the expressive powers of BA_n for different n. The speaker’s result on the non-existence of interpretations from BA_n to itself unless isomorphic to the trivial one is presented and put in context.