No label defined (Q3787475)

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 4050986
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4050986

      Statements

      0 references
      0 references
      1988
      0 references
      complexity theory
      0 references
      alternating auxiliary pushdown hierarchy
      0 references
      machine model
      0 references
      logarithmic alternation hierarchy
      0 references
      pushdown store
      0 references
      PSPACE
      0 references
      pushdown automata with unbounded alternation
      0 references
      [For the entire collection see Zbl 0635.00015.] An alternating auxiliary pushdown hierarchy is defined by extending the machine model of the logarithmic alternation hierarchy by a pushdown store while keeping a polynomial time bound. Although recently it was proven by Borodin et al. that the class of languages accepted by nondeterministic logarithmic space bounded auxiliary pushdown automata with a polynomial time bound is closed under complement, it is shown that, surprisingly, the further levels of this alternating auxiliary pushdown hierarchy coincide level by level with the polynomial hierarchy. Furthermore, it is shown that PSPACE can be characterized by simultaneously logarithmic space and polynomial time bounded auxiliary pushdown automata with unbounded alternation.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references