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

Аннотация

В задачах искусственного интеллекта, где исследуются сложные структурированные объекты, которые задаются свойствами своих элементов и отношениями между этими элементами, удобно использовать формулы исчисления предикатов, точнее элементарные конъюнкции атомарных предикатных формул. При этом встает задача выделения общих свойств таких объектов. Общие свойства сложных составных объектов задаются максимальными по количеству литералов формулами с переменными в качестве аргументов, которые с точностью до имен аргументов совпадают с подформулами исследуемых объектов, т. е. изоморфны этим подформулам. Задача проверки элементарных конъюнкций предикатных формул на изоморфизм является GI-полной задачей, т. е. полиномиально эквивалентна "открытой" задаче проверки двух графов на изоморфизм. Ранее авторами были разработаны алгоритмы проверки таких формул на изоморфизм. В настоящей статье предложен алгоритм нахождения наибольшей по количеству литералов подформулы с переменными в качестве аргументов, изоморфной подформулам двух элементарных конъюнкций предикатных формул, содержащих единственный предикатный символ. В такой постановке рассматриваемая задача полиномиально эквивалентна NP-трудной задаче выделения наибольшего общего подграфа двух графов. В частности, задача выделения наибольшего общего подграфа двух ориентированных графов является частным случаем рассматриваемой в статье задачи при условии, что предикатный символ двуместный. Задача выделения наибольшего общего подграфа двух графов является частным случаем рассматриваемой в статье задачи при условии, что предикатный символ двуместный и вместе с литералом P(x, y) всегда присутствует литерал P(y, x). Доказаны оценки вычислительной сложности предложенного алгоритма. Алгоритм реализован на языке Python.

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

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