Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines (Q4723306)
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 3997170
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines |
scientific article; zbMATH DE number 3997170 |
Statements
Logspace hierarchies, polynomial time and the complexity of fairness problems concerning ω-machines (English)
0 references
1986
0 references
relativized computation
0 references
oracle machine
0 references
completeness
0 references
fairness
0 references
restricted logspace oracle hierarchy
0 references
logspace alternation hierarchy
0 references
\(\omega \)-finite state machines
0 references
\(\omega \)-one counter machines
0 references
networks of communicating finite state machines
0 references
0.9999999
0 references
0.85368955
0 references
0.8465077
0 references
0.8451606
0 references
0.83622247
0 references
0 references
0.83193314
0 references
0.8294363
0 references
0.8294363
0 references
The central notion of the paper is the restricted logspace oracle hierarchy which is a refinement of (the second level of) the logspace oracle hierarchy obtained by fixing the number of oracle calls allowed during a computation. The authors prove that the hierarchy is equivalent to the logspace alternation hierarchy and exhibit a number of problems complete for NLOGSPACE, the second, resp. the third level of the restricted logspace oracle hierarchy, and PTIME. The problems are natural problems concerning fair computations of \(\omega\)-Finite State Machines, \(\omega\)-One Counter Machines and networks of Communicating Finite State Machines. For the entire collection see [Zbl 0578.00004].
0 references