TY - JOUR

T1 - Algorithm for Extraction Common Properties of Objects Described in the Predicate Calculus Language with Several Predicate Symbols

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

AU - Чжоу, Цзюань

PY - 2024/11

Y1 - 2024/11

N2 - Abstract: In artificial intelligence problems, connected with the study of complex structured objects which are described in the terms of properties of their elements and relationships between these elements, it is convenient to use predicate calculus formulas, more precisely elementary conjunctions of atomic predicate formulas. In such a case, the problem of extraction common properties of objects arises. The common properties of complex structured objects are set by formulas with variables as arguments, which, up to the names of the arguments, coincide with the subformulas of the objects under study, that is, are isomorphic to these subformulas. Previously, the authors developed algorithms for checking such formulas for isomorphism, as well as for extraction the maximal common subformula of two elementary conjunctions of predicate formulas with a single predicate symbol. Two algorithms, the first of which solves this problem for elementary conjunctions containing two predicate symbols, and the second for an arbitrary number of predicate symbols are proposed in this paper using the last-mentioned algorithm. Estimates of the computational complexity of the presented algorithms are proved. The algorithm is implemented in Python.

AB - Abstract: In artificial intelligence problems, connected with the study of complex structured objects which are described in the terms of properties of their elements and relationships between these elements, it is convenient to use predicate calculus formulas, more precisely elementary conjunctions of atomic predicate formulas. In such a case, the problem of extraction common properties of objects arises. The common properties of complex structured objects are set by formulas with variables as arguments, which, up to the names of the arguments, coincide with the subformulas of the objects under study, that is, are isomorphic to these subformulas. Previously, the authors developed algorithms for checking such formulas for isomorphism, as well as for extraction the maximal common subformula of two elementary conjunctions of predicate formulas with a single predicate symbol. Two algorithms, the first of which solves this problem for elementary conjunctions containing two predicate symbols, and the second for an arbitrary number of predicate symbols are proposed in this paper using the last-mentioned algorithm. Estimates of the computational complexity of the presented algorithms are proved. The algorithm is implemented in Python.

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

KW - максимальная общая подформула

KW - унификатор предикатных формул

KW - isomorphism of elementary conjunctions of predicate formulas

KW - maximal common subformula

KW - unifier of predicate formulas

UR - https://www.mendeley.com/catalogue/df634b23-10a7-3441-9079-88eeca7a0350/

U2 - 10.1134/s0361768824700348

DO - 10.1134/s0361768824700348

M3 - Article

VL - 50

SP - S1-S9

JO - Programming and Computer Software

JF - Programming and Computer Software

SN - 0361-7688

IS - Suppl 1

ER -