Context-sensitive transitive closure operators (Q1319508)
From MaRDI portal
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Context-sensitive transitive closure operators |
scientific article |
Statements
Context-sensitive transitive closure operators (English)
0 references
12 April 1994
0 references
This paper continues research initiated by Fagin about the question which (first or second order) logics can capture which complexity classes. The author introduces a new operator, called the context-sensitive transitive closure operator, which is able to express the class PSPACE. By varying how the operator is applied, also the complexity classes P, NP, PH (the polynomial-time hierarchy) can be captured.
0 references
descriptive complexity theory
0 references
program schemes
0 references
fixed point operator
0 references
complexity classes
0 references
context-sensitive transitive closure operator
0 references
PSPACE
0 references
P
0 references
NP
0 references
PH
0 references
polynomial-time hierarchy
0 references
