License
when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2011.603
URN: urn:nbn:de:0030-drops-30478
URL: http://drops.dagstuhl.de/opus/volltexte/2011/3047/
Parys, Pawel

Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata

pdf-format:
Dokument 1.pdf (568 KB)

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.

BibTeX - Entry

@InProceedings{parys:LIPIcs:2011:3047,
  author =	{Pawel Parys},
  title =	{{Collapse Operation Increases Expressive Power of Deterministic Higher Order Pushdown Automata}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011) },
  pages =	{603--614},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Thomas Schwentick and Christoph D{\"u}rr},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3047},
  URN =		{urn:nbn:de:0030-drops-30478},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2011.603},
  annote =	{Keywords: pushdown automata}
}

Keywords: pushdown automata
Seminar: 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Issue date: 2011
Date of publication: 11.03.2011

DROPS-Home | Fulltext Search | Imprint Published by LZI