DROPS

Document

DOI: 10.4230/LIPIcs.CSL.2011.322

A Pumping Lemma for Collapsible Pushdown Graphs of Level 2

Authors: Alexander Kartzow

Published in: LIPIcs, Volume 12, Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL (2011)

Abstract

We present a pumping lemma for the class of collapsible pushdown graphs of level 2. This pumping lemma even applies to epsilon-contractions of level 2 collapsible pushdown graphs. Our pumping lemma also improves the bounds of Hayashi's pumping lemma for indexed languages.

Cite as

Alexander Kartzow. A Pumping Lemma for Collapsible Pushdown Graphs of Level 2. In Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL. Leibniz International Proceedings in Informatics (LIPIcs), Volume 12, pp. 322-336, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{kartzow:LIPIcs.CSL.2011.322,
  author =	{Kartzow, Alexander},
  title =	{{A Pumping Lemma for Collapsible Pushdown Graphs of Level 2}},
  booktitle =	{Computer Science Logic (CSL'11) - 25th International Workshop/20th Annual Conference of the EACSL},
  pages =	{322--336},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-32-3},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{12},
  editor =	{Bezem, Marc},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2011.322},
  URN =		{urn:nbn:de:0030-drops-32406},
  doi =		{10.4230/LIPIcs.CSL.2011.322},
  annote =	{Keywords: collapsible pushdown graph, epsilon-contraction, pumping lemma}
}

Document

DOI: 10.4230/LIPIcs.STACS.2010.2480

Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

Authors: Alexander Kartzow

Published in: LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Abstract

We show that graphs generated by collapsible pushdown systems of level $2$ are tree-automatic. Even when we allow $\varepsilon$-contractions and add a reachability predicate (with regular constraints) for pairs of configurations, the structures remain tree-automatic. Hence, their \FO theories are decidable, even when expanded by a reachability predicate. As a corollary, we obtain the tree-automaticity of the second level of the Caucal-hierarchy.

Cite as

Alexander Kartzow. Collapsible Pushdown Graphs of Level 2 are Tree-Automatic. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 501-512, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{kartzow:LIPIcs.STACS.2010.2480,
  author =	{Kartzow, Alexander},
  title =	{{Collapsible Pushdown Graphs of Level 2 are Tree-Automatic}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{501--512},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Marion, Jean-Yves and Schwentick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2480},
  URN =		{urn:nbn:de:0030-drops-24801},
  doi =		{10.4230/LIPIcs.STACS.2010.2480},
  annote =	{Keywords: Tree-automatic structures, collapsible pushdown graphs, collapsible pushdown systems, first-order decidability, reachability}
}

Search Results

Documents authored by Kartzow, Alexander

A Pumping Lemma for Collapsible Pushdown Graphs of Level 2

Abstract

Cite as

Collapsible Pushdown Graphs of Level 2 are Tree-Automatic

Abstract

Cite as

Thanks for your feedback!

Could not send message