A generalized quantifier concept in computational complexity theory (Q4955353)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1453080
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | A generalized quantifier concept in computational complexity theory |
scientific article; zbMATH DE number 1453080 |
Statements
8 May 2001
0 references
descriptive complexity
0 references
generalized quantifier
0 references
computational complexity theory
0 references
leaf language definability
0 references
oracle separations
0 references
type 2 operators
0 references
circuits with monoidal gates
0 references
Lindström quantifiers
0 references
0 references
0.8968763
0 references
0.89283156
0 references
0.8907633
0 references
0.88843673
0 references
0.88469774
0 references
A generalized quantifier concept in computational complexity theory (English)
0 references
In finite model theory, examinations of the expressive power of various logics enhanced by Lindström and other quantifiers form a very well established field of active research. Descriptive complexity theory has characterized a great bulk of complexity classes by such logics. In this paper, a notion of generalized quantifier in computational complexity theory is explored and used to give a unified treatment of leaf language definability, oracle separations, type 2 operators, and circuits with monoidal gates. Relations to Lindström quantifiers are pointed out. For the entire collection see [Zbl 0931.00026].
0 references
