Выделение наибольших общих свойств сложных структурированных объектов тема диссертации и автореферата по ВАК РФ 00.00.00, кандидат наук Чжоу Цзюань

• Чжоу Цзюань
• кандидат наук
• 2025

Оглавление диссертации кандидат наук Чжоу Цзюань

Введение

Глава 1. Изоморфизм элементарных конъюнкций предикатных

формул

1.1. Необходимые определения

1.2. Алгоритм ISOM-1 проверки изоморфизма двух элементарных конъюнкций, содержащих единственный предикатный символ

1.3. Вычислительная сложность алгоритма ISOM-1

1.4. Алгоритм ISOM проверки изоморфизма двух элементарных конъюнкций, содержащих несколько предикатных символов

1.5. Вычислительная сложность алгоритма ISOM

1.6. Модельный пример применения алгоритма ISOM-1

1.7. Выводы

Глава 2. Наибольшая общая подформула с единственным предикатным символом

2.1. Необходимые определения и обозначения

2.2. Постановка задачи

2.3. Описание алгоритма MCF1 нахождения наибольшей общей подформулы двух заданных элементарных конъюнкций с единственным предикатным символом

2.4. Описание алгоритма CONS-T построения непротиворечивого дерева возможных унификаторов

2.5. Анализ вычислительной сложности алгоритма MCF1

2.6. Пример применения алгоритма MCF1 для предикатных формул

2.7. Пример применения алгоритма формирования непротиворечивого дерева возможных унификаторов CONS-T

2.8. Выводы

65

Глава 3. Наибольшая общая подформула с произвольным коли-

чеством предикатных символов

3.1. Описание алгоритма MCF2 выделения общих свойств объектов, описанных на языке исчисления предикатов с двумя предикатными символами

3.2. Вычислительная сложность MCF2

3.3. Пример применения алгоритма MCF2

3.4. Описание алгоритма MCFn выделения общих свойств объектов, описанных на языке исчисления предикатов с несколькими предикатными символами

3.5. Вычислительная сложность MCFn

3.6. Пример применения алгоритма MCFn

3.7. Выводы

Глава 4. Применение предложенных алгоритмов к решению

некоторых задач для ориентированных графов

4.1. Изоморфизм графов

4.2. Пример применения алгоритма ISOM-1 для ориентированных графов

4.3. Максимальный общий подграф

4.4. Пример применения алгоритма MCF1 для ориентированных графов

4.5. Выводы

Заключение

Список литературы

Введение

Введение диссертации (часть автореферата) на тему «Выделение наибольших общих свойств сложных структурированных объектов»

Актуальность темы исследования

В области искусственного интеллекта часто возникают задачи, которые требуют формализации представления исследуемого объекта не только как единого целого, но и его составных частей и взаимосвязей между ними. Это ведет к определению предметов как сложных структурированных объектов. Одним из примеров такого подхода является процесс распознавания контурных изображений. При этом описание сложного структурированного объекта может быть сформулировано как элементарная конъюнкция атомарных предикатных формул, в которых свойства элементов объектов и отношения между его элементами описаны в терминах заданного набора предикатов. Подобные методы и концепции обсуждались в научной литературе ещё с 70-х годов двадцатого века, что свидетельствует о долгосрочном интересе к вопросам, связанным с пониманием структуры объектов и их характеристик (например, [1,2]), и получили дальнейшее развитие в современных исследованиях, например, в [3].

Однако практика реализации такого подхода сталкивается с серьезными ограничениями. Основная проблема заключается в значительной вычислительной сложности, обусловленной тем, что рассматриваемые задачи принадлежат классам КР-трудных задач (как показано в [4-8]) или С1-трудных (полиномиально эквивалентных задаче изоморфизма графов [9]). Аналогичные задачи на графах тоже КР-трудны или С1-трудны. Поэтому, несмотря на теоретическую значимость выявления общих свойств, его практическое применение до сих пор остается затруднительным.

Степень разработанности темы исследования

Для уменьшения такой вычислительной сложности в работе [10] была предложена концепция многоуровневого описания классов объектов, которая позднее была уточнена в [11]. Этот подход позволяет существенно уменьшить вычислительную сложность распознавания сложных структурированных объектов, и

это продемонстрировано в [12] при описании многогранников, где обобщённые предикаты отражают уникальную специфику структур данных.

При создании таких описаний требуются выделения наибольших общих свойств объектов. Эти свойства описываются формулами, имеющими максимальное количество литералов и содержащими переменные в качестве аргументов, которые с точностью до имён аргументов совпадают с подформулами исследуемых объектов, т.е. изоморфны этим подформулам. Согласно [12], максимальное общее свойство отражает важные общие характеристики элементов сложных структурированных объектов, а также их соотношения.

Помимо многоуровневого описания объектов [13], алгоритм нахождения максимального общего свойства может быть применён для других задач (рис. 1). Это показывает универсальность подхода, его полезность не только для анализа, но и для моделирования знаний и выделения ключевых атрибутов.

1. Неполная информация [14], например, отсутствие данных, ошибки в измерениях или частичное скрытие объектов, создает трудности для систем распознавания, которые требуют полной информации для точного анализа. Выделение максимальных общих характеристик позволяет выявить общие черты между различными представлениями объектов, даже если некоторые детали отсутствуют. Это означает, что система может сосредоточиться на наиболее значимых и общих характеристиках, и использовать их для распознавания или классификации. Следовательно, выделение максимальной общей подформулы является важным инструментом в логике и распознавании образов, позволяющим эффективно работать с неполной и частично искаженной информацией.

2. Метрику в пространстве элементарных конъюнкций предикатных формул1 можно определить на основе нахождения максимальной общей под-

1 Поскольку в работе будут рассматриваться только элементарные конъюнкции предикатных формул, то вместо этого длинного термина будет использоваться термин "предикатная формула".

Рис. 1. Применения выделения общих свойств объектов

