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

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 -