Изучаются вопросы, связанные с восстановлением алгебраической структуры из ее полугруппы частичных автоморфизмов. Частичные преобразования изучались во многих работах и часто более полно характеризуют алгебраическую структуру в отличии от полных преобразований.
Частичное преобразование $f$ модели ${\cal M}$ в себя назовем частичным автоморфизмом, если оно взаимо однозначно и для любого предиката $P$ модели ${\cal M}$, для любых $a_1,\ldots ,a_n \in |{\cal M}|$, принадлежащих области определения преобразования $f$, выполняется $${\cal M}\models P(a_1,\ldots,a_n) \iff {\cal M}\models P(f(a_1),\ldots,f(a_n))$$
Частичный автоморфизм $f$ назовем конечным (частично рекурсивным), если область определения автоморфизма $f$ является конечным (рекурсивно перечислимым) множеством.
Ранее автором было доказано[1], что произвольная модель конечной сигнатуры определяется своей полугруппой конечных частичных автоморфизмов с точностью до элементарной эквивалентности.
Известно[2], что граф характеризуется своей полугруппой частичных преобразований (изотонных или направленных) с точностью до двойственности. Этот результат может быть усилен следующим образом: если $G_1,G_2$ -- направленные графы, $I_f(G_1),I_f(G_2)$ -- их полугруппы конечных частичных автоморфизмов и $I_f(G_1)\cong I_f(G_2)$, то $G_1$ и $G_2$ изоморфны или антиизоморфны. Таким образом, даже полугруппа конечных частичных автоморфизмов характеризует граф с точностью до двойственности.
Изучение рекурсивных моделей и их рекурсивных преобразований позволяет получить более сильные результаты. Пусть $B_1,B_2$ -- рекурсивные булевы алгебры, $I_r(B_1),I_r(B_2)$ -- их полугруппы частично рекурсивных частичных изотонных преобразований и $I_r(B_1)\cong I_r(B_2)$. Тогда $B_1$ и $B_2$ рекурсивно изоморфны.
[1]\rm Липачева Е. В. \it Частичные автоморфизмы счетных моделей \rm // Известия ВУЗов. Математика. -- 1997. -- N 1. -- С.~12 -- 21.
[2]\rm Важенин Ю. М. \it Элементарные свойства полугрупп частичных преобразований рефлексивных графов \rm // "Исслед. по соврем. алгебре". Мат. записки. Свердловск, УрГУ. -- 1977. -- Т.~10, N 3. -- C.~3 -- 19.