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

Bollig, Benedikt ; Gastin, Paul ; Kumar, Akshay

Parameterized Communicating Automata: Complementation and Model Checking

pdf-format:
52.pdf (1 MB)

Abstract

We study the language-theoretical aspects of parameterized communicating automata (PCAs), in which processes communicate via rendez-vous. A given PCA can be run on any topology of bounded degree such as pipelines, rings, ranked trees, and grids. We show that, under a context bound, which restricts the local behavior of each process, PCAs are effectively complementable. Complementability is considered a key aspect of robust automata models and can, in particular, be exploited for verification. In this paper, we use it to obtain a characterization of context-bounded PCAs in terms of monadic second-order (MSO) logic. As the emptiness problem for context-bounded PCAs is decidable for the classes of pipelines, rings, and trees, their model-checking problem wrt. MSO properties also becomes decidable. While previous work on model checking parameterized systems typically uses temporal logics without next operator, our MSO logic allows one to express several natural next modalities.

BibTeX - Entry

@InProceedings{bollig_et_al:LIPIcs:2014:4876,
  author =	{Benedikt Bollig and Paul Gastin and Akshay Kumar},
  title =	{{Parameterized Communicating Automata: Complementation and Model Checking}},
  booktitle =	{34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
  pages =	{625--637},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-77-4},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{29},
  editor =	{Venkatesh Raman and S. P. Suresh},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2014/4876},
  URN =		{urn:nbn:de:0030-drops-48761},
  doi =		{10.4230/LIPIcs.FSTTCS.2014.625},
  annote =	{Keywords: parameterized verification, complementation, monadic second-order logic}
}

Keywords: parameterized verification, complementation, monadic second-order logic
Collection: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)
Issue Date: 2014
Date of publication: 12.12.2014

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