Paper Info
Title
The expressibility of nondeterministic auxiliary stack automata and its relation to Treesize bounded alternating auxiliary pushdown automata
Abstract
Two aspects of nondeterministic auxiliary stack automata (NAuxSA) are studied in this paper. The first is regarding the expressibility of NAuxSA. More specifically, it is shown that the polynomial hierarchy can be characterised in terms of AuxSA with resource bounds. The second aspect is a duality relation between NAuxSA and alternating auxiliary pushdown automata (Alt-AuxPDA) connecting time bounds on the former with treesise bounds on the latter.
Year
DOI
Venue
1990
10.1007/3-540-53487-3_38
FSTTCS
Keywords
Field
DocType
auxiliary pushdown automaton,pushdown automata,nondeterministic auxiliary stack automata,treesize bounded alternating auxiliary
Polynomial hierarchy,Discrete mathematics,State transition table,Embedded pushdown automaton,Combinatorics,Nested word,Nondeterministic algorithm,Computer science,Deterministic pushdown automaton,Pushdown automaton,Bounded function
Conference
ISBN
Citations 
PageRank 
0-387-53487-3
2
0.38
References 
Authors
7
2
Name
Order
Citations
PageRank
V. Vinay1486.38
V. Chandru220823.88