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 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

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references