Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies (Q4800264)
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 1890826
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies |
scientific article; zbMATH DE number 1890826 |
Statements
Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies (English)
0 references
15 July 2003
0 references
automata theory
0 references
complexity theory
0 references
leaf-languages
0 references
Straubing hierarchy
0 references
Brzozowski hierarchy
0 references
typed Boolean hierarchy
0 references
fine hierarchy
0 references
polynomial-time hierarchy
0 references
0.9138550162315368
0 references
0.7532334923744202
0 references
0.7461186647415161
0 references
0.7461184859275818
0 references
0.7323532700538635
0 references
It is a well-known fact that many important complexity classes have natural descriptions in terms of automata theory. For this purpose leaf-languages are especially useful. These languages are defined as the sets of words obtained from symbols printed after finishing any computation path by a polynomial-time nondeterministic Turing machine. The author presents some hierarchies relevant to the topic of the paper. After the definitions of two hierarchies from automata theory, namely the Straubing hierarchy and the Brzozowski hierarchy, the author introduces the typed Boolean hierarchy and recalls his definition of the fine hierarchy. In the main part of the paper some theorems are proved which relate the introduced hierarchies to the polynomial-time hierarchy via the leaf-languages approach. In the end the meaning and importance of the obtained results are discussed. The author points out that the existence of nontrivial connections between automata and complexity hierarchies is an interesting and unexpected fact. The usefulness of such results to study the noncollapsing character of hierarchies is also mentioned.
0 references