Paper Info
Title
Membership Testing: Removing Extra Stacks from Multi-stack Pushdown Automata
Abstract
We show that fixed membership testing for many interesting subclasses of multi-pushdown machines is no harder than for pushdowns with single stack. The models we consider are MVPA, OVPA and MPDA, which have all been defined and studied in the past. Multi-stack pushdown automata, MPDA, have ordered stacks with pop access restricted to the stack-top of the first non-empty stack. The membership for MPDAs is known to be in NSPACE(n ) and in P. We show that the P-time algorithm can be implemented in the complexity class LogCFL; thus membership for MPDAs is LogCFL-complete. It follows that membership testing for ordered visibly pushdown automata OVPA is also in LogCFL. The membership problem for multi-stack visibly pushdown automata, MVPA, is known to be NP-complete. However, many applications focus on MVPA with O (1) phases. We show that for MVPA with O (1) phases, membership reduces to that in MPDAs, and so is in LogCFL.
Year
DOI
Venue
2009
10.1007/978-3-642-00982-2_42
LATA
Keywords
Field
DocType
membership testing,pushdown automaton,interesting subclasses,p-time algorithm,removing extra stacks,multi-stack pushdown automaton,membership problem,multi-stack pushdown automata,multi-pushdown machine,complexity class logcfl,fixed membership testing,pop access,complexity class,pushdown automata
Complexity class,Discrete mathematics,Embedded pushdown automaton,Combinatorics,Nested word,LOGCFL,Computer science,NSPACE,Deterministic pushdown automaton,Pushdown automaton,Formal grammar
Conference
Volume
ISSN
Citations 
5457
0302-9743
1
PageRank 
References 
Authors
0.38
13
2
Name
Order
Citations
PageRank
Nutan Limaye113420.59
Meena Mahajan268856.90