Algorithms of Isomorphism of Elementary Conjunctions Checking

Standard

Algorithms of Isomorphism of Elementary Conjunctions Checking. / Косовская, Татьяна Матвеевна ; Чжоу, Цзюань.

In: Pattern Recognition and Image Analysis, Vol. 34, No. 1, 01.03.2024, p. 102–109.

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

BibTeX

@article{d075a5a7a80d473ca10abb9ebe00f374,

title = "Algorithms of Isomorphism of Elementary Conjunctions Checking",

abstract = "When solving artificial intelligence problems related to the study of complex structured objects, a convenient tool for describing such objects is the language of predicate calculus. The paper presents two algorithms for checking the isomorphism of pairs of elementary conjunctions of predicate formulas (they coincide up to variable names and the order of conjunctive terms). The first of the algorithms checks elementary conjunctions containing a single predicate symbol for isomorphism. Furthermore, if the formulas are isomorphic, it finds a one-to-one correspondence between the arguments of these formulas. If all predicates are binary, the proposed algorithm is an algorithm for checking two directed graphs for isomorphism. The second algorithm checks elementary conjunctions containing multiple predicate symbols for isomorphism. Estimates of their time complexity are given for both algorithms.",

keywords = "complex structured object, isomorphism of predicate formulas, predicate formulas",

author = "Косовская, {Татьяна Матвеевна} and Цзюань Чжоу",

year = "2024",

month = mar,

day = "1",

doi = "10.1134/s1054661824010103",

language = "English",

volume = "34",

pages = "102–109",

journal = "Pattern Recognition and Image Analysis",

issn = "1054-6618",

publisher = "МАИК {"}Наука/Интерпериодика{"}",

number = "1",

}

RIS

TY - JOUR

T1 - Algorithms of Isomorphism of Elementary Conjunctions Checking

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

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

PY - 2024/3/1

Y1 - 2024/3/1

N2 - When solving artificial intelligence problems related to the study of complex structured objects, a convenient tool for describing such objects is the language of predicate calculus. The paper presents two algorithms for checking the isomorphism of pairs of elementary conjunctions of predicate formulas (they coincide up to variable names and the order of conjunctive terms). The first of the algorithms checks elementary conjunctions containing a single predicate symbol for isomorphism. Furthermore, if the formulas are isomorphic, it finds a one-to-one correspondence between the arguments of these formulas. If all predicates are binary, the proposed algorithm is an algorithm for checking two directed graphs for isomorphism. The second algorithm checks elementary conjunctions containing multiple predicate symbols for isomorphism. Estimates of their time complexity are given for both algorithms.

AB - When solving artificial intelligence problems related to the study of complex structured objects, a convenient tool for describing such objects is the language of predicate calculus. The paper presents two algorithms for checking the isomorphism of pairs of elementary conjunctions of predicate formulas (they coincide up to variable names and the order of conjunctive terms). The first of the algorithms checks elementary conjunctions containing a single predicate symbol for isomorphism. Furthermore, if the formulas are isomorphic, it finds a one-to-one correspondence between the arguments of these formulas. If all predicates are binary, the proposed algorithm is an algorithm for checking two directed graphs for isomorphism. The second algorithm checks elementary conjunctions containing multiple predicate symbols for isomorphism. Estimates of their time complexity are given for both algorithms.

KW - complex structured object

KW - isomorphism of predicate formulas

KW - predicate formulas

UR - https://www.mendeley.com/catalogue/99406111-9e84-3e16-a8db-cf9bbe6679cd/

U2 - 10.1134/s1054661824010103

DO - 10.1134/s1054661824010103

M3 - Article

VL - 34

SP - 102

EP - 109

JO - Pattern Recognition and Image Analysis

JF - Pattern Recognition and Image Analysis

SN - 1054-6618

IS - 1

ER -

ID: 119001653