СУ "Св. Климент Охридски"

Научноизследователски проекти

Skip Navigation Links
 

Търсене

Новини

Вход в системата

 

 





>>Регистрация
>>Забравена парола

Ръководство


Ефективни свойства на абстрактни структури



1.9.2019 г. 1.9.2021 г.

Теория на изчислимостта, като основна част от математическата логика, разглежда възможността и границите на ефективност и прилагането на алгоритмични методи и е силно свързана с други области на математиката и теоретичната компютърна наука. Изследванията са в областта на еффективната структурна теория, комбинираща методи от теория на изчислимостта, алгебрата и теория на моделите. Един от основните въпроси в тази област е характеризацията на абстрактните структури от гледна точка на тяхната сложност., т.е. кои множества са определими и кои функции са изчислими в тях. сложността на връзките между отделните представяния са интересни, защото дават по-пълна картина на алгоритмичните свойства на структурата. Задачата е да се изследва как моделите на изчислимост могат да се приложат за изучаването на ефективните свойства на класическите математически обекти. И двете групи изследователи, българската и австрийскта, са експерти в тази област с много скорошни изследвания, прилагайки изчислимо-теоретини методи в изучаването на абстрактните структури, като структури с релация на еквивалентност, линейни наредби, Булеви алгебри, групи, графи и др. В този проект се интересуваме от следните теми: 1.Класификация на проблема за принадлежност на дума в групите. Проблемът за принадлежност на дума в дадена изчислимо представена група естествено определя една рекурсивно-номеруема релация на еквивалентност, наречена "ceer"(computably-enumerable equivalence relation) : две думи са в един и същи клас, ако те представят един и същи елемент в групата. Естествено е да се попитамекои ceer могат да бъдат реализирани като проблема за принадлежност на дума в група. Например, наскоро бе показана крайно представима група, чиито проблем за принадлржност формира най-общия ceer спрямо Тюринговата сводимост. Тъй като не всеки ceer може да се реализира като проблем за принадлежност в група, този въпрос е сложен. Повечето въпроси за реализуемост са открити. 2. Хомоморфизъм между структури. Австрийската група е изследвала сложността на инективните хомоморфизми между двойки от структури с релация на еквивалентност и двойки от Абелеви групи без торсия. Целта ни е да разгледаме по-общ проблем: фиксирайки две структури от някой познат клас, да изследваме с каква сложност можем да изчислим инективе/сюрективен изоморфизъм между тях. 3. Ефективни влагания на класове от структури. Широко използван метод за изследване на алгоритмичната сложност включва сравняването на различните класове от структури, използвайки различни ефективни сводимости между класовете. Две от най-често използваните сводимости са базирани на Тюринговите и номерационни оператори. Членове на българскта група наскоро изследваха един най-прост случай, когато класовете са генерирани от две структури-линейни наредби, затворени относно изоморфизъм. Те изучиха как таква двойки се различават, когато сменяме една ефективна сводимост с друга. От друга страна, членове на австрийската група изучиха ефективните влагания като функтори-двойки от номерационни оператори. Планираме да комбинираме двата подхода и да изучим сложността на класовете абстрактни структури по-прецизно.
Изчислимост, рекурсивно-номеруема релация на еквивалентност, Тюр-рингов и номерационен оператор, хоморфизъм между структури, спектър на структура, ефективно влагане на класове от структури

Детайлна информация

Международен
Конкурс за финансиране проекти по програми за двустранно сътрудничество 2018 г. – България - Австрия МОН - Фонд „Научни изследвания”
40000,00 0,00

Координатор


Софийски университет, Факултет по Математика и Информатика

Александра Соскова

Участващи подструктури на СУ "Св. Климент Охридски"


Ръководител(и) в СУ "Св. Климент Охридски"



Доцент, asoskova@fmi.uni-sofia.bg

Партньори на проекта



Научни прояви

<декември 2019 г.>
пнвтсрчтптсбнд
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345