文章基本信息

标题：Parameterised Pushdown Systems with Non-Atomic Writes
本地全文：下载
作者：Matthew Hague
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2011
卷号：13
页码：457-468
DOI：10.4230/LIPIcs.FSTTCS.2011.457
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the master/slave parameterised reachability problem for networks of pushdown systems, where communication is via a global store using only non-atomic reads and writes. We show that the control-state reachability problem is decidable. As part of the result, we provide a constructive extension of a theorem by Ehrenfeucht and Rozenberg to produce an NFA equivalent to certain kinds of CFG. Finally, we show that the non-parameterised version is undecidable.
关键词：Verification; Concurrency; Pushdown Systems; Reachability; Parameterised Systems; Non-atomicity