Input-Driven Stack Automata

Abstract : We introduce and investigate input-driven stack automata, which are a generalization of input-driven pushdown automata that recently became popular under the name visibly pushdown automata. Basically, the idea is that the input letters uniquely determine the operations on the pushdown store. This can nicely be generalized to stack automata by further types of input letters which are responsible for moving the stack pointer up or down. While visibly pushdown languages share many desirable properties with regular languages, input-driven stack automata languages do not necessarily so. We prove that deterministic and nondeterministic input-driven stack automata have different computational power, which shows in passing that one cannot construct a deterministic input-driven stack automaton from a nondeterministic one. We study the computational capacity of these devices. Moreover, it is shown that the membership problem for nondeterministic input-driven stack automata languages is NP-complete.
Type de document :
Communication dans un congrès
Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.28-42, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_3〉
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01556210
Contributeur : Hal Ifip <>
Soumis le : mardi 4 juillet 2017 - 17:45:35
Dernière modification le : lundi 26 février 2018 - 13:40:02
Document(s) archivé(s) le : vendredi 15 décembre 2017 - 01:34:20

Fichier

978-3-642-33475-7_3_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Suna Bensch, Markus Holzer, Martin Kutrib, Andreas Malcher. Input-Driven Stack Automata. Jos C. M. Baeten; Tom Ball; Frank S. Boer. 7th International Conference on Theoretical Computer Science (TCS), Sep 2012, Amsterdam, Netherlands. Springer, Lecture Notes in Computer Science, LNCS-7604, pp.28-42, 2012, Theoretical Computer Science. 〈10.1007/978-3-642-33475-7_3〉. 〈hal-01556210〉

Partager

Métriques

Consultations de la notice

46

Téléchargements de fichiers

25