On the undecidability of asynchronous session subtyping
File(s)lange-yoshida-fossacs-17.pdf (381.58 KB)
Accepted version
Author(s)
Lange, J
Yoshida, N
Type
Conference Paper
Abstract
Asynchronous session subtyping has been studied extensively
in [9, 10, 28–31] and applied in [23, 32, 33, 35]. An open question was
whether this subtyping relation is decidable. This paper settles the ques-
tion in the negative. To prove this result, we first introduce a new sub-
class of two-party communicating finite-state machines (CFSMs), called
asynchronous duplex (ADs), which we show to be Turing complete. Sec-
ondly, we give a compatibility relation over CFSMs, which is sound and
complete wrt. safety for ADs, and is equivalent to the asynchronous
subtyping. Then we show that the halting problem reduces to check-
ing whether two CFSMs are in the relation. In addition, we show the
compatibility relation to be decidable for three sub-classes of ADs.
in [9, 10, 28–31] and applied in [23, 32, 33, 35]. An open question was
whether this subtyping relation is decidable. This paper settles the ques-
tion in the negative. To prove this result, we first introduce a new sub-
class of two-party communicating finite-state machines (CFSMs), called
asynchronous duplex (ADs), which we show to be Turing complete. Sec-
ondly, we give a compatibility relation over CFSMs, which is sound and
complete wrt. safety for ADs, and is equivalent to the asynchronous
subtyping. Then we show that the halting problem reduces to check-
ing whether two CFSMs are in the relation. In addition, we show the
compatibility relation to be decidable for three sub-classes of ADs.
Date Issued
2017-03-16
Date Acceptance
2016-12-15
Citation
Lecture Notes in Computer Science, 2017, pp.441-457
ISSN
0302-9743
Publisher
Springer Verlag
Start Page
441
End Page
457
Journal / Book Title
Lecture Notes in Computer Science
Copyright Statement
© Springer-Verlag GmbH Germany 2017. The final publication is available at Springer via https://link.springer.com/chapter/10.1007%2F978-3-662-54458-7_26
Sponsor
Engineering & Physical Science Research Council (EPSRC)
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (E
Engineering & Physical Science Research Council (EPSRC)
Commission of the European Communities
Engineering & Physical Science Research Council (E
Grant Number
EP/N027833/1
ERI 025567 (EP/K034413/1)
20104124
EP/K011715/1
612985
20103649
Source
19th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS)
Subjects
Science & Technology
Technology
Computer Science, Software Engineering
Computer Science, Theory & Methods
Logic
Computer Science
Science & Technology - Other Topics
COMMUNICATION
Artificial Intelligence & Image Processing
Publication Status
Published
Start Date
2017-04-22
Finish Date
2017-04-30
Coverage Spatial
Uppsala, Sweden
Date Publish Online
2017-03-16