uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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
Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Information Technology, Computer Systems.
CNRS, LSV, Paris, France.;ENS Paris Saclay, Paris, France.
CNRS, IRIF, Paris, France.;Univ Paris Diderot, Paris, France..
2017 (English)In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 28, no 8, p. 945-975Article in journal (Refereed) 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.

Place, publisher, year, edition, pages
2017. Vol. 28, no 8, p. 945-975
Keyword [en]
Multi-pushdown automata, emptiness problem
National Category
Computer Sciences Computer Systems
Identifiers
URN: urn:nbn:se:uu:diva-348938DOI: 10.1142/S0129054117500332ISI: 000426085800001OAI: oai:DiVA.org:uu-348938DiVA, id: diva2:1198959
Available from: 2018-04-19 Created: 2018-04-19 Last updated: 2018-04-19Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full text

Authority records BETA

Atig, Mohamed Faouzi

Search in DiVA

By author/editor
Atig, Mohamed Faouzi
By organisation
Computer Systems
In the same journal
International Journal of Foundations of Computer Science
Computer SciencesComputer Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

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

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • 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