|
Sibirskii Matematicheskii Zhurnal, 2010, Volume 51, Number 4, Pages 838–847
(Mi smj2129)
|
|
|
|
This article is cited in 5 scientific papers (total in 5 papers)
On decidability of the decomposability problem for finite theories
A. S. Morozova, D. K. Ponomaryovb a Sobolev Institute of Mathematics, Novosibirsk, Russia
b Institute of Informatics Systems, Novosibirsk, Russia
Abstract:
We consider the decomposability problem for elementary theories, i.e. the problem of deciding whether a theory has a nontrivial representation as a union of two (or several) theories in disjoint signatures. For finite universal Horn theories, we prove that the decomposability problem is $\Sigma _1^0$-complete and, thus, undecidable. We also demonstrate that the decomposability problem is decidable for finite theories in signatures consisting only of monadic predicates and constants.
Keywords:
decomposable theory, decomposition of a theory, Horn theory, logic programming, monadic logic.
Received: 09.10.2008
Citation:
A. S. Morozov, D. K. Ponomaryov, “On decidability of the decomposability problem for finite theories”, Sibirsk. Mat. Zh., 51:4 (2010), 838–847; Siberian Math. J., 51:4 (2010), 667–674
Linking options:
https://www.mathnet.ru/eng/smj2129 https://www.mathnet.ru/eng/smj/v51/i4/p838
|
Statistics & downloads: |
Abstract page: | 304 | Full-text PDF : | 85 | References: | 38 |
|