Links

A problem of isomorphism checking of two elementary conjunctions of predicate formulas is under consideration. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.
Translated title of the contributionPolynomial equivalence of the problems predicate formulas isomorphism and graph isomorphism
Original languageRussian
Pages (from-to)430–439
JournalВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Volume6 (64)
Issue number3
StatePublished - May 2019

    Scopus subject areas

  • Mathematics(all)
  • Computer Science(all)

ID: 47420642