Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata

Author Pawel Parys



PDF
Thumbnail PDF

File

LIPIcs.STACS.2011.603.pdf
  • Filesize: 0.55 MB
  • 12 pages

Document Identifiers

Author Details

Pawel Parys

Cite AsGet BibTex

Pawel Parys. Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 603-614, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
https://doi.org/10.4230/LIPIcs.STACS.2011.603

Abstract

We show that collapsible deterministic second level pushdown automata can recognize more languages than deterministic second level pushdown automata (without collapse). This implies that there exists a tree generated by a second level recursion scheme which is not generated by any second level safe recursion scheme.
Keywords
  • pushdown automata

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail