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

D. Ponomaryov

Результат исследования: Научные публикации в периодических изданияхстатьярецензирование

Аннотация

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.

Язык оригиналаанглийский
Номер статьи24
Страницы (с-по)2905-2912
Число страниц8
ЖурналLobachevskii Journal of Mathematics
Том42
Номер выпуска12
DOI
СостояниеОпубликовано - дек 2021

Предметные области OECD FOS+WOS

  • 1.01 МАТЕМАТИКА

ГРНТИ

  • 27 МАТЕМАТИКА

Fingerprint

Подробные сведения о темах исследования «On the Relationship Between the Complexity of Decidability and Decomposability of First-Order Theories». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать