{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:29:12Z","timestamp":1787340552953,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[1985,8]]},"abstract":"<jats:p>Consider a network of two communicating finite state machines which exchange messages over two one-directional, unbounded channels, and assume that each machine receives the messages from its input channel based on some fixed (partial) priority relation. We address the problem of whether the communication of such a network is deadlock-free and bounded. We show that the problem is undecidable if the two machines exchange two types of messages. The problem is also undecidable if the two machines exchange three types of messages, and one of the channels is known to be bounded. However, if the two machines exchange two (or less) types of messages, and one channel is known to be bounded, then the problem becomes decidable. The problem is also decidable if one machine sends one type of message and the second machine sends two (or less) types of messages; the problem becomes undecidable if the second machine sends three types of messages. The problem is also decidable if the message priority relation is empty. We also address the problem of whether there is a message priority relation such that the priority network behaves like a FIFO network. We show that the problem is undecidable in general, and present some special cases for which the problem becomes decidable.<\/jats:p>","DOI":"10.1137\/0214042","type":"journal-article","created":{"date-parts":[[2005,2,24]],"date-time":"2005-02-24T06:25:35Z","timestamp":1109226335000},"page":"569-584","source":"Crossref","is-referenced-by-count":11,"title":["Priority Networks of Communicating Finite State Machines"],"prefix":"10.1137","volume":"14","author":[{"given":"Mohamed G.","family":"Gouda","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Louis E.","family":"Rosier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,2]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1016\/0376-5075(78)90015-6"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1145\/322374.322380"},{"key":"R3","unstructured":"P. Cunha, T. Maibaum,  A synchronization calculus for message-oriented programming,  Proc. 2nd International Conference on Distributed Computing Systems,  1981,  433\u2013445, April"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"M. Gouda, E. Manning, Y. Yu,  On the progress of communication between two finite state machines, Tech. Rep., 200, Dept. Computer Sciences, Univ. Texas,  1982, May, revised August 1983","DOI":"10.1016\/S0019-9958(84)80014-5"},{"key":"R5","unstructured":"M. Gouda, L. Rosier,  Priority networks of communicating finite state machines, Tech. Rep., 83-10, Dept. Computer Sciences, Univ. Texas, Austin,  1983, August"},{"key":"R6","unstructured":"M. Hack, Masters Thesis,  Decidability questions for Petri nets, Ph.D. dissertation, Dept. Electrical Engineering, Massachusetts Institute of Technology, Cambridge,  1975"},{"key":"R7","volume-title":"Introduction to automata theory, languages, and computation","author":"Hopcroft J.","year":"1979"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1145\/322047.322058"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1007\/BF01752400"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(69)80011-5"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"S. Kosaraju,  Decidability of reachability in vector addition systems,  Proc.14th Annual ACM Symposium on the Theory of Computing,  1982,  267\u2013281","DOI":"10.1145\/800070.802201"},{"key":"R12","first-page":"81","volume-title":"Computer Communications, Vol. I, Principles","author":"Lam S.","year":"1983"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"E. Mayr,  An algorithm for the general Petri net reachability problem,  Proc. 13th Annual ACM Symposium on the Theory of Computing,  1981,  238\u2013246","DOI":"10.1145\/800076.802477"},{"key":"R14","unstructured":"P. Merlin, G. Bochmann,  On the construction of communication protocols and module specification, Pub., 352, Dept. d'Informatique de Recherche Op\u00e9rationnelle, Universit\u00e9 de Montr\u00e9al, Montr\u00e9al, Quebec,  1980, January"},{"key":"R15","volume-title":"Computation: finite and infinite machines","author":"Minsky Marvin L.","year":"1967"},{"key":"R16","volume-title":"Petri net theory and the modeling of systems","author":"Peterson James Lyle","year":"1981"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90036-1"},{"key":"R18","unstructured":"L. Rosier, M. Gouda,  Deciding progress for a class of communicating finite state machines,  Proc. Eighteenth Annual Conference on Information Sciences and Systems, Princeton Univ., Princeton, NJ,  1984"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"George S. Sacerdote, Richard L. Tenney,  The decidability of the reachability problem for vector addition systems (preliminary version),  Conference Record of the Ninth Annual ACM Symposium on Theory of Computing (Boulder, Colo., 1977), Assoc. Comput. Mach., New York,  1977,  61\u201376 58:8477","DOI":"10.1145\/800105.803396"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(70)80006-X"},{"key":"R21","volume-title":"Computer Networks","author":"Tannenbaum A.","year":"1981"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(75)80005-5"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1982.1095450"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90105-9"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1980.1094687"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/0214042","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:07Z","timestamp":1787337547000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/0214042"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1985,8]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1985,8]]}},"alternative-id":["10.1137\/0214042"],"URL":"https:\/\/doi.org\/10.1137\/0214042","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[1985,8]]}}}