ПОЛИНОМИАЛЬНАЯ ЭКВИВАЛЕНТНОСТЬ ЗАДАЧ ИЗОМОРФИЗМ ПРЕДИКАТНЫХ ФОРМУЛ И ИЗОМОРФИЗМ ГРАФОВ

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

Аннотация

В работе рассматривается задача проверки изоморфности двух элементарных конъюнкций предикатных формул, возникающая при решении ряда задач искусственного интеллекта, допускающих формализацию средствами языка исчисления предикатов и её связь с задачей проверки изоморфизма графов.

Точное определение понятия изоморфности таких формул приведено в тексте статьи. Однако неформально говоря изоморфные элементарные конъюнкции предикатных формул -- это формулы, которые при некоторой подстановке переменных вместо их аргументов совпадают с точностью до порядка записи литералов. Описаны задачи, при решении которых возникает необходимость проверки формул на изоморфность.
Переведенное названиеPolynomial equivalence of the problems predicate formulas isomorphism and graph isomorphism
Язык оригиналарусский
Страницы (с-по)430–439
ЖурналВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ
Том6 (64)
Номер выпуска3
СостояниеОпубликовано - мая 2019

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

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

Ключевые слова

  • изоморфизм графов, изоморфизм предикатных формул, GI-полнота

Fingerprint Подробные сведения о темах исследования «ПОЛИНОМИАЛЬНАЯ ЭКВИВАЛЕНТНОСТЬ ЗАДАЧ ИЗОМОРФИЗМ ПРЕДИКАТНЫХ ФОРМУЛ И ИЗОМОРФИЗМ ГРАФОВ». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать