Standard

Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis. / Kosovskaya, T.M.; Kosovskii, N.N.

In: Vestnik St. Petersburg University: Mathematics, Vol. 52, No. 3, 09.2019, p. 286–292.

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

Harvard

Kosovskaya, TM & Kosovskii, NN 2019, 'Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis', Vestnik St. Petersburg University: Mathematics, vol. 52, no. 3, pp. 286–292. https://doi.org/10.1134/S1063454119030105

APA

Kosovskaya, T. M., & Kosovskii, N. N. (2019). Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis. Vestnik St. Petersburg University: Mathematics, 52(3), 286–292. https://doi.org/10.1134/S1063454119030105

Vancouver

Kosovskaya TM, Kosovskii NN. Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis. Vestnik St. Petersburg University: Mathematics. 2019 Sep;52(3):286–292. https://doi.org/10.1134/S1063454119030105

Author

Kosovskaya, T.M. ; Kosovskii, N.N. / Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis. In: Vestnik St. Petersburg University: Mathematics. 2019 ; Vol. 52, No. 3. pp. 286–292.

BibTeX

@article{b0a97bec783143718cbb2fa98664c666,
title = "Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis",
abstract = "The problem of isomorphism checking of two elementary conjunctions of predicate formulas is considered in this work. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. The exact definition of the concept of isomorphism of such formulas is given in this paper. However, isomorphic elementary conjunctions of predicate formulas are formulas that, with some substitution of variables instead of their arguments, coincide with the accuracy of the order of writing literals. Problems are described that, when solved, mean the necessity of testing formulas for isomorphism arises. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.",
keywords = "GI-completeness, graph isomorphism, predicate formulas isomorphism",
author = "T.M. Kosovskaya and N.N. Kosovskii",
note = "Kosovskaya, T.M. & Kosovskii, N.N. Vestnik St.Petersb. Univ.Math. (2019) 52: 286. https://proxy.library.spbu.ru:2060/10.1134/S1063454119030105",
year = "2019",
month = sep,
doi = "10.1134/S1063454119030105",
language = "English",
volume = "52",
pages = "286–292",
journal = "Vestnik St. Petersburg University: Mathematics",
issn = "1063-4541",
publisher = "Pleiades Publishing",
number = "3",

}

RIS

TY - JOUR

T1 - Polynomial Equivalence of the Problems Predicate Formulas Isomorphism and Graph Isomorphis

AU - Kosovskaya, T.M.

AU - Kosovskii, N.N.

N1 - Kosovskaya, T.M. & Kosovskii, N.N. Vestnik St.Petersb. Univ.Math. (2019) 52: 286. https://proxy.library.spbu.ru:2060/10.1134/S1063454119030105

PY - 2019/9

Y1 - 2019/9

N2 - The problem of isomorphism checking of two elementary conjunctions of predicate formulas is considered in this work. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. The exact definition of the concept of isomorphism of such formulas is given in this paper. However, isomorphic elementary conjunctions of predicate formulas are formulas that, with some substitution of variables instead of their arguments, coincide with the accuracy of the order of writing literals. Problems are described that, when solved, mean the necessity of testing formulas for isomorphism arises. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.

AB - The problem of isomorphism checking of two elementary conjunctions of predicate formulas is considered in this work. Such a problem appears while solving some Artificial Intelligence problems, admitting formalization by means of predicate calculus language. The exact definition of the concept of isomorphism of such formulas is given in this paper. However, isomorphic elementary conjunctions of predicate formulas are formulas that, with some substitution of variables instead of their arguments, coincide with the accuracy of the order of writing literals. Problems are described that, when solved, mean the necessity of testing formulas for isomorphism arises. Polynomial equivalence of this problem with the Graph Isomorphism (GI) problem is proved.

KW - GI-completeness

KW - graph isomorphism

KW - predicate formulas isomorphism

UR - https://link.springer.com/article/10.1134/S1063454119030105

UR - http://www.scopus.com/inward/record.url?scp=85071982220&partnerID=8YFLogxK

U2 - 10.1134/S1063454119030105

DO - 10.1134/S1063454119030105

M3 - Article

VL - 52

SP - 286

EP - 292

JO - Vestnik St. Petersburg University: Mathematics

JF - Vestnik St. Petersburg University: Mathematics

SN - 1063-4541

IS - 3

ER -

ID: 46130767