Standard

On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories. / Ponomaryov, D.

In: Lobachevskii Journal of Mathematics, Vol. 42, No. 12, 24, 12.2021, p. 2905-2912.

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

Harvard

Ponomaryov, D 2021, 'On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories', Lobachevskii Journal of Mathematics, vol. 42, no. 12, 24, pp. 2905-2912. https://doi.org/10.1134/S199508022112026X

APA

Ponomaryov, D. (2021). On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories. Lobachevskii Journal of Mathematics, 42(12), 2905-2912. [24]. https://doi.org/10.1134/S199508022112026X

Vancouver

Ponomaryov D. On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories. Lobachevskii Journal of Mathematics. 2021 Dec;42(12):2905-2912. 24. doi: 10.1134/S199508022112026X

Author

Ponomaryov, D. / On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories. In: Lobachevskii Journal of Mathematics. 2021 ; Vol. 42, No. 12. pp. 2905-2912.

BibTeX

@article{d3fc86c12cd34703bea7954d267f7afa,
title = "On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories",
abstract = "We consider the decomposability problem, i.e., the problem to decide whether a logical theory T is equivalent to a union of two (or several) components in signatures, which correspond to a partition of the signature of T {\textquoteleft}{\textquoteleft}modulo'' a given shared subset of symbols. We introduce several tools for proving that the computational complexity of this problem coincides with the complexity of entailment. As an application of these tools we derive tight bounds for the complexity of decomposability of theories in signature fragments of first-order logic, i.e., those fragments, which are obtained by restricting signature.",
keywords = "computational complexity, decidability, decomposition",
author = "D. Ponomaryov",
note = "Funding Information: The work was supported by the Mathematical Center in Akademgorodok under Agreement no. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation. Publisher Copyright: {\textcopyright} 2021, Pleiades Publishing, Ltd.",
year = "2021",
month = dec,
doi = "10.1134/S199508022112026X",
language = "English",
volume = "42",
pages = "2905--2912",
journal = "Lobachevskii Journal of Mathematics",
issn = "1995-0802",
publisher = "Maik Nauka Publishing / Springer SBM",
number = "12",

}

RIS

TY - JOUR

T1 - On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories

AU - Ponomaryov, D.

N1 - Funding Information: The work was supported by the Mathematical Center in Akademgorodok under Agreement no. 075-15-2019-1675 with the Ministry of Science and Higher Education of the Russian Federation. Publisher Copyright: © 2021, Pleiades Publishing, Ltd.

PY - 2021/12

Y1 - 2021/12

N2 - We consider the decomposability problem, i.e., the problem to decide whether a logical theory T is equivalent to a union of two (or several) components in signatures, which correspond to a partition of the signature of T ‘‘modulo'' a given shared subset of symbols. We introduce several tools for proving that the computational complexity of this problem coincides with the complexity of entailment. As an application of these tools we derive tight bounds for the complexity of decomposability of theories in signature fragments of first-order logic, i.e., those fragments, which are obtained by restricting signature.

AB - We consider the decomposability problem, i.e., the problem to decide whether a logical theory T is equivalent to a union of two (or several) components in signatures, which correspond to a partition of the signature of T ‘‘modulo'' a given shared subset of symbols. We introduce several tools for proving that the computational complexity of this problem coincides with the complexity of entailment. As an application of these tools we derive tight bounds for the complexity of decomposability of theories in signature fragments of first-order logic, i.e., those fragments, which are obtained by restricting signature.

KW - computational complexity

KW - decidability

KW - decomposition

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

UR - https://www.elibrary.ru/item.asp?id=47327859

UR - https://www.mendeley.com/catalogue/daaa971a-86be-36bc-bdc7-917144abc390/

U2 - 10.1134/S199508022112026X

DO - 10.1134/S199508022112026X

M3 - Article

AN - SCOPUS:85121349848

VL - 42

SP - 2905

EP - 2912

JO - Lobachevskii Journal of Mathematics

JF - Lobachevskii Journal of Mathematics

SN - 1995-0802

IS - 12

M1 - 24

ER -

ID: 35259346