{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,23]],"date-time":"2023-10-23T08:10:48Z","timestamp":1698048648184},"reference-count":3,"publisher":"Wiley","issue":"4","license":[{"start":{"date-parts":[[2007,9,5]],"date-time":"2007-09-05T00:00:00Z","timestamp":1188950400000},"content-version":"vor","delay-in-days":7187,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp;amp; Computers in Japan"],"published-print":{"date-parts":[[1988,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Usually, communication protocols are modelled as a communication between two finite\u2010state machines. Yu and Gouda [1] have shown that if the messages of a single type and the finite\u2010state machine have no mixed nodes, the verification of deadlock can be made in a polynomial time. This paper shows that if the messages are of a single type, the verification of deadlock can be made in a polynomial time, even if there does exist mixed nodes. The proof is derived by indicating that the communication sequences arriving at deadlock states form a context\u2010free language. If there does not exist a deadlock in the protocol obtained by converting all the messages into a single type, no deadlock exists in the original protocol (the converse is not always true). In this sense, the result in this paper is important.<\/jats:p>","DOI":"10.1002\/scj.4690190405","type":"journal-article","created":{"date-parts":[[2009,11,19]],"date-time":"2009-11-19T21:16:08Z","timestamp":1258665368000},"page":"48-55","source":"Crossref","is-referenced-by-count":0,"title":["A Validation Method for Communication Protocols Using Context\u2013Free Language Theory"],"prefix":"10.1002","volume":"19","author":[{"given":"Kaoru","family":"Kurosawa","sequence":"first","affiliation":[]},{"given":"Yoshiki","family":"Kuwabara","sequence":"additional","affiliation":[]},{"given":"Takashi","family":"Shigeno","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2007,9,5]]},"reference":[{"issue":"12","key":"e_1_2_1_2_2","first-page":"2514","article-title":"Deadlock detection for a class of communicating finite state machines, I.E.E.E.","volume":"30","author":"Yu Y. T.","year":"1982","journal-title":"Trans."},{"key":"e_1_2_1_3_2","first-page":"65","article-title":"An improved protocol validation technique","volume":"6","author":"Rubin J.","year":"1982","journal-title":"Computer Networks"},{"key":"e_1_2_1_4_2","volume-title":"Formal Languages and Their Relations to Automata","author":"Hopcroft J. E.","year":"1969"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690190405","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690190405","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,22]],"date-time":"2023-10-22T07:59:47Z","timestamp":1697961587000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690190405"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1988,1]]},"references-count":3,"journal-issue":{"issue":"4","published-print":{"date-parts":[[1988,1]]}},"alternative-id":["10.1002\/scj.4690190405"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690190405","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1988,1]]}}}