License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2015.244
URN: urn:nbn:de:0030-drops-54185
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5418/
Go to the corresponding LIPIcs Volume Portal

Clemente, Lorenzo ; Lasota, Slawomir

Reachability Analysis of First-order Definable Pushdown Systems

pdf-format:
15.pdf (0.5 MB)

Abstract

We study pushdown systems where control states, stack alphabet, and transition relation, instead of being finite, are first-order definable in a fixed countably-infinite structure. We show that the reachability analysis can be addressed with the well-known saturation technique for the wide class of oligomorphic structures. Moreover, for the more restrictive homogeneous structures, we are able to give concrete complexity upper bounds. We show ample applicability of our technique by presenting several concrete examples of homogeneous structures, subsuming, with optimal complexity, known results from the literature. We show that infinitely many such examples of homogeneous structures can be obtained with the classical wreath product construction.

BibTeX - Entry

@InProceedings{clemente_et_al:LIPIcs:2015:5418,
  author =	{Lorenzo Clemente and Slawomir Lasota},
  title =	{{Reachability Analysis of First-order Definable Pushdown Systems}},
  booktitle =	{24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
  pages =	{244--259},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5418},
  URN =		{urn:nbn:de:0030-drops-54185},
  doi =		{10.4230/LIPIcs.CSL.2015.244},
  annote =	{Keywords: automata theory, pushdown systems, sets with atoms, saturation technique}
}

Keywords: automata theory, pushdown systems, sets with atoms, saturation technique
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI