Henkin quantifiers and complete problems (Q1088983)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Henkin quantifiers and complete problems |
scientific article |
Statements
Henkin quantifiers and complete problems (English)
0 references
1986
0 references
The authors analyze computational aspects of partially ordered quantification (introduced by Henkin) in first-order logic. They show that formulas obtained from first-order ones by applications of Henkin qantifiers are able to express \({\mathcal N}{\mathcal P}\)-complete properties of finite structures. However, Henkin quantifiers of one extremely restricted sort (narrow Henkin quantifiers) express exactly the co-\({\mathcal N}{\mathcal P}\) properties of finite structures.
0 references
computational aspects of partially ordered quantification
0 references
first-order logic
0 references
Henkin qantifiers
0 references
\({\mathcal N}{\mathcal P}\)-complete properties of finite structures
0 references
co-\({\mathcal N}{\mathcal P}\) properties
0 references
