Research output: Contribution to journal › Article › peer-review
Algorithm for Extracting the Common Properties of Objects Described in the Predicate Calculus Language with a Single Predicate Symbol. / Zhou, J.; Kosovskaya, T.M.
In: Vestnik St. Petersburg University: Mathematics, Vol. 57, No. 4, 2024, p. 514-522.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Algorithm for Extracting the Common Properties of Objects Described in the Predicate Calculus Language with a Single Predicate Symbol
AU - Zhou, J.
AU - Kosovskaya, T.M.
N1 - Export Date: 01 November 2025; Cited By: 0; Correspondence Address: J. Zhou; St. Petersburg State University, St. Petersburg, 199034, Russian Federation; email: st103098@student.spbu.ru; T.M. Kosovskaya; St. Petersburg State University, St. Petersburg, 199034, Russian Federation; email: kosovtm@gmail.com
PY - 2024
Y1 - 2024
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 extracting the 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. In the case of a single predicate symbol in the descriptions of objects, the problem under consideration is polynomial equivalent to the NP-hard problem of extracting the largest common subgraph of two graphs. An algorithm for finding the largest (in terms of the number of literals) subformula with variables as arguments, isomorphic to the subformulas of two elementary conjunctions of predicate formulas containing a single predicate symbol is proposed in this work. Estimates of the computational complexity of the proposed algorithm are proved. The algorithm is implemented in Python. © 2025 Elsevier B.V., All rights reserved.
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 extracting the 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. In the case of a single predicate symbol in the descriptions of objects, the problem under consideration is polynomial equivalent to the NP-hard problem of extracting the largest common subgraph of two graphs. An algorithm for finding the largest (in terms of the number of literals) subformula with variables as arguments, isomorphic to the subformulas of two elementary conjunctions of predicate formulas containing a single predicate symbol is proposed in this work. Estimates of the computational complexity of the proposed algorithm are proved. The algorithm is implemented in Python. © 2025 Elsevier B.V., All rights reserved.
KW - isomorphism of elementary conjunctions of predicate formulas
KW - maximal common subformula
KW - unifier of predicate formulas
U2 - 10.1134/S1063454124700353
DO - 10.1134/S1063454124700353
M3 - статья
VL - 57
SP - 514
EP - 522
JO - Vestnik St. Petersburg University: Mathematics
JF - Vestnik St. Petersburg University: Mathematics
SN - 1063-4541
IS - 4
ER -
ID: 143367907