uu.seUppsala universitets publikasjoner
Endre søk
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet 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 (engelsk)Inngår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, nr 8, s. 945-975Artikkel i tidsskrift (Fagfellevurdert) 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.

sted, utgiver, år, opplag, sider
2017. Vol. 28, nr 8, s. 945-975
Emneord [en]
Multi-pushdown automata, emptiness problem
HSV kategori
Identifikatorer
URN: urn:nbn:se:uu:diva-348938DOI: 10.1142/S0129054117500332ISI: 000426085800001OAI: oai:DiVA.org:uu-348938DiVA, id: diva2:1198959
Tilgjengelig fra: 2018-04-19 Laget: 2018-04-19 Sist oppdatert: 2018-04-19bibliografisk kontrollert

Open Access i DiVA

Fulltekst mangler i DiVA

Andre lenker

Forlagets fulltekst

Personposter BETA

Atig, Mohamed Faouzi

Søk i DiVA

Av forfatter/redaktør
Atig, Mohamed Faouzi
Av organisasjonen
I samme tidsskrift
International Journal of Foundations of Computer Science

Søk utenfor DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric

doi
urn-nbn
Totalt: 223 treff
RefereraExporteraLink to record
Permanent link

Direct link
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Annet format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annet språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf