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 -