Pozivamo vas da prisustvujete zajedničkom sastanku Odeljenja za matematiku i Seminara za računarsku logiku u petak, 17. aprila, sa početkom u 14.15 časova, u sali 301f, Matematičkog instituta SANU, Kneza Mihaila 36, kao i onlajn.
Predavač: Staniclav Speranski, Steklov Mathematical Institute of RAS
Tema predavanja: WEAK ARITNMETIC FROM THE VIEWPOINT OF MONADIC SECOND-ORDER LOGIC
Apstrakt:
By a weak arithmetical structure we shall mean a structure on the natural numbers such that: a) all the corresponding predicates and functions are computable; b) its elementary (that is, first-order) theory
is decidable. Among the structures of this kind are Presburger’s and Skolem’s arithmetics, viz. the natural numbers with equality and either addition or multiplication. We are going to discuss monadic second-order definability in weak arithmetical structures and related complexity issues. Here `monadic’ means that only predicate variables of arity 1 — which range over unary predicates on the natural numbers — are allowed. In effect, in second order logic, it is often natural to focus on monadic formulas. We shall examine in detail the case of Presburger arithmetic, and somewhat less explicitly, the case of Skolem arithmetic and its reducts.
Napomena: Predavanja možete pratiti na daljinu. Sve informacije su dostupne na stranici:
