|
Zapiski Nauchnykh Seminarov POMI, 2004, Volume 316, Pages 147–162
(Mi znsl730)
|
|
|
|
A new decidable Horn fragment of the predicate calculus
V. P. Orevkov St. Petersburg Department of V. A. Steklov Institute of Mathematics, Russian Academy of Sciences
Abstract:
We describe an extension of the class $\forall\exists$ of Horn formulas in the predicate calculus. We prove the decidability of this class. We describe complexity characteristics such that fixing them splits this extended class into polynomially decidable subclasses. If one fixes the maximum arity of predicates, our class splits into subclasses belonging to NP.
Received: 02.12.2004
Citation:
V. P. Orevkov, “A new decidable Horn fragment of the predicate calculus”, Computational complexity theory. Part IX, Zap. Nauchn. Sem. POMI, 316, POMI, St. Petersburg, 2004, 147–162; J. Math. Sci. (N. Y.), 134:5 (2006), 2403–2410
Linking options:
https://www.mathnet.ru/eng/znsl730 https://www.mathnet.ru/eng/znsl/v316/p147
|
Statistics & downloads: |
Abstract page: | 250 | Full-text PDF : | 87 | References: | 42 |
|