Об элементарных теориях графов и абелевых луп

Рассматривается алгоритмическая разрешимость элементарных теорий некоторых классов графов, таких, как однородные, плоские, двудольные плоские, критические неплоские. Для первых классов доказана неразрешимость элементарных теорий, а для последнего — разрешимость с дополнительным предикатом. Доказана также неразрешимость теории абелевых луп интерпретацией в ней теории двудольных однородных степени 3 графов. Библ. 7 назв.