H2020Индивидуална стипендия2020–2022

D-FINED · Duality for Finite Models: Relating Structure and Power

„Хоризонт 2020“ — Действия „Мария Склодовска-Кюри“

Период: 2020-02-01 → 2022-01-31
Финансиране от ЕС: 212 934 €
Участници: 1
Схема: MSCA-IF-EF-ST

Линиите свързват координатора с партньорите.

Накратко на български

Логиката и семантиката на изчисленията изследват връзката между структурата на данните и изчислителната сложност при крайни модели. Това помага за създаването на единен подход между математическата логика и компютърните науки.

Този кратък обзор е генериран от изкуствен интелект

Кратко обяснение, генерирано от езиков модел по текста на CORDIS. Оригиналът е по-долу.

Резултати накратко

Duality for Finite Models: Relating Structure and Power

This project focusses on the research area of logic and semantics of computation. Finite model theory is the specialisation of model theory to finite structures and has been called “the logic of computer science” since in the latter field the basic models of computation are finite. Many classical results of model theory fail when restricted to finite models. For this reason, finite model theory has developed independently from model theory and the research communities, as well as the techniques, are almost disjoint. Finite model theory exemplifies a strand in the field of logic in computer science focussing on expressiveness and complexity (“Power”), as opposed to the one focussing on semantics and compositionality (“Structure”). The overall objective of this project is to bridge the gap between the semantics methods of model theory, and the combinatorial and complexity-theoretic methods of finite model theory, i.e., to relate Structure and Power. The three main goals in this direction are to: - (Objective 1) Develop a structural approach to the study of spaces of finite structures, based on duality and categorical methods. - (Objective 2) Extend the applicability of these methods from finite structures to tame classes of infinite structures. - (Objective 3) Relate the duality approach to existing categorical semantics, such as Lawvere's hyperdoctrines and the game comonads recently introduced by Abramsky, Dawar and their collaborators. This project may contribute to a more unified view of logic in mathematics and computer science, providing new tools for a structural approach to more algorithmic and complexity-oriented areas of logic such as finite model theory.

Текст от CORDIS, на английски · Данни: CORDIS, © Европейски съюз

Цел на проекта

The present project is positioned in the research area of logic and semantics of computation, combining a rich mathematical theory with concrete applications in computer science. Finite model theory (FMT) is the specialisation of model theory to the class of finite models, and has been called ``the logic of computer science'' because in the latter field the basic models of computation are finite. Most of the classical results of model theory fail when restricted to finite models, hence FMT is studied using different tools and methods. For this reason, FMT has developed mostly independently from model theory and the research communities, as well as the techniques, are almost disjoint. FMT exemplifies a strand in the field of logic in computer science focussing on expressiveness and complexity (``Power""), as opposed to the one focussing on semantics and compositionality (``Structure""). In this project we will apply Stone duality to bridge the gap between the semantics methods of model theory, and the combinatorial and complexity-theoretic methods of FMT, i.e., to relate Structure and Power.In his Ph.D. thesis, the applicant has successfully applied Stone duality and topology to the study of formal languages and logic on finite words. The proposed project constitutes both a natural continuation of this research line, generalising from finite words to finite models, and a novel approach to FMT. The applicant will collaborate with the supervisor, who is a leading expert in the interactions between logic and computational models arising in computer science. An essential feature of this project is its high degree of interdisciplinarity, aiming to strengthen the connections between mathematics and computer science. The host institution, which is home to several experts in logic and foundations of computer science, will benefit from the applicant's experience in duality theory and topology, thus fostering cross-fertilisation within the European research community.""

Оригинален текст от CORDIS (на английски).

Участници

THE CHANCELLOR, MASTERS AND SCHOLARS OF THE UNIVERSITY OF OXFORD · OxfordКоординаторОбединеното кралство