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.CONCUR.2018.12
URN: urn:nbn:de:0030-drops-95500
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9550/
Go to the corresponding LIPIcs Volume Portal

Meyer, Roland ; Muskalla, Sebastian ; Zetzsche, Georg

Bounded Context Switching for Valence Systems

pdf-format:
LIPIcs-CONCUR-2018-12.pdf (0.5 MB)

Abstract

We study valence systems, finite-control programs over infinite-state memories modeled in terms of graph monoids. Our contribution is a notion of bounded context switching (BCS). Valence systems generalize pushdowns, concurrent pushdowns, and Petri nets. In these settings, our definition conservatively generalizes existing notions. The main finding is that reachability within a bounded number of context switches is in NPTIME, independent of the memory (the graph monoid). Our proof is genuinely algebraic, and therefore contributes a new way to think about BCS. In addition, we exhibit a class of storage mechanisms for which BCS reachability belongs to PTIME.

BibTeX - Entry

@InProceedings{meyer_et_al:LIPIcs:2018:9550,
  author =	{Roland Meyer and Sebastian Muskalla and Georg Zetzsche},
  title =	{{Bounded Context Switching for Valence Systems}},
  booktitle =	{29th International Conference on Concurrency Theory  (CONCUR 2018)},
  pages =	{12:1--12:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-087-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{118},
  editor =	{Sven Schewe and Lijun Zhang},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9550},
  URN =		{urn:nbn:de:0030-drops-95500},
  doi =		{10.4230/LIPIcs.CONCUR.2018.12},
  annote =	{Keywords: valence systems, graph monoids, bounded context switching}
}

Keywords: valence systems, graph monoids, bounded context switching
Collection: 29th International Conference on Concurrency Theory (CONCUR 2018)
Issue Date: 2018
Date of publication: 31.08.2018

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