zbMATH — the first resource for mathematics

The power of priority channel systems. (English) Zbl 1390.68471
D’Argenio, Pedro R. (ed.) et al., CONCUR 2013 – concurrency theory. 24th international conference, CONCUR 2013, Buenos Aires, Argentina, August 27–30, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40183-1/pbk). Lecture Notes in Computer Science 8052, 319-333 (2013).
Summary: We introduce priority channel systems, a new natural 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.
For the entire collection see [Zbl 1269.68020].
68Q85 Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.)
Full Text: DOI