Henkin quantifiers and complete problems (Q1088983)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Henkin quantifiers and complete problems |
scientific article; zbMATH DE number 4002077
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Henkin quantifiers and complete problems |
scientific article; zbMATH DE number 4002077 |
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
0.9235978
0 references
0.91245157
0 references
0 references
0.89731556
0 references
0.89664066
0 references
0.89638627
0 references
0 references
