Boundedness, Empty Channel Detection, and Synchronization for Communicating Finite Automata.
Journal
Theor. Comput. Sci.
Journal Volume
44
Pages
69-105
Date Issued
1986
Author(s)
Rosier, Louis E.
Abstract
In this paper, we consider networks of communicating finite state machines (CFSM's) that explicitly allow zero testing (i.e., empty channel detection). In our main result, we show that the boundedness problem is decidable for the class of FIFO networks consisting of two such CFSM's, where one of the two machines is allowed to send only a single type of message to the other. This result, we feel, is somewhat surprising since the zero testing capability is precisely the required extension needed in order to render the problem undecidable for the related class of vector addition systems with states (VASS's) of dimension two. Note that both have the ability to store two nonnegative integers which can be conditionally tested for zero. The reason for the disparity appears to be that such a class of extended VASS's would be capable of more synchronized behaviour (since the actions of the two counters can be controlled by a single finite state control). The rest of the paper examines other classes of networks which allow empty channel detection. These results seem to indicate that our main result cannot be extended. © 1986.
Type
journal article