uu.seUppsala universitets publikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • 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
Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete
Uppsala universitet, Teknisk-naturvetenskapliga vetenskapsområdet, Matematisk-datavetenskapliga sektionen, Institutionen för informationsteknologi, Datorteknik.
CNRS, LSV, Paris, France.;ENS Paris Saclay, Paris, France.
CNRS, IRIF, Paris, France.;Univ Paris Diderot, Paris, France..
2017 (Engelska)Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, nr 8, s. 945-975Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We consider ordered multi-pushdown automata, a multi-stack extension of pushdown automata that comes with a constraint on stack operations: a pop can only be performed on the first non-empty stack (which implies that we assume a linear ordering on the collection of stacks). We show that the emptiness problem for multi-pushdown automata is 2ETIME-complete. Containment in 2ETIME is shown by translating an automaton into a grammar for which we can check if the generated language is empty. The lower bound is established by simulating the behavior of an alternating Turing machine working in exponential space. We also compare ordered multi-pushdown automata with the model of bounded-phase (visibly) multi-stack pushdown automata, which do not impose an ordering on stacks, but restrict the number of alternations of pop operations on different stacks.

Ort, förlag, år, upplaga, sidor
2017. Vol. 28, nr 8, s. 945-975
Nyckelord [en]
Multi-pushdown automata, emptiness problem
Nationell ämneskategori
Datavetenskap (datalogi) Datorsystem
Identifikatorer
URN: urn:nbn:se:uu:diva-348938DOI: 10.1142/S0129054117500332ISI: 000426085800001OAI: oai:DiVA.org:uu-348938DiVA, id: diva2:1198959
Tillgänglig från: 2018-04-19 Skapad: 2018-04-19 Senast uppdaterad: 2018-04-19Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

Förlagets fulltext

Personposter BETA

Atig, Mohamed Faouzi

Sök vidare i DiVA

Av författaren/redaktören
Atig, Mohamed Faouzi
Av organisationen
Datorteknik
I samma tidskrift
International Journal of Foundations of Computer Science
Datavetenskap (datalogi)Datorsystem

Sök vidare utanför DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetricpoäng

doi
urn-nbn
Totalt: 223 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • 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