Skip to Main content Skip to Navigation
Journal articles

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).
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-00681253
Contributor : Antoine Meyer <>
Submitted on : Wednesday, March 21, 2012 - 9:33:14 AM
Last modification on : Thursday, November 19, 2020 - 11:48:02 AM
Long-term archiving on: : Monday, November 26, 2012 - 11:45:22 AM

File

jalc-spda.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-00681253, version 1

Collections

Citation

Nutan Limaye, Meena Mahajan, Antoine Meyer. On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata. Journal of Automata Languages and Combinatorics, Otto-von-Guericke-Universität Magdeburg, 2009, 14 (3/4), p. 211-235. ⟨hal-00681253⟩

Share

Metrics

Record views

298

Files downloads

322