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 :
