umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Input-Driven Stack Automata
Umeå universitet, Teknisk-naturvetenskapliga fakulteten, Institutionen för datavetenskap.
Institut für Informatik, Universität Giessen.
Institut für Informatik, Universität Giessen.
Institut für Informatik, Universität Giessen.
2012 (Engelska)Ingår i: IFIP TCS: Theoretical Computer Science - 7th IFIP TC 1/WG 2.2 International Conference, TCS 2012, Amsterdam, 2012. Proceedings / [ed] Jos C. M. Baeten, Thomas Ball, and Frank S. de Boer, 2012, s. 28-42Konferensbidrag, Publicerat paper (Refereegranskat)
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.

Ort, förlag, år, upplaga, sidor
2012. s. 28-42
Serie
Lecture Notes in Computer Science ; 7604
Nationell ämneskategori
Naturvetenskap Data- och informationsvetenskap
Identifikatorer
URN: urn:nbn:se:umu:diva-60131ISBN: 978-3-642-33474-0 (tryckt)OAI: oai:DiVA.org:umu-60131DiVA, id: diva2:558087
Konferens
Theoretical Computer Science
Tillgänglig från: 2012-10-01 Skapad: 2012-10-01 Senast uppdaterad: 2018-06-08Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Personposter BETA

Bensch, Suna

Sök vidare i DiVA

Av författaren/redaktören
Bensch, Suna
Av organisationen
Institutionen för datavetenskap
NaturvetenskapData- och informationsvetenskap

Sök vidare utanför DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetricpoäng

isbn
urn-nbn
Totalt: 394 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf