BOUNDEDNESS ANALYSIS OF FINITELY RECURSIVE PROCESSES - PART I - CONCURRENT PROCESSES

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.