О теориях подмножеств некоторых алгебр

Одной из задач общей алгебры и теории моделей является изучение различных операций, позволяющих получать из одних алгебраических систем другие. Важным примером такой операции является прямое произведение. С “программистской” точки зрения прямое произведение соответствует переходу от скалярных типов данных к векторам, то есть к упорядоченным наборам значений. Однако в программировании встречаются и множества, то есть неупорядоченные наборы. Математически этой структуре данных соответствует операция взятия некоторых подмножеств универсума исходной алгебраической системы. В качестве примера такой операции можно привести переход от операций над отдельными словами к операциями над языками. Доклад посвящён обзору результатов, связанных с различными свойствами некоторых алгебр подмножеств. Была исследована алгоритмическая сложность некоторых теорий класса регулярных языков с различными наборами операций (объединение, конкатенация, итерация), а также вычислительная сложность некоторых из этих теорий. Также были исследованы свойства унаров — простейших алгебр, содержащих единственную одноместную функцию. Для широкого класса унаров было изучено, как сохраняются или изменяются их свойства при переходе к унару подмножеств.