Alternating and empty alternating auxiliary stack automata.
type: Item
instance of: scholarly article
title: Alternating and empty alternating auxiliary stack automata.
zbMATH Open document ID: 1040.68054
DOI: 10.1016/S0304-3975(02)00326-2
author: Markus Holzer
author: Pierre McKenzie
published in: Theoretical Computer Science
publication date: 2003-05-25T00:00:00Z
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 1915574
zbMATH Keywords: polynomial hierarchy
MaRDI profile type: Publication
cites work: Q4039803
cites work: An Analysis of a Logical Machine Using Parenthesis-Free Notation
cites work: Alternation
cites work: Characterizations of Pushdown Machines in Terms of Time-Bounded Computers
cites work: One-way stack automata
cites work: Checking automata and one-way stack languages
cites work: Nonerasing stack automata
cites work: Q5592246
cites work: Characterizations of some tape and time complexity classes of Turing machines in terms of multihead and auxiliary stack automata
cites work: Nondeterministic Space is Closed under Complementation
cites work: Characterizing the polynomial hierarchy by alternating auxiliary pushdown automata
cites work: Alternating Pushdown and Stack Automata
cites work: Relativization of questions about log space computability
cites work: Alternation bounded auxiliary pushdown automata
cites work: Empty alternation
cites work: The complexity of facets (and some facets of complexity)
cites work: Q4743737
cites work: Space-bounded hierarchies and probabilistic computations
cites work: Relationships between nondeterministic and deterministic tape complexities
cites work: On the Tape Complexity of Deterministic Context-Free Languages
cites work: The method of forced enumeration for nondeterministic automata
cites work: Bounded Query Classes
cites work: Q3795617
full work available at URL: s0304-3975(02)00326-2
OpenAlex ID: W2007370828
description: scientific article; zbMATH DE number 1915574