формулы [15]. Этот подход позволяет определить расстояние (степень их "похожести") между объектами, описанными предикатными формулами, путем анализа их логических описаний. Наибольшая общая подформула служит основой для оценки степени сходства между двумя объектами: чем больше общих элементов (атомарных подформул) содержится в описании, тем ближе объекты. Это позволяет не только количественно оценивать расстояние между объектами, но и учитывать их логические структуры и взаимосвязи. Таким образом, использование максимальной общей подформулы для определения метрики способствует более точному решению задач распознавания и классификации объектов, что является важным аспектом в области искусственного интеллекта и обработки данных.

3. В работах [11,16] показано, что несколько агентов могут составлять описание объекта, обладая лишь частичной информацией. Задача заключается в восстановлении полного описания на основе данных от каждого агента. Для этого предлагается алгоритм, который выявляет общие подформулы и их унификаторы, что позволяет сформировать общее представление об объекте, несмотря на различия в именах элементов.

4. Построение многоуровневой базы данных для уменьшения вычислительной сложности решения КР-полной задачи Конъюнктивного Булевского Запроса [17] рассматривается в статье [18]. Одним из основных этапов этого подхода является выделение наибольших общих свойств (или подформул) из элементарных конъюнкций, задающих описания. Выделение наибольших общих свойств (или подформул) в контексте задачи конъюнктивного булевского запроса связано с тем, что многократное решение этих задач может привести к обнаружению частей запросов с аналогичной структурой или формой, то есть изоморфными подформулами. Такой подход значительно уменьшает количество шагов проверки истинности запросов. Так как с одной стороны, результаты выделенных одинаковых подформул можно сохранять и повторно использовать, а с другой стороны, он фокусируется на уникальных и значимых частях запросов, что уменьшает общую вычислительную нагрузку.

5. В [19] предложена адаптивная модель самообучающейся сети с двухмо-дульной архитектурой (обучение/распознавание), где динамическая реконфигурация сети инициируется ошибками классификации. Основу метода составляет логико-предикатный подход с использованием элементарных конъюнкций для формализации задач искусственного интеллекта. Для снижения вычислительной сложности (КР-трудность) применена иерархические многоуровневые описания целевых формул через выделение наибольших подформул, что сокращает экспоненциальные затраты за

счёт разделения на подзадачи.

6. Статья [20,21] посвящена логико-предикатной сети, предназначенной для нечеткого распознавания сложных структурированных объектов, описываемых предикатными формулами. Ключевым аспектом данной методологии является процесс извлечения общих признаков, который позволяет выявлять группы характеристик, общих для объектов одного класса, что способствует повышению эффективности распознавания и уменьшению вычислительной сложности. Основной результат работы заключается в реконструкции ячейки распознавания логико-предикатной сети, что позволяет распознавать объекты, описание которых не является изоморфным тем, что использовались в обучающем наборе. Этот процесс включает также расчёт степени совпадения между признаками распознаваемого объекта и характеристиками, присущими объектам из извлеченной группы. Кроме того, логико-предикатная сеть отличается от существующих сетей, таких как нейронные [22-24] или байесовские [25], своей способностью изменять конфигурацию во время переобучения. Это отражает процесс обучения у человека, когда связи между нейронами изменяются, что делает сеть более адаптивной и эффективной.

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

кусственного интеллекта.

В процессе выделения максимального общего свойства между двумя объектами важным этапом является проверка изоморфизма элементарных конъюнкций предикатных формул [27], которая позволяет с точностью до имён переменных определять структурные сходства. Эта задача относится к классу GI-полных задач. Другими словами, она полиномиально эквивалентна "открытой" задаче "Изоморфизм графов" [9], для которой не доказана NP-полнота и отсутствуют алгоритмы, позволяющие решить её за полиномиальное время. Оценка сложности алгоритма квазиполиномиального времени, доказанная Ба-баем [28], является 2°((log п) ()). Хелфготт впоследствии утверждает, что время выполнения составляет 2O ((logn) ) [29,30].

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

Различные исследования направлены на решение данной задачи. Например, в работе [31] разработан алгоритм VF2 для графового сопоставления, который применяет набор правил выполнимости и соответствует проверке унификаторов на противоречивость, изложенной ниже; в [32] представлен новый алгоритм VF3 для проверки изоморфизма графов с определёнными свойствами, который на несколько порядков превосходит своего предшественника по времени выполнения; модель GLSEARCH (Graph Learning to Search) [33] построена на алгоритме ветвей и границ с использованием новой глубокой DQN-сети на базе графовых нейронных сетей [34-43] для отбора пар узлов, что позволяет находить гораздо больше общих подграфов, чем существующие алгоритмы решения проблемы максимального общего подграфа при аналогичном уровне вычислительных затрат.

В работе [44] были предложены возможные алгоритмы, которые позволяют как проверять предикатные формулы на изоморфизм, так и выделять

наибольшее общее свойство двух объектов. Кратко изложены описания этих алгоритмов.

В [45,46] представлены детализированные, отличающиеся от [44] алгоритмы проверки элементарных конъюнкций на изоморфизм, а также доказаны оценки числа шагов этих алгоритмов.

Цели и задачи диссертационной работы

Цели заключаются в научном обосновании и разработке алгоритмов проверки изоморфизма предикатных формул и нахождения их наибольших общих подформул, а также в доказательстве оценок вычислительной сложности предложенных алгоритмов. Для достижения поставленных целей были решены следующие задачи:

1. Изучить методы ветвей и границ, поиска с возвратом, «разделяй и властвуй» и алгоритмы нахождения максимальных общих подграфов.

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

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

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

5. Получить и доказать оценки вычислительной сложности всех созданных алгоритмов.

Научная новизна

1. Разработан и реализован на языке Python алгоритм ISOM-1 проверки двух элементарных конъюнкций с единственным предикатным символом на изоморфизм, на основе которого построен алгоритм ISOM для нескол-ких предикатных символов.

