文章基本信息

标题：The Power of Priority Channel Systems
本地全文：下载
作者：Christoph Haase ; Sylvain Schmitz ; Philippe Schnoebelen 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2014
卷号：10
期号：4
页码：1
DOI：10.2168/LMCS-10(4:4)2014
出版社：Technical University of Braunschweig
摘要：We introduce Priority Channel Systems, a new class of channel systems where messages carry a numeric priority and where higher-priority messages can supersede lower-priority messages preceding them in the fifo communication buffers. The decidability of safety and inevitability properties is shown via the introduction of a priority embedding, a well-quasi-ordering that has not previously been used in well-structured systems. We then show how Priority Channel Systems can compute Fast-Growing functions and prove that the aforementioned verification problems are $\mathbf{F}_{\varepsilon_{0}}$-complete.
其他关键词：Well quasi order; well-structured transition systems; fast-growing complexity.