Imperial College London
Professor Nobuko Yoshida

ProfessorNobukoYoshida

Faculty of Engineering, Department of Computing

Academic Visitor
 
 
 
//

Contact

 

+44 (0)20 7594 8240n.yoshida Website

 
 
//

Location

 

556Huxley BuildingSouth Kensington Campus

//

Summary

 

Publications

Citation

BibTex format

@techreport{Lange:2016:10.25561/94970,
author = {Lange, J and Yoshida, N},
booktitle = {Departmental Technical Report: 16/9},
doi = {10.25561/94970},
publisher = {Department of Computing, Imperial College London},
title = {On the undecidability of asynchronous session subtyping},
url = {http://dx.doi.org/10.25561/94970},
year = {2016}
}
Download

RIS format (EndNote, RefMan)

TY  - RPRT
AB  - Asynchronous session subtyping has been studied extensivelyin [9, 10, 29{32] and applied in [24, 33, 34, 36]. An open question waswhether this subtyping relation is decidable. This paper settles the questionin the negative. To prove this result, we  rst introduce a new subclassof two-party communicating  nite-state machines (CFSMs), calledasynchronous duplex (ADs), which we show to be Turing complete. Secondly,we give a compatibility relation over CFSMs, which is sound andcomplete wrt. safety for ADs, and is equivalent to the asynchronoussubtyping. Then we show that the halting problem reduces to checkingwhether two CFSMs are in the relation. In addition, we show thecompatibility relation to be decidable for three sub-classes of ADs.
AU  - Lange,J
AU  - Yoshida,N
DO  - 10.25561/94970
PB  - Department of Computing, Imperial College London
PY  - 2016///
TI  - On the undecidability of asynchronous session subtyping
T1  - Departmental Technical Report: 16/9
UR  - http://dx.doi.org/10.25561/94970
UR  - http://hdl.handle.net/10044/1/94970
ER  -
Download