Affordable Access

Access to the full text

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

Authors
  • Ponomaryov, D.1
  • 1 Ershov Institute of Informatics Systems, Novosibirsk State University, Novosibirsk, 630090, Russia , Novosibirsk (Russia)
Type
Published Article
Journal
Lobachevskii Journal of Mathematics
Publisher
Pleiades Publishing
Publication Date
Dec 13, 2021
Volume
42
Issue
12
Pages
2905–2912
Identifiers
DOI: 10.1134/S199508022112026X
Source
Springer Nature
Keywords
Disciplines
  • Article
License
Yellow

Abstract

AbstractWe consider the decomposability problem, i.e., the problem to decide whether a logical theory \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{T}}$$\end{document} is equivalent to a union of two (or several) components in signatures, which correspond to a partition of the signature of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal{T}}$$\end{document} ‘‘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.

Report this publication

Statistics

Seen <100 times