DocumentCode
766432
Title
Deadlock Detection for a Class of Communicating Finite State Machines
Author
Yu, Yao-Tin ; Gouda, Mohamed G.
Author_Institution
Univ. of Texas at Austin, Austin, TX, USA
Volume
30
Issue
12
fYear
1982
fDate
12/1/1982 12:00:00 AM
Firstpage
2514
Lastpage
2518
Abstract
Let 
and 
be two communicating finite state machines which exchange one type of message. We develope a polynomial algorithm to detect whether or not and can reach a deadlock. The time complexity of the algorithm is 
and its space is 
where 
and 
are the numbers of states in and , respectively. The algorithm can also be used to verify that two communicating machines which exchange many types of messages are deadlock-free.
and be two communicating finite state machines which exchange one type of message. We develope a polynomial algorithm to detect whether or not and can reach a deadlock. The time complexity of the algorithm is and its space is where and are the numbers of states in and , respectively. The algorithm can also be used to verify that two communicating machines which exchange many types of messages are deadlock-free.Keywords
Automata; Computer communication protocols; Multiprocessing, interconnection; Automata; Helium; Polynomials; Protocols; System recovery; Tail; Testing; Timing; Very large scale integration;
fLanguage
English
Journal_Title
Communications, IEEE Transactions on
Publisher
ieee
ISSN
0090-6778
Type
jour
DOI
10.1109/TCOM.1982.1095450
Filename
1095450
Link To Document