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

D. Ponomaryov

Research output: Contribution to journalArticlepeer-review

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 ‘‘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.

Original languageEnglish
Article number24
Pages (from-to)2905-2912
Number of pages8
JournalLobachevskii Journal of Mathematics
Volume42
Issue number12
DOIs
Publication statusPublished - Dec 2021

Keywords

  • computational complexity
  • decidability
  • decomposition

OECD FOS+WOS

  • 1.01 MATHEMATICS

State classification of scientific and technological information

  • 27 MATHEMATICS

Fingerprint

Dive into the research topics of 'On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories'. Together they form a unique fingerprint.

Cite this