Algebraic models for asynchronous control structures

[摘要] The study of asynchronous control structures used for enforcing the coordination required to carry out an activity that exhibits concurrency is of considerable interest and importance. A large class of these control structures can be adequately and concisely described by Petri-nets. The Petri-net, being a graphical model, promises to be a powerful tool in the design of such control structures. However, precisely because it is a graphical model, the Petri-net is not amenable to elegant mathematical analysis. Hence it is difficult to find answers to significant questions regarding the structure and behavior of asynchronous control structures if their sole available descriptions are in the form of Petri-nets. For this reason, the problem of formulating valid algebraic models for the above-mentioned class of control structures is studied. In particular, attention is confined to those control structures that can be described by marked graphs, which are a restricted type of Petrinets. Two algebraic models called the C-D model and the Poset model are formulated and their validity is established. Both these models represent the control structure under study by specifying the cause-effect relationship imposed by the control structure on the flow of signals that are associated with it. Finally, as an example of the application of these two models, a simple scheme for realizing marked-graph-describable asynchronous control structures is demonstrated.

[发布机构] Rice University