DocumentCode :
3170664
Title :
Blocking in Parameterized Networks of Discrete-Event-Systems
Author :
Nazari, Siamak ; Thistle, John
Author_Institution :
Univ. of Waterloo, Waterloo
fYear :
2007
fDate :
9-13 July 2007
Firstpage :
5676
Lastpage :
5681
Abstract :
The problem of checking blocking is addressed for two different types of networks that are fully connected, in the graph-theoretic sense. In the first framework, a network consists of an arbitrary number of identical processes and a possibly distinguished control process. Their communication is according to Milner´s calculus of communicating systems (CCS). It is shown that the problems of testing such networks for two kinds of blocking, component blocking (CBP) and network blocking (NBP), are decidable. The results are also extended to networks consisting of a finite number of process classes where each class contains an arbitrary number of identical processes. In the second framework, networks consist of isomorphic processes; i.e., all processes are obtained from a unique template by appropriate relabelling. This framework differs from the previous one because processes are distinguishable. It is shown that the halting problem can be reduced to CBP and NBP of such networks, and therefore, they are undecidable.
Keywords :
calculus of communicating systems; decidability; discrete event systems; graph theory; network theory (graphs); calculus of communicating systems; component blocking; decidability; discrete-event-systems; graph theory; halting problem; network blocking; parameterized network; Algebra; Calculus; Carbon capture and storage; Cities and towns; Communication system control; Computer networks; Logic; Network topology; Process control; Testing;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
American Control Conference, 2007. ACC '07
Conference_Location :
New York, NY
ISSN :
0743-1619
Print_ISBN :
1-4244-0988-8
Electronic_ISBN :
0743-1619
Type :
conf
DOI :
10.1109/ACC.2007.4282824
Filename :
4282824
Link To Document :
بازگشت