Title | ||
---|---|---|
On the complexity of membership and counting in height-deterministic pushdown automata |
Abstract | ||
---|---|---|
While visibly pushdown languages properly generalise regular languages and are properly contained in deterministic context-free languages, the complexity of their membership problem is equivalent to that of regular languages. However, the corresponding counting problem could be harder than counting paths in a non-deterministic finite automaton: it is only known to be in LogDCFL. We investigate the membership and counting problems for generalisations of visibly pushdown automata, defined using the notion of height-determinism. We show that, when the stack-height of a given PDA can be computed using a finite transducer, both problems have the same complexity as for visibly pushdown languages. We also show that when allowing pushdown transducers instead of finite-state ones, both problems become LogDCFL-complete; this uses the fact that pushdown transducers are sufficient to compute the stack heights of all real-time height-deterministic pushdown automata, and yields a candidate arithmetization of LogDCFL that is no harder than LogDCFL (our main result). |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-540-79709-8_25 | Journal of Automata, Languages and Combinatorics |
Keywords | DocType | Volume |
generalise regular language,pushdown automaton,candidate arithmetization,corresponding counting problem,real-time height-deterministic pushdown automaton,finite transducer,pushdown transducers,non-deterministic finite automaton,membership problem,regular language,pushdown language,context free language,pushdown automata,real time | Conference | 14 |
Issue | ISSN | ISBN |
3 | 0302-9743 | 3-540-79708-4 |
Citations | PageRank | References |
6 | 0.48 | 19 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nutan Limaye | 1 | 134 | 20.59 |
Meena Mahajan | 2 | 688 | 56.90 |
Antoine Meyer | 3 | 79 | 4.69 |