文章基本信息

标题：On Bounded Reachability Analysis of Shared Memory Systems
本地全文：下载
作者：Mohamed Faouzi Atig ; Ahmed Bouajjani ; K. Narayan Kumar 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：29
页码：611-623
DOI：10.4230/LIPIcs.FSTTCS.2014.611
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：This paper addresses the reachability problem for pushdown systems communicating via shared memory. It is already known that this problem is undecidable. It turns out that undecidability holds even if the shared memory consists of a single boolean variable. We propose a restriction on the behaviours of such systems, called stage bound, towards decidability. A k stage bounded run can be split into a k stages, such that in each stage there is at most one process writing to the shared memory while any number of processes may read from it. We consider several versions of stage-bounded systems and establish decidability and complexity results.
关键词：Reachability problem; Pushdown systems; Counter systems