Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis

Переведенное название: Полиномиальная эквивалентность задач изоморфизм предикатных формул и изоморфизм графов

Результат исследований: Научные публикации в периодических изданияхстатья

1 Цитирования (Scopus)

Аннотация

The problem of isomorphism checking of two elementary conjunctions of predicate formulas is considered in this work. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. The exact definition of the concept of isomorphism of such formulas is given in this paper. However, isomorphic elementary conjunctions of predicate formulas are formulas that, with some substitution of variables instead of their arguments, coincide with the accuracy of the order of writing literals. Problems are described that, when solved, mean the necessity of testing formulas for isomorphism arises. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.
Переведенное названиеПолиномиальная эквивалентность задач изоморфизм предикатных формул и изоморфизм графов
Язык оригиналаанглийский
Страницы (с-по)286–292
ЖурналVestnik St. Petersburg University: Mathematics
Том52
Номер выпуска3
DOI
СостояниеОпубликовано - сен 2019

Предметные области Scopus

  • Математика (все)
  • Компьютерные науки (все)

Fingerprint Подробные сведения о темах исследования «Полиномиальная эквивалентность задач изоморфизм предикатных формул и изоморфизм графов». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать