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

被引：0
作者：
D. Ponomaryov
机构：
[1] Ershov Institute of Informatics Systems,
[2] Novosibirsk State University,undefined
来源：
Lobachevskii Journal of Mathematics | 2021年 / 42卷
关键词：
decomposition; decidability; computational complexity;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
引用
收藏
页码：2905 / 2912
页数：7
相关论文
共 50 条
[31]   On the Mints Hierarchy in First-Order Intuitionistic Logic [J].
Schubert, Aleksy ;
Urzyczyn, Pawel ;
Zdanowski, Konrad .
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES (FOSSACS 2015), 2015, 9034 :451-465
[32]   First-order concatenation theory with bounded quantifiers [J].
Kristiansen, Lars ;
Murwanashyaka, Juvenal .
ARCHIVE FOR MATHEMATICAL LOGIC, 2021, 60 (1-2) :77-104
[33]   ON THE MINTS HIERARCHY IN FIRST-ORDER INTUITIONISTIC LOGIC [J].
Schubert, Aleksy ;
Urzyczyn, Pawel ;
Zdanowski, Konrad .
LOGICAL METHODS IN COMPUTER SCIENCE, 2016, 12 (04)
[34]   Prenex universal first-order safety properties [J].
Dundua, Besik ;
Kapanadze, Ioane ;
Seidl, Helmut .
INFORMATION PROCESSING LETTERS, 2024, 186
[35]   On A New Semantics for First-Order Predicate Logic [J].
Andreka, Hajnal ;
van Benthem, Johan ;
Nemeti, Istvan .
JOURNAL OF PHILOSOPHICAL LOGIC, 2017, 46 (03) :259-267
[36]   First-order factors of linear Mahler operators ☆ [J].
Chyzak, Frederic ;
Dreyfus, Thomas ;
Dumas, Philippe ;
Mezzarobba, Marc .
JOURNAL OF SYMBOLIC COMPUTATION, 2025, 130
[37]   Stratified Guarded First-Order Transition Systems [J].
Mueller, Christan ;
Seidl, Helmut .
STATIC ANALYSIS (SAS 2020), 2020, 12389 :113-133
[38]   On A New Semantics for First-Order Predicate Logic [J].
Hajnal Andréka ;
Johan van Benthem ;
István Németi .
Journal of Philosophical Logic, 2017, 46 :259-267
[39]   Craig Interpolation for Decidable First-Order Fragments [J].
ten Cate, Balder ;
Comer, Jesse .
FOUNDATIONS OF SOFTWARE SCIENCE AND COMPUTATION STRUCTURES, PT II, FOSSACS 2024, 2024, 14575 :137-159
[40]   Decidable fragments of first-order temporal logics [J].
Hodkinson, I ;
Wolter, F ;
Zakharyaschev, M .
ANNALS OF PURE AND APPLIED LOGIC, 2000, 106 (1-3) :85-134
12345