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

被引：0
|
作者：
Ponomaryov, D. [1 ]
机构：
[1] Novosibirsk State Univ, Ershov Inst Informat Syst, Novosibirsk 630090, Russia
来源：
LOBACHEVSKII JOURNAL OF MATHEMATICS | 2021年 / 42卷 / 12期
关键词：
decomposition; decidability; computational complexity;
D O I：
10.1134/S199508022112026X
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
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.
引用
收藏
页码：2905 / 2912
页数：8
相关论文
共 50 条
  • [1] On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories
    D. Ponomaryov
    Lobachevskii Journal of Mathematics, 2021, 42 : 2905 - 2912
  • [2] GENERIC COMPLEXITY OF FIRST-ORDER THEORIES
    Rybalov, A. N.
    SIBERIAN ELECTRONIC MATHEMATICAL REPORTS-SIBIRSKIE ELEKTRONNYE MATEMATICHESKIE IZVESTIYA, 2011, 8 : 168 - 178
  • [3] Decidability of first-order theories for groups and monoids of integral matrices
    Nagrebetskaya Yu.V.
    Algebra and Logic, 2000, 39 (4) : 276 - 291
  • [4] Combination of Decomposability and Propagation for Solving First-Order Constraints in Decomposable Theories
    Djelloul, Khalil
    APPLIED COMPUTING 2008, VOLS 1-3, 2008, : 1728 - 1732
  • [5] The Complexity of Decomposing Modal and First-Order Theories
    Goeller, Stefan
    Jung, Jean Christoph
    Lohrey, Markus
    2012 27TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2012, : 325 - 334
  • [6] The Complexity of Decomposing Modal and First-Order Theories
    Goeller, Stefan
    Jung, Jean-Christoph
    Lohrey, Markus
    ACM TRANSACTIONS ON COMPUTATIONAL LOGIC, 2015, 16 (01)
  • [7] Decidability, Complexity, and Expressiveness of First-Order Logic Over the Subword Ordering
    Halfon, Simon
    Schnoebelen, Philippe
    Zetzsche, Georg
    2017 32ND ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2017,
  • [8] On decidability of the decomposability problem for finite theories
    Morozov, A. S.
    Ponomaryov, D. K.
    SIBERIAN MATHEMATICAL JOURNAL, 2010, 51 (04) : 667 - 674
  • [9] On decidability of the decomposability problem for finite theories
    Andrey S. Morozov
    Denis K. Ponomaryov
    Siberian Mathematical Journal, 2010, 51 : 667 - 674
  • [10] Decidability Results in First-Order Epistemic Planning
    Liberman, Andres Occhipinti
    Rendsvig, Rasmus Kraemmer
    PROCEEDINGS OF THE TWENTY-NINTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, 2020, : 4161 - 4167
12345