2. Разработан и реализован на языке Python алгоритм MCF1 выделения общих свойств объектов, описанных на языке исчисления предикатов с одним предикатным символом, на базе которого созданы MCF2 и MCFn для двух и произвольных предикатных символов.

Теоретическая и практическая значимость

Результаты, изложенные в диссертации, могут быть использованы для выделения наибольших общих свойств сложных структурированных объектов, определенных как свойствами своих элементов, так и отношениями между ними. Данные характеристики позволяют формализовать объекты на языке исчисления предикатов и решать задачи, такие как многоуровневые описания классов [12], распознавание объектов с неполной информацией [14], определение расстояния (степени их "похожести") между объектами [15], составление мультиагентного описания объекта по достоверной информации [16], построение "логических баз данных" [18], формирование "предикатной сети", которая может менять свою конфигурацию после дообучения [19], нечеткое распознавание сложных структурированных объектов [20], разработка онтологий [26].

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

Методология и методы исследования

Основной методологической основой является теоретический подход, основанный на математической логике [47-49], математических моделях и тео-

рии графов [50-54]. В рамках этого подхода применяются различные алгоритмические стратегии, включая метод ветвей и границ (например, QuickSI [55], GraphQL [56], GADDI [57], Spath [58], Turboiso [59], DualIso [60], VF3 [61], BB-Graph [62], SubISO [63], BF-BigGraph [64]), поиск с возвратом (англ. backtracking) [31,65-72], подход «разделяй и властвуй» [73,74], а также алгоритмы для проверки графов на изоморфизм [75—79] и нахождения максимальных общих подграфов [80-84].

Степень достоверности и апробация результатов Основные результаты диссертации докладывались на следующих конференциях:

• Конференция «Информационные технологии в управлении» (ИТУ-2022) в рамках 15-й мультиконференции по проблемам управления (МКПУ-2022), секция: «Интеллектуальные информационные технологии в управлении» [85], г. Санкт-Петербург;

• Всероссийская научная конференция по проблемам информатики «СПИ-СОК-2023», секция: «Фундаментальная информатика» [86], г. Санкт-Петербург;

• The 14th international conference «Computer Science and Information Technologies» (CSIT 2023), секция: «Algorithms, Automata and Logic» [45], г. Ереван, Армения;

• Всероссийская конференция по естественным и гуманитарным наукам с международным участием «Наука СПбГУ 2023», секция: «Математика, механика, информатика» [87], г. Санкт-Петербург;

• The International Workshop «Data Analytics and Mathematical Modeling» within the CSIT conference [88], г. Тбилиси, Грузия.

Публикации

Материалы диссертации опубликованы в 8 работах, из них 2 статьи в рецензируемых журналах [89,90], рекомендованных ВАК РФ, 2 статьи в зарубежных научных журналах на английском языке [46,88], индексируемых Scopus и Web of Science, 4 статьи в сборниках трудов конференций [45,85—87]. В статьях [45,46,86] диссертанту принадлежит построение алгоритмов проверки двух элементарных конъюнкций на изоморфизм. В статьях [88—90] диссертантом предложены алгоритмы наибольших общих с точностью до имён аргументов подформул с единственным предикатным символом и произвольными предикатными символами.

Личный вклад автора

Результаты, представленные в диссертационной работе, получены соискателем либо самостоятельно, либо при её непосредственном участии в неразделимом соавторстве.

Краткое описание структуры диссертации

Структура диссертационного исследования включает в себя введение, четыре главы, представленные с разбиением на разделы, описание основных результатов и выводов — в каждой главе, заключение и список литературы, содержащий 101 источник. Общий объем работы составляет 100 страниц машинописного текста, содержит 5 таблицы и 21 рисунков.

Положения, выносимые на защиту

1. Созданы алгоритмы ISOM-1 и ISOM проверки двух элементарных конъюнкций на изоморфизм. Доказаны оценки их временной сложности. Реализация данных алгоритмов выполнена на Python 2.

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

2 Ссылка на программы: https://github.com/zhoujuanna/ISOM/tree/master/ISOM

доказаны. Алгоритм реализован с использованием языка программирования Python.

3. Разработаны алгоритмы MCF2 и MCFn выделения общих свойств объектов, описанных на языке исчисления предикатов с двумя и более предикатными символами соответственно. Представлено доказательство оценок вычислительной сложности алгоритмов. Алгоритмы реализованы при помощи языка Python 3.

Основные научные результаты

1. Построены два алгоритма ISOM-1 и ISOM проверки двух элементарных конъюнкций на изоморфизм. Первый из алгоритмов проверяет на изоморфизм элементарные конъюнкции, содержащие один предикатный символ. Если предполагать, что все предикаты являются бинарными, предложенный алгоритм представляет собой алгоритм проверки двух ориентированных графов на изоморфизм. Второй алгоритм проверяет на изоморфизм элементарные конъюнкции с несколькими предикатными символами. В случае изоморфизма формул для обоих алгоритмов находятся унификаторы, которые устанавливают взаимно однозначное соответствие между их аргументами. Доказаны оценки их временной сложности. Алгоритмы реализованы на языке Python.

Алгоритм ISOM-1 первой главы опубликован в работе [86], а ISOM — [45,46].

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

3 Ссылка на программы: https://github.com/zhoujuanna/MCF/tree/master/MCF

В такой формулировке изучаемая задача является полиномиально эквивалентной NP-трудной задаче выделения наибольшего общего подграфа двух графов. В особенности, задача нахождения наибольшего общего подграфа двух ориентированных графов представляет собой частный случай рассматриваемой в этой главе задачи, при условии, что предикатный символ двухместный и вместе с литералом Р(х,у) всегда имеется литерал Р (у,х).

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

Оценки вычислительной сложности предложенного алгоритма доказаны. Реализация данного алгоритма выполнена на языке Python.

Алгоритм MCF1 опубликован в работе [89].

3. С использованием алгоритма MCF1 предложены два алгоритма MCF2 и MCFn, первый из которых решает задачу выделения максимальной элементарной конъюнкции для элементарных конъюнкций, содержащих два предикатных символа, а второй — произвольное количество предикатных символов. Доказаны оценки вычислительной сложности предложенных алгоритмов. Алгоритмы реализованы на языке Python.

