Algorithms for Checking Isomorphism of Two Elementary Conjunctiоns

Standard

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

Proceedings of Computer Science and Information Technologies 2023 Conference. 2023.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Косовская, ТМ & Чжоу, Ц 2023, Algorithms for Checking Isomorphism of Two Elementary Conjunctiоns. in Proceedings of Computer Science and Information Technologies 2023 Conference. 14th International Conference on Computer Science and Information Technologies CSIT 2023, Ереван, Armenia, 25/09/23. https://doi.org/10.51408/csit2023_01

BibTeX

@inproceedings{2bb620e214f245f684b725fed0d9c55d,

title = "Algorithms for Checking Isomorphism of Two Elementary Conjunctiоns",

abstract = "When solving AI problems related to the study of complex structured objects, a convenient tool for describing such objects is the predicate calculus language. The paper presents two algorithms for checking two elementary conjunctions of predicate formulas for isomorphism (matches up to the names of variables and the order of conjunctive terms). The first of the algorithms checks for isomorphism elementary conjunctions containing a single predicate symbol. In addition, if the formulas are isomorphic, then 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 for isomorphism elementary conjunctions containing several predicate symbols. Estimates of their time complexity are given for both algorithms.",

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

year = "2023",

month = sep,

day = "14",

doi = "10.51408/csit2023_01",

language = "English",

booktitle = "Proceedings of Computer Science and Information Technologies 2023 Conference",

note = "14th International Conference on Computer Science and Information Technologies CSIT 2023 ; Conference date: 25-09-2023 Through 30-09-2023",

}

RIS

TY - GEN

T1 - Algorithms for Checking Isomorphism of Two Elementary Conjunctiоns

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

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

PY - 2023/9/14

Y1 - 2023/9/14

N2 - When solving AI problems related to the study of complex structured objects, a convenient tool for describing such objects is the predicate calculus language. The paper presents two algorithms for checking two elementary conjunctions of predicate formulas for isomorphism (matches up to the names of variables and the order of conjunctive terms). The first of the algorithms checks for isomorphism elementary conjunctions containing a single predicate symbol. In addition, if the formulas are isomorphic, then 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 for isomorphism elementary conjunctions containing several predicate symbols. Estimates of their time complexity are given for both algorithms.

AB - When solving AI problems related to the study of complex structured objects, a convenient tool for describing such objects is the predicate calculus language. The paper presents two algorithms for checking two elementary conjunctions of predicate formulas for isomorphism (matches up to the names of variables and the order of conjunctive terms). The first of the algorithms checks for isomorphism elementary conjunctions containing a single predicate symbol. In addition, if the formulas are isomorphic, then 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 for isomorphism elementary conjunctions containing several predicate symbols. Estimates of their time complexity are given for both algorithms.

UR - https://www.mendeley.com/catalogue/6e618ae9-26e6-3579-a154-ed264b2cd059/

U2 - 10.51408/csit2023_01

DO - 10.51408/csit2023_01

M3 - Conference contribution

BT - Proceedings of Computer Science and Information Technologies 2023 Conference

T2 - 14th International Conference on Computer Science and Information Technologies CSIT 2023

Y2 - 25 September 2023 through 30 September 2023

ER -

ID: 112562463