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.STACS.2014.1
URN: urn:nbn:de:0030-drops-44985
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4498/
Go to the corresponding LIPIcs Volume Portal

Esparza, Javier

Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk)

pdf-format:
56.pdf (0.5 MB)

Abstract

We survey some results on the automatic verification of parameterized programs without identities. These are systems composed of arbitrarily many components, all of them running exactly the same finite-state program. We discuss the complexity of deciding that no component reaches an unsafe state. The note is addressed at theoretical computer scientists in general.

BibTeX - Entry

@InProceedings{esparza:LIPIcs:2014:4498,
  author =	{Javier Esparza},
  title =	{{Keeping a Crowd Safe: On the Complexity of Parameterized Verification (Invited Talk)}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{1--10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Ernst W. Mayr and Natacha Portier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4498},
  URN =		{urn:nbn:de:0030-drops-44985},
  doi =		{10.4230/LIPIcs.STACS.2014.1},
  annote =	{Keywords: Parameterized verification, automata theory}
}

Keywords: Parameterized verification, automata theory
Collection: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)
Issue Date: 2014
Date of publication: 05.03.2014

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