Umeå University's logo

umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Input-driven stack automata
Umeå University, Faculty of Science and Technology, Department of Computing Science.
Institut für Informatik, Universität Giessen, Giessen, Germany.
Institut für Informatik, Universität Giessen, Giessen, Germany.
Institut für Informatik, Universität Giessen, Giessen, Germany.
2012 (English)In: Theoretical computer science: 7th IFIP TC1/WG 2.2 International Conference, TCS 2012, Amsterdam, The Netherlands, September 26-28, 2012, Proceedings / [ed] Jos C. M. Baeten; Tom Ball; Frank S. Boer, Springer Nature, 2012, p. 28-42Conference paper, Published paper (Refereed)
Abstract [en]

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 non- deterministic 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.

Place, publisher, year, edition, pages
Springer Nature, 2012. p. 28-42
Series
Lecture Notes in Computer Science, ISSN 1611-3349, E-ISSN 1611-3349 ; 7604
National Category
Natural Sciences Computer and Information Sciences
Identifiers
URN: urn:nbn:se:umu:diva-60131DOI: 10.1007/978-3-642-33475-7_3Scopus ID: 2-s2.0-84866929892ISBN: 978-3-642-33474-0 (print)ISBN: 978-3-642-33475-7 (electronic)OAI: oai:DiVA.org:umu-60131DiVA, id: diva2:558087
Conference
TCS 2012, Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, Amsterdam, the Netherlands, September 26-28, 2012
Available from: 2012-10-01 Created: 2012-10-01 Last updated: 2023-07-24Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records

Bensch, Suna

Search in DiVA

By author/editor
Bensch, Suna
By organisation
Department of Computing Science
Natural SciencesComputer and Information Sciences

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 549 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf