S. Bose et al., BOUNDEDNESS ANALYSIS OF FINITELY RECURSIVE PROCESSES - PART I - CONCURRENT PROCESSES, IEEE transactions on automatic control, 43(11), 1998, pp. 1514-1531
In the finitely recursive process (FRP) model of discrete event system
s (DES), concepts about processes and process operators have been intr
oduced. An infinite set of process expressions or functions can be bui
lt recursively through function composition using a few elementary ope
rators. Given any process realization, it is important to find out whe
ther the process is bounded, i.e., whether it has a finite state reali
zation. In the FRP setting this translates to the problem of finding o
ut whether the set of post-process expressions is finite or not, In Ci
eslak and Varaiya (1990) it has been shown that the boundedness proble
m is undecidable for general FRP's, This paper investigates the decida
bility of the problem for subclasses of FRP, In Inan and Varaiya (1988
), it was conjectured that the set of functions that can be recursivel
y generated using the parallel composition operator (PCO) and differen
t change operators [i.e., without using the Sequential Composition Ope
rator (SCO)] will be finite and FRP's constructed over this set of fun
ctions will naturally be bounded. In the present work a counterexample
has been provided to disprove the conjecture about the finiteness of
the above set of functions. However, using a suitable post-process com
putation procedure, it has been shown here that the FRP's, built recur
sively over this set of functions, are bounded.