Abstract:
Для изучения алгоритмических свойств моделей с интересными алгебраическими и теоретико-модельными свойствами часто используются их структурные свойства. Однако во многих случаях результаты о моделях одного класса могут быть перенесены на модели из других важных классов. Одним из способов получения таких результатов является кодирование исходных моделей в модели из заданного класса достаточно эффективным образом, чтобы сохранить все нужные свойства. Существует множество конструкций, позволяющих сводить вопросы об алгоритмических свойствах различных классов к аналогичным вопросам для графов. С другой стороны, результаты, верные для графов, также верны для класса всех моделей произвольной конечной сигнатуры, содержащей хотя бы один предикатный или функциональный символ местности не менее 2. В данной работе мы обобщаем этот подход на случай всех так называемых богатых сигнатур и доказываем, что подобные результаты можно получить для классов всех моделей произвольной сигнатуры, содержащей хотя бы один двухместный предикатный символ или два одноместных функциональных символа.
