On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata - Laboratoire d'Informatique Algorithmique, Fondements et Applications
Article Dans Une Revue Journal of Automata Languages and Combinatorics Année : 2009

On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata

Résumé

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).
Fichier principal
Vignette du fichier
jalc-spda.pdf (258.32 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00681253 , version 1 (21-03-2012)

Identifiants

  • HAL Id : hal-00681253 , version 1

Citer

Nutan Limaye, Meena Mahajan, Antoine Meyer. On the Complexity of Membership and Counting in Height-Deterministic Pushdown Automata. Journal of Automata Languages and Combinatorics, 2009, 14 (3/4), p. 211-235. ⟨hal-00681253⟩
170 Consultations
181 Téléchargements

Partager

More