An online session of the Algebra and Logic Seminar will be held on July 29, 2022 (Friday) at 1:00 pm (UTC+3).

A talk on:

Modal Descriptive Complexity

will be delivered by Petar Iliev (IPS-BAS and IMI-BAS, Bulgaria).

Abstract. 

The study of the descriptive complexity of a class of structures S relative to a class of formulae F from a logic L revolves around the question: what can we say about the definability of S with formulae from F? For example, we might want to know whether there is a formula from F defining S or, if not, whether there is a countably infinite sequence of F-formulae such that each formula from the sequence defines a subset of S and the union of all these subsets is the whole S. If we have the former situation, it is natural to ask about the minimal number of variables in any F-formula defining S, or its minimal length, or the minimal number of operators like quantifiers, disjunctions and conjunctions, and the minimal depth of their nesting. In the latter situation, we might want to know how (some of) these measures scale with the index of individual formulae.

In my talk, I am going to survey several recent results, in some of which I have been involved, coming from the area of the descriptive complexity of classes of Kripke frames (directed graphs) and classes of Kripke models (edge-and vertex-coloured directed graphs) relative to some well-known modal logics.

Join Zoom meeting:
https://us02web.zoom.us/j/85137375021?pwd=RE5QczdFTE1xL1R6MnI2b1lkcGczQT09

Topic: Онлайн семинар на секция “Алгебра и логика”
Time: July 29, 2022 01:00 PM Sofia
Meeting ID: 851 3737 5021
Passcode: 035647

Algebra and Logic Department, IMI-BAS
http://www.math.bas.bg/algebra/seminarAiL/
============================== =====================