Chennai Mathematical Institute

Seminars




2.00 pm, NKN Hall
The Power of Priority Channel Systems

Philippe Schnoebelen
CNRS and ENS Cachan, France.
25-02-14


Abstract

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 show how Priority Channel Systems can compute Fast-Growing functions and prove that the aforementioned verification problems are F_{\epsilon_{0}}-complete.

Slides





Google
Search WWW Search cmi.ac.in