Зарежда Събития

На 29 юли 2022 г. (петък) от 13:00 ч. ще се проведе дистанционно заседание на семинара по „Алгебра и логика”.

Доклад на тема:

Modal Descriptive Complexity

ще изнесе Петър Илиев (ИФС-БАН и ИМИ-БАН).

Абстракт. 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.


Семинарът ще се проведе посредством платформата Zoom и всеки желаещ може да се присъедини като последва линка:


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

От секция „Алгебра и логика” на ИМИ – БАН
============================== =====================

Go to Top