Результаты третьей главы опубликованы в работе [88].

4. Написаны применения алгоритмов ISOM-1 и MCF1 к решению задач проверки ориентированных графов на изоморфизмы и выделения наибольшего общего подграфов двух ориентированных графов.

Применение алгоритма MCF1 для ориентированных графов опубликовано в работе [90].

Благодарности

Автор выражает искреннюю благодарность всем, кто оказал поддержку в процессе написания данной диссертации.

В частности, особую признательность хочется выразить своему научному руководителю, доктору физико-математических наук, профессору кафедры информатики санкт-петербургского государственного университета Косовской Татьяне Матвеевне. Её неоценимые советы, конструктивные замечания и терпеливые объяснения на протяжении всего исследования сыграли ключевую роль в формировании моего научного подхода. Глубокие знания и высокий профессионализм Татьяны Матвеевны в области применения исчисления предикатов к решению задач искусственного интеллекта и оценка вычислительной сложности алгоритмов вдохновили меня и способствовали развитию моих исследовательских навыков.

Кроме того, её поддержка в повседневной жизни была очень важна и сделала путь автора в России более комфортным и менее стрессовым. Также автор хотел бы отметить значимую поддержку, оказанную Китайским Советом по стипендиям в ходе обучения в аспирантуре, что способствовало успешному завершению учебного процесса.

В заключение, автор выражает глубокую признательность своей семье за их безусловную любовь.

17

Глава 1

Изоморфизм элементарных конъюнкций предикатных формул

1.1. Необходимые определения

Определение 1 [91,92]. Сложным структурированным объектом называется объект ш = {ш\, • • • ,шг}, элементы которого обладают заданными свойствами и находятся в заданных отношениях, определяемых предикатами

Ръ • • ,Р1.

На рис. 1.1 заданы предикаты , которые взяты из [1].

У

У(х, у, г) (Аухг < 7г)

х

и

\¥(х, у, г, и) У(х, у, г) & У(х, у, и) & У(х, и)

ж

У(ж, 2/, г, и) ^(ж, т/, г) & г, и) & г¿, г/)

У

и х у

Т(ж, 2/, г, -и) О у, г) & г, и) & у, и)

Рис. 1.1. Предикаты V, Ж, У, Т

Пример 1.1.1. Для контурного изображения на рис. 1.2 объект и = {а, Ь, с, е, /, д, К}. Элементы а,Ъ, • • • ,К находятся в отношениях, определяемых предикатами У,Ш,Т,У (см. рис. 1.1).

Рис. 1.2. Контурное изображение

Определение 2 [93,94]. Описанием сложного структурированного объекта в (и) называется максимальная по количеству литералов элементарная конъюнкция атомарных формул с предикатами Рх, • • • , истинная для и.

Пример 1.1.2. Для контурного изображения на рис. 1.2 описание объекта и представляет собой

5(и) = У (/, Ь, е, К) & Ш(Ь, а, /, с) & №(с1, д, е, а) & №(д, К, е, в) & №г(К, с, /, д) & Т(е, д,, д, /) & V(а, д,, Ъ) & V(с, Ъ, К).

Определение 3 [44]. Две элементарные конъюнкции атомарных формул исчисления предикатов ^ (ах, • • • , ап) и Р2 (Ьх, • • • , Ъп) называются изоморфными

(ах, ••• ,ап) - Р2 (Ьх, ••• ,Ьп),

если существуют такая элементарная конъюнкция Я(х1, ••• ,хп) и подстановки аргументов а^, • • • и , • • • , bjn формул ^ (ах, • • • , ап) и Р2 (Ьх, • • • , Ьп) соответственно вместо всех вхождений переменных хх, • • • ,хп формулы Я(хх, • • • , хп), что результаты этих подстановок , • • • , а1п) и

, • • • ,Ъ^п) совпадают с формулами Р1 (ах, • • • , ап) и Р2(Ьх, • • • , Ьп) соответственно с точностью до порядка литералов.

При этом полученные подстановки Хе, р1 = {х1 : а^, ••• , хп : а,1п} 4 и Хе, р2 = {х1 : , ••• ,хп : Ь3п} называются унификаторами формул Р1(а1, • • • ,ап) и Р2(Ь1, • • • ,Ъп) с формулой Я(х1, • • • ,хп) соответственно.

Пример 1.1.3. Заданы две предикатные формулы

Р1(й1, &3, 0>6, @<7, &8, 0>9) =

Р1(а6) & Р1(а2,а7) & Р2(а4,а7,а1) & Р2(^з,^5,^8) & Рз(а>9,а>2,а7,а4) & (а1,а5,аз,а8), Р2(Ь1,Ь2, ЬЗ, Ь4, Ь5, Ь6, Ьг, Ь8, Ьд) =

Р1(Ь2,Ь8)& Р1(Ьг,Ь1)& Р2(Ь5,Ь1,Ь)&

Р2(Ь8, Ьд, Ь4) & Р3(Ь6, Ь7, Ь1,Ь5) & Р3(Ьз, Ьд, Ь8, Ъ4).

Формула

Я(х1 ,х2, Х%, х4, Х5, Х6, х7, х8, Хд) =

Р1(х6,х2,) & Р1(х2,х7) & Р2(х4,х7,х1) & Р2(ХЗ,Х5,Х8) & Рз (хд,Х2,Х7,Х4) & Рз (х1,хъ,хз,х8) при подстановках

^к, = {х1 : а1, х2 : а2, : аз, х4 : а4, х5 : а5, х6 : а6, х7 : а7, х8 : а8, хд : ад}, Хе, = {Х1 : Ьз, Х2 : Ь7, ж3 : Ь8, Х4 : Ь5, х5 : Ьд, х6 : Ь<2, Х7 : &ь Х8 : Ь4, хд : Ь6}

совпадает с Р1 и Р2 соответственно:

Я(х1 ,х2,хз,х4,х5,х6,х7,х8,хд) = Р1(а1,а2,аз,а4,а5,а6,а7,а8,ад),

Я(Х1 ,Х2, Хз, Х4, Х5, Х6, Х7, Х8, Хд) = Р2(Ь, Ь7, Ь8, Ь5, Ьд, Ь<2, Ь1, Ь4, Ь6).

Следовательно, формулы Р1(а1,а2,аз,а4,а5,а6,а7,а8,ад) и Р2(Ьз,Ь7,Ь8,Ь5, Ьд,Ь2,Ь1,Ь4, Ь6) изоморфны.

В приведённом определении можно было бы обойтись без введения в него формулы Я(х1, ••• ,хп), если написать, что между константами а^, ••• ,а{п и

4 Обозначение Ад, р = {х1 : , • • • , хп : } используется для результата замены всех свободных вхождений переменных Ж1, • • • ,хп в формулу Д на константы а^, • • • , формулы Р соответственно.

, • • • , Ь^ существует взаимно-однозначное соответствие, после применения которого формулы совпадут. Тем не менее, следует отметить, что в дальнейшем данная формула будет выступать именно как формула с переменными. Это необходимо, так как такая формула позволяет задавать общие свойства двух сложных структурированных объектов, что имеет важное значение для дальнейшего анализа этих объектов.

Укажем, что в данном определении и ниже буквы а1,а2,...,ап и Ь1,Ь2,... ,Ьп представляют собой аргументы, которые могут выражать как константы, так и переменные (а также имена более сложных объектов). Переменные обозначаются буквами х1,х2,... , хп. Более того, понятие изоморфизма элементарных конъюнкций атомарных формул в исчислении предикатов не совпадает с понятием их равносильности, поскольку аргументы могут значительно различаться.

Определение 4 [95]. Элементарная конъюнкция, не содержащая констант, называется общим свойством двух объектов, если она изоморфна некоторым подформулам каждого из описаний этих объектов.

Пример 1.1.4. Пусть имеются два объекта, описываемые предикатными формулами Р1 и Р2 соответственно:

Рх (а,1,0,2,йъ, 0>4,0>ь,0>6,0>%,йд) =

Р1(а6,а{) & Р2(а4,ад,а8) &

Рз(«2,аз,ад,а8) & Р3(0,1,0,9,0,4,0,5) & Р3(0^,0^,02,05), (ЬМ, Ьз, Ъ±, Ь5, Ь6, Ьг, Ь8, Ьд) =

Р^А) & р2(ь,ь8,ь5) &

Рз(Ьт,Ь2,Ь6,Ьд) & Рз(Ь1,Ь7,Ь8,Ь5) & Рз(Ь4,Ь8,Ь3,Ьд).

Эти элементарные конъюнкции имеют общую подформулу

К1(х1,х4,х5,х6,х8,хд) = Р1(х6,х1) & Р2(х4,хд,х8) & Рз(х1,хд,х4,х5)

с унификатором для Р2 5

^Дь р2 = {х1 : ЬА, Х4 : Ьз, х5 : Ьд, х6 : Ъ2, Х8 : Ь5, Хд :

так как

^(01,04,0^,0^,0^,0^) & Рз(а2,аз,ад,а8) & Рз(аз,а6,а2,а5), ^2(^1, &2, Ьз, Ь4, Ь5, Ьб, Ь7, Ь8, Ьд) =

Д1(&4, Ьз, Ьд, Ь2, Ь5, Ь8) & Рз(&7, Ь2, Ьб, Ьд) & Рз(&1, Ь7, Ь8, Ь5),

Список литературы диссертационного исследования кандидат наук Чжоу Цзюань, 2025 год

Список литературы

1. Nilsson N. J. Problem-solving methods in artificial intelligence. — New York : McGraw-Hill, 1971. — 284 p.

2. Duda R. O., Hart P. E, Stork D. G. Pattern classification. — Hoboken, NJ : John Wiley & Sons, 2000. — 688 p.

3. Artificial intelligence: a modern approach / S. J. Russell [et al.]. — Fourth edition, global edition. — Harlow : Pearson, 2022. — 1166 p.

4. Kosovskaya T. M. Estimating the number of steps that it takes to solve some problems of pattern recognition which admit logical description // Vestnik St. Petersburg University: Mathematics. — 2007. — Vol. 40, no. 4. — P. 287-293.

5. Косовская Т. М. Некоторые задачи искусственного интеллекта, допускающие формализацию на языке исчисления предикатов, и оценки числа шагов их решения // Труды СПИИРАН. — 2010. — Т. 3, № 14. — С. 58— 75.

6. Du D.-Z., Ko K.-I. Theory of computational complexity. — 2nd ed. — Hoboken, New Jersey : John Wiley & Sons, 2014. — 512 p.

7. Arora S., Barak B. Computational complexity: a modern approach. — Cambridge : Cambridge University Press, 2009. — 605 p.

8. Sipser M. Introduction to the theory of computation. — 3rd ed. — Boston, MA : Cengage Learning, 2012. — 482 p.

9. Косовская Т. М., Косовский Н. Н. Полиномиальная эквивалентность задач изоморфизм предикатных формул и изоморфизм графов // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. — 2019. — Т. 6(64), № 3. — С. 430—439.

10. Kosovskaya T. M. Multilevel descriptions of classes decreasing the number of steps in solving pattern recognition problems described by propositional formulas // Vestnik St. Petersburg University: Mathematics. — 2008. — Vol. 41, no. 1. — P. 21-27.

11. Kosovskaya T. Predicate calculus as a tool for AI problems solution: algorithms and their complexity // Intelligent System. — IntechOpen, 2018. — P. 57-78.

12. Косовская T. M. Многоуровневые описания классов для уменьшения числа шагов решения задач распознавания образов, описываемых формулами исчисления предикатов // Вестник Санкт-Петербургского университета. Сер. 10. Прикладная математика. Информатика. Процессы управления. — 2008. — Т. 10, № 2. — С. 62—70.

13. Kosovskaya T. M. Distributed construction of a level class description in the framework of logic-predicate approach to AI problems // Intelligent Distributed Computing XIII / ed. by I. Kotenko [et al.]. — Cham : Springer International Publishing. — P. 177-182.

14. Косовская Т. М. Частичная выводимость предикатных формул как средство распознавания объектов с неполной информацией // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. — 2009. — Т. 10, № 1. — С. 74—83.

15. Kosovskaya T. Distance between objects described by predicate formulas // International Book Series. Information Science and Computing. Book. — 2012. — Vol. 25. — P. 153-159.

16. Косовская Т. М. Мультиагентное описание сложного объекта по достоверной информации // Компьютерные инструменты в образовании. —. — № 4. — С. 5—18.

17. Гэри М. Р., Джонсон Д. С. Вычислительные машины и труднорешаемые задачи. — М. : Мир, 1982. — 420 с.

18. Косовская Т. М. Построение многоуровневой базы для уменьшения вычислительной сложности решения задачи конъюнктивный булевский запрос // Информационные технологии в управлении (ИТУ). — 2018. — С. 31—36.

19. Kosovskaya Т. М. Самообучающаяся сеть с ячейками, реализующими предикатные формулы // Труды СПИИРАН. — 2015. — Т. 6, № 43. — С. 94— 113.

20. Kosovskaya T. Fuzzy recognition by logic-predicate network // Advances in Science, Technology and Engineering Systems. — 2020. — Vol. 5, no. 4. — P. 686-699.

21. Kosovskaya T. Fuzzy neural networks that change their configuration // Programming and Computer Software. — 2024. — Vol. 50, Suppl 1. — S10-S17.

22. A review of convolutional neural networks in computer vision / X. Zhao [et al.] // Artificial Intelligence Review. — 2024. — Vol. 57, no. 4. — P. 99.

23. Deep neural networks and tabular data: A survey / V. Borisov [et al.] // IEEE Transactions on Neural Networks and Learning Systems. — 2024. — Vol. 35, no. 6. — P. 7499-7519.

24. A survey of uncertainty in deep neural networks / J. Gawlikowski [et al.] // Artificial Intelligence Review. — 2023. — Vol. 56, Suppl 1. — P. 15131589.

25. A survey of bayesian network structure learning / N. K. Kitson [et al.] // Artificial Intelligence Review. — 2023. — Vol. 56, no. 8. — P. 8721-8814.

26. Косовская Т. М., Косовский Н. Н. Выделение общих свойств объектов для создания логических онтологий // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. — 2022. — Т. 18, № 1. — С. 37—51.

27. Kosovskaya T. Isomorphism of predicate formulas in artificial intelligence problems // International Journal "Information Theories and Applications". — 2019. — Vol. 26, no. 3. — P. 221-230.

28. Babai L. Graph isomorphism in quasipolynomial time // Proceedings of the forty-eighth annual ACM symposium on Theory of Computing. — 2016. — P. 684-697.

29. Helfgott H. A., Bajpai J., Dona D. Graph isomorphisms in quasi-polynomial time. — 2017. — URL: https://arxiv.org/abs/1710.04574 (visited on Apr. 2, 2025).

30. Helfgott H. A. Graph isomorphisms in quasi-polynomial time. — 2017. — URL: https://arxiv.org/abs/1701.04372 (visited on Apr. 2, 2025).

31. A (sub)graph isomorphism algorithm for matching large graphs / L. P. Cordella [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2004. — Vol. 26, no. 10. — P. 1367-1372.

32. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3 / V. Carletti [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2018. — Vol. 40, no. 4. — P. 804-818.

33. GLSearch: Maximum common subgraph detection via learning to search / Y. Bai [et al.] // International Conference on Machine Learning. — PMLR, 2021. — P. 588-598.

34. Baghbani A., Bouguila N., Patterson Z. Short-term passenger flow prediction using a bus network graph convolutional long short-term memory neural network model // Transportation Research Record. — 2023. — Vol. 2677, no. 2. — P. 1331-1340.

35. Yao L., Mao C., Luo Y. Graph convolutional networks for text classification // Proceedings of the AAAI conference on artificial intelligence. — 2019. — P. 7370-7377.

36. Dropedge: towards deep graph convolutional networks on node classification / Y. Rong [et al.]. — 2020. — URL: https://arxiv.org/abs/1907. 10903 (visited on Apr. 2, 2025).

37. Chang L., Branco P. Graph-based solutions with residuals for intrusion detection: the modified e-graphsage and e-resgat algorithms. — 2021. — URL: https://arxiv.org/abs/2111.13597 (visited on Apr. 8, 2025).

38. Graph attention networks / P. Velickovic [et al.]. — 2018. — URL: https: //arxiv.org/abs/2111.13597 (visited on Apr. 8, 2025).

39. Hyperbolic graph attention network / Y. Zhang [et al.] // IEEE Transactions on Big Data. — 2021. — Vol. 8, no. 6. — P. 1690-1701.

40. Ye Y, Ji S. Sparse graph attention networks // IEEE Transactions on Knowledge and Data Engineering. — 2021. — Vol. 35, no. 1. — P. 905916.

41. Kgancda: predicting circrna-disease associations based on knowledge graph attention network / W. Lan [et al.] // Briefings in Bioinformatics. — 2022. — Vol. 23, no. 1. — P. 1-13.

42. How powerful are graph neural networks? / K. Xu [et al.]. — 2019. — URL: http://arxiv.org/abs/1810.00826 (visited on Apr. 2, 2025).

43. Kim B.-H., Ye J. C. Understanding graph isomorphism network for rs-fmri functional connectivity analysis // Frontiers in Neuroscience. — 2020. — Vol. 14. — P. 630.

44. Косовская Т. М., Петров Д. А. Выделение наибольшей общей подформулы предикатных формул для решения ряда задач искусственного интеллекта // Вестник Санкт-Петербургского университета. Прикладная математика. Информатика. Процессы управления. — 2017. — Т. 13, № 3. — С. 250—263.

45. Kosovskaya T., Zhou J. Algorithms for checking isomorphism of two elementary conjunctions // Proceedings of Computer Science and Information Technologies 2023 Conference. — Yerevan, Armenia, 2023. — P. 13-16.

46. Kosovskaya T., Zhou J. Algorithms of isomorphism of elementary conjunctions checking // Pattern Recognition and Image Analysis. — 2024. — Vol. 34, no. 1. — P. 102-109.

47. Ebbinghaus H., Flum J., Thomas W. Mathematical logic. — 3rd ed. — Springer International Publishing, 2021. — 304 p.

48. Enderton H. A mathematical introduction to logic. — Burlington, Massachusetts : Academic Press, 2001. — 336 p.

49. Smith P. Beginning mathematical logic: a study guide. — Cambridge : Logic Matters, 2024. — 194 p.

50. Diestel R. Graph theory. — Berlin, Heidelberg : Springer Berlin Heidelberg, 2025. — 466 p.

51. Gross J., Yellen J., Zhang P. Handbook of graph theory. — 2nd ed. — CRC Press LLC, 2014. — 1630 p.

52. Gross J. L., Yellen J., Anderson M. Graph theory and its applications. — 3rd ed. — New York : Chapman, Hall/CRC. — 592 p.

53. Bondy J. A., Murty U. S. R. Graph theory. — Springer Publishing Company, Incorporated, 2008. — 654 p.

54. Guest editorial: deep neural networks for graphs: theory, models, algorithms, and applications / M. Li [et al.] // IEEE Transactions on Neural Networks and Learning Systems. — 2024. — Vol. 35, no. 4. — P. 43674372.

55. Taming verification hardness: an efficient algorithm for testing subgraph isomorphism / H. Shang [et al.] // Proceedings of the VLDB Endowment. — 2008. — Vol. 1, no. 1. — P. 364-375.

56. He H., Singh A. K. Graphs-at-a-time: query language and access methods for graph databases // Proceedings of the 2008 ACM SIGMOD International Conference on Management of Data. — Vancouver Canada : ACM, 2008. — P. 405-418.

57. Zhang S., Li S., Yang J. GADDI: distance index based subgraph matching in biological networks // Proceedings of the 12th international conference on extending database technology: advances in database technology. — Saint Petersburg Russia : ACM, 2009. — P. 192-203.

58. Zhao P., Han J. On graph query optimization in large networks // Proceedings of the VLDB Endowment. — 2010. — Vol. 3, no. 1. — P. 340351.

59. Han W.-S., Lee J., Lee J.-H. Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases // Proceedings of the 2013 ACM SIGMOD International Conference on Management of Data. — 2013. — P. 337-348.

60. Dualiso: An algorithm for subgraph pattern matching on very large labeled graphs / M. Saltz [et al.] // 2014 IEEE International Congress on Big Data. — IEEE, 2014. — P. 498-505.

61. Introducing VF3: A new algorithm for subgraph isomorphism / V. Car-letti [et al.] // Graph-Based Representations in Pattern Recognition: 11th IAPR-TC-15 International Workshop, GbRPR 2017, Anacapri, Italy, May 16-18, Proceedings 11. Vol. 10310 / ed. by P. Foggia, C.-L. Liu, M. Vento. — Cham : Springer International Publishing, 2017. — P. 128139.

62. Asiler M., Yazici A. Bb-graph: A subgraph isomorphism algorithm for efficiently querying big graph databases. — 2017. — URL: http : / / arxiv.org/abs/1706.06654 (visited on Apr. 2, 2025).

63. Abulaish M., Ansari Z. A., Jahiruddin. SubISO: a scalable and novel approach for subgraph isomorphism search in large graph // 11th International Conference on Communication Systems & Networks (COM-SNETS). — Bengaluru, India : IEEE, 2019. — P. 1-8.

64. Yazici A., Ta§komaz E. BF-BigGraph: An efficient subgraph isomorphism approach using machine learning for big graph databases // Information Systems. — 2024. — Vol. 124. — P. 102401.

65. Ullmann J. R. An algorithm for subgraph isomorphism // Journal of the ACM (JACM). — 1976. — Vol. 23, no. 1. — P. 31-42.

66. Ullmann J. R. Bit-vector algorithms for binary constraint satisfaction and subgraph isomorphism // Journal of Experimental Algorithmics (JEA). — 2011. — Vol. 15. — P. 1-64.

67. Development and in silico evaluation of large-scale metabolite identification methods using functional group detection for metabolomics / J. M. Mitchell [et al.] // Frontiers in Genetics. — 2014. — Vol. 5. — P. 1-18.

68. Gouda K., Bujdoso G., Hassaan M. Scaling subgraph matching by improving ullmann algorithm // Computing and Informatics. — 2022. — Vol. 41, no. 4. — P. 1002-1024.

69. Challenging the time complexity of exact subgraph isomorphism for huge and dense graphs with vf3 / V. Carletti [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2017. — Vol. 40, no. 4. — P. 804-818.

70. Juttner A., Madarasi P. VF2++—an improved subgraph isomorphism algorithm // Discrete Applied Mathematics. — 2018. — Vol. 242. — P. 6981.

71. McKay B. D. Nauty user's guide (version 2.4) // Computer Science Dept., Australian National University. — 2009. — P. 1-70.

72. McKay B. D., Piperno A. Practical graph isomorphism, II // Journal of Symbolic Computation. — 2014. — Vol. 60. — P. 94-112.

73. Luks E. M. Lsomorphism of graphs of bounded valence can be tested in polynomial time // Journal of computer and system sciences. — 1982. — Vol. 25, no. 1. — P. 42-65.

74. Grohe M., Schweitzer P. The graph isomorphism problem // Communications of the ACM. — 2020. — Vol. 63, no. 11. — P. 128-134.

75. Graph isomorphism, color refinement, and compactness / V. Arvind [et al.] // computational complexity. — 2017. — Vol. 26, no. 3. — P. 627685.

76. Weisfeiler B., Leman A. The reduction of a graph to canonical form and the algebra which appears therein // Scientific and technical information, Series. — 1968. — Vol. 2, no. 9. — P. 1-9.

77. Weisfeiler and leman go machine learning: the story so far / C. Morris [et al.] // The Journal of Machine Learning Research. — 2023. — Vol. 24, no. 1. — P. 15865-15923.

78. Immerman N., Lander E. Describing graphs: A first-order approach to graph canonization. — New York, NY : Springer New York, 1990. — P. 59-81.

79. Otto M. Bounded variable logics and counting: a study in finite models. — Cambridge University Press, 2017. — 182 с.

80. An efficient heuristic approach to detecting graph isomorphism based on combinations of highly discriminating invariants / M. Dehmer [et al.] // Advances in Computational Mathematics. — 2013. — Vol. 39, no. 2. — P. 311-325.

81. VF3-Light: A lightweight subgraph isomorphism algorithm and its experimental evaluation / V. Carletti [et al.] // Pattern Recognition Letters. — 2019. — Vol. 125. — P. 591-596.

82. Grohe M. The graph isomorphism problem // Proceedings of ACM Symposium on Neural Gaze Detection. — Woodstock, NY., 2018. — P. 19.

83. Graph matching networks for learning the similarity of graph structured objects / Y. Li [et al.] // Proceedings of the 36th International Conference on Machine Learning. Vol. 97 / ed. by K. Chaudhuri, R. Salakhutdinov. — PMLR, 2019. — P. 3835-3845.

84. A strengthened branch and bound algorithm for the maximum common (connected) subgraph problem / J. Zhou [et al.] // Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI-22 / ed. by L. D. Raedt. — International Joint Conferences on Artificial Intelligence Organization, 2022. — P. 1908-1914.

85. Чжоу Ц. Представление степени совпадения входных строк с общим свойством модальными операторами и в трехзначной логике лукасеви-ча // Материалы конференции «Информационные технологии в управле-

нии» (ИТУ) в рамках 15-й мультиконференции по проблемам управления (МКПУ). — СПб. : АО "Концерн «ЦНИИ „Электроприбор"»", 2022. — С. 10—13.

86. Чжоу Ц. Алгоритм проверки на изоморфизм двух элементарных конъюнкций с одним предикатным символом // Материалы 10-й всероссийской научной конференции по проблемам информатики «Системное Программирование, Интеллектуальные Системы, Обеспечение Качества» (СПИСОК). — СПб. : ВВМ, 2023. — С. 1—7.

87. Чжоу Ц., Косовская Т. М. Наибольшая общая подформула двух элементарных конъюнкций с одним предикатным символом // Наука СПбГУ -2023. Сборник материалов Всероссийской конференции по естественным и гуманитарным наукам с международным участием. — СПб. : СПбГУ,

2023. — С. 144—146.

88. Kosovskaya T. M., Zhou J. Algorithm for extraction common properties of objects described in the predicate calculus language with several predicate symbols // Programming and Computer Software. — 2024. — Т. 50, Suppl 1. — S1—S9.

89. Чжоу Ц., Косовская Т. М. Алгоритм выделения общих свойств объектов, описанных на языке исчисления предикатов с одним предикатным символом // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. — 2024. — Т. 11(69), № 4. — С. 733—744.

90. Чжоу Ц. Алгоритм нахождения наибольшего общего подграфа двух ориентированных графов // Компьютерные инструменты в образовании. —

2024. — № 3. — С. 5—13.

91. Косовская Т. М. Сравнение различных представлений знаний для сложных структурированных объектов при решении задач ии // Компьютерные инструменты в образовании. — 2021. — № 2. — С. 41—57.

92. Косовская Т. М. Изоморфизм предикатных формул и его применение для выделения общих свойств сложных структурированных объектов в задачах ии // Всероссийская научная конференция «Математические основы информатики и информационно-коммуникационных систем». Сборник трудов. — Тверь: ТвГУ, 2021. — С. 168—175.

93. Косовская Т. М. Доказательства оценок числа шагов решения некоторых задач распознавания образов, имеющих логические описания // Вестник Санкт-Петербургского университета. Математика. Механика. Астрономия. — 2007. — № 4. — С. 82—90.

94. Косовская Т. М. Формулы исчисления предикатов для представления знаний о сложных структурированных объектах // Материалы конференции «Информационные технологии в управлении» (ИТУ) в рамках 15-й муль-тиконференции по проблемам управления (МКПУ). — Санкт-Петербург : АО "Концерн «ЦНИИ „Электроприбор"»", 2022. — С. 9—12.

95. Косовская Т. М. Логико-предметный подход к решению задач искусственного интеллекта для сложных структурированных объектов: учебное пособие. — М. : Ай Пи Ар Медиа, 2023. — 119 с.

96. Kosovskaya T. Aggregation of information from various agents in terms of predicate formulas // AIP Conference Proceedings. — 2023. — Vol. 2757, no. 1. — P. 040004.

97. Matthes E. Python crash course: a hands-on, project-based introduction to programming. — 3rd ed. — San Francisco, CA : No Starch Press, 2023. — 554 p.

98. A survey on hypergraph representation learning / A. Antelmi [et al.] // ACM Computing Surveys. — 2024. — Vol. 56, no. 1. — P. 1-38.

99. Hypergraph isomorphism computation / Y. Feng [et al.] // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2024. — Vol. 46, no. 5. — P. 3880-3896.

100. Bretto A. Hypergraph theory: an introduction. — Cham, Switzerland : Springer International Publishing, 2013. — 129 p.

101. Chodrow P. S., Veldt N., Benson A. R. Generative hypergraph clustering: from blockmodels to modularity // Science Advances. — 2021. — Vol. 7, no. 28. — eabh1303.