Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en La Torre, Salvatore; Parthasarathy, Madhusudan http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-116082
URL:

;

Reachability in Concurrent Uninterpreted Programs

pdf-format:


Abstract

We study the safety verification (reachability problem) for concurrent programs with uninterpreted functions/relations. By extending the notion of coherence, recently identified for sequential programs, to concurrent programs, we show that reachability in coherent concurrent programs under various scheduling restrictions is decidable by a reduction to multistack pushdown automata, and establish precise complexity bounds for them. We also prove that the coherence restriction for these various scheduling restrictions is itself a decidable property.

BibTeX - Entry

@InProceedings{latorre_et_al:LIPIcs:2019:11608,
  author =	{Salvatore La Torre and Madhusudan Parthasarathy},
  title =	{{Reachability in Concurrent Uninterpreted Programs}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{46:1--46:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11608},
  URN =		{urn:nbn:de:0030-drops-116082},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.46},
  annote =	{Keywords: Verification, uninterpreted programs, concurrent programs, shared memory}
}

Keywords: Verification, uninterpreted programs, concurrent programs, shared memory
Seminar: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue date: 2019
Date of publication: 2019


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