Back to Search
Start Over
Complexity of Existential Positive First-Order Logic
- Source :
- Journal of Logic and Computation, Journal of Logic and Computation, Oxford University Press (OUP), 2013, 23 (4), pp.753-760. ⟨10.1093/logcom/exr043⟩, Journal of Logic and Computation, 2013, 23 (4), pp.753-760. ⟨10.1093/logcom/exr043⟩
- Publication Year :
- 2013
- Publisher :
- HAL CCSD, 2013.
-
Abstract
- Let gamma be a (not necessarily finite) structure with a finite relational signature. We prove that deciding whether a given existential positive sentence holds in gamma is in Logspace or complete for the class CSP(gamma)_NP under deterministic polynomial-time many-one reductions. Here, CSP(gamma)_NP is the class of problems that can be reduced to the Constraint Satisfaction Problem of gamma under non-deterministic polynomial-time many-one reductions.<br />Comment: 8 pages
- Subjects :
- FOS: Computer and information sciences
[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]
Computer Science - Logic in Computer Science
Class (set theory)
Computational Complexity
Computational complexity theory
Logic
Astrophysics::High Energy Astrophysical Phenomena
Structure (category theory)
Constraint Satisfaction Problems
0102 computer and information sciences
02 engineering and technology
Computer Science::Computational Complexity
Computational Complexity (cs.CC)
01 natural sciences
Theoretical Computer Science
Combinatorics
Arts and Humanities (miscellaneous)
Computer Science::Logic in Computer Science
Constraint logic programming
ComputingMethodologies_SYMBOLICANDALGEBRAICMANIPULATION
0202 electrical engineering, electronic engineering, information engineering
Hardware_ARITHMETICANDLOGICSTRUCTURES
Constraint satisfaction problem
Mathematics
Discrete mathematics
Existential Positive First-Order Logic
[INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
16. Peace & justice
Signature (logic)
First-order logic
Logic in Computer Science (cs.LO)
Computer Science - Computational Complexity
010201 computation theory & mathematics
Hardware and Architecture
[INFO.INFO-IR]Computer Science [cs]/Information Retrieval [cs.IR]
020201 artificial intelligence & image processing
Software
Sentence
Subjects
Details
- Language :
- English
- ISSN :
- 0955792X and 1465363X
- Database :
- OpenAIRE
- Journal :
- Journal of Logic and Computation, Journal of Logic and Computation, Oxford University Press (OUP), 2013, 23 (4), pp.753-760. ⟨10.1093/logcom/exr043⟩, Journal of Logic and Computation, 2013, 23 (4), pp.753-760. ⟨10.1093/logcom/exr043⟩
- Accession number :
- edsair.doi.dedup.....356770440c4f1146a8afd6d4aa3583a0
- Full Text :
- https://doi.org/10.1093/logcom/exr043⟩