|
СЕМИНАРЫ |
Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar"
|
|||
|
Алгоритмические свойства алгебр подмножеств С. М. Дудаков Тверской государственный университет |
|||
Аннотация: Одним из способов построения новых алгебр из уже существующих является рассмотрение алгебры всех или некоторых (например, только конечных) подмножеств. В частности, таким образом из алгебры слов с операцией конкатенации можно получить алгебру языков с этой же операцией. Мы исследуем некоторые вопросы, связанные с такими алгебрами. Основным из них является разрешимость или неразрешимость теории таких алгебр, возможность интерпретации в ней элементарной арифметики. В качестве исходных алгебр рассматриваются уноиды (алгебры с одной одноместной операцией) и некоторые виды полугрупп. |