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

Standard

ПОЛИНОМИАЛЬНАЯ ЭКВИВАЛЕНТНОСТЬ ЗАДАЧ ИЗОМОРФИЗМ ПРЕДИКАТНЫХ ФОРМУЛ И ИЗОМОРФИЗМ ГРАФОВ. / Косовская, Татьяна Матвеевна ; Косовский, Николай Николаевич.

In: ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ, Vol. 6 (64), No. 3, 05.2019, p. 430–439.

Research output: Contribution to journal › Article › peer-review

BibTeX

@article{82d525c880ac4e5c928beb0a30422133,

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

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

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

author = "Косовская, {Татьяна Матвеевна} and Косовский, {Николай Николаевич}",

year = "2019",

month = may,

language = "русский",

volume = "6 (64)",

pages = "430–439",

journal = "ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ",

issn = "1025-3106",

publisher = "Издательство Санкт-Петербургского университета",

number = "3",

}

RIS

TY - JOUR

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

AU - Косовская, Татьяна Матвеевна

AU - Косовский, Николай Николаевич

PY - 2019/5

Y1 - 2019/5

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

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

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

UR - https://elibrary.ru/item.asp?id=39422812

M3 - статья

VL - 6 (64)

SP - 430

EP - 439

JO - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

JF - ВЕСТНИК САНКТ-ПЕТЕРБУРГСКОГО УНИВЕРСИТЕТА. МАТЕМАТИКА. МЕХАНИКА. АСТРОНОМИЯ

SN - 1025-3106

IS - 3

ER -

ID: 47420642