Алгоритмические свойства алгебр подмножеств

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