Nivat's processing systems: decision problems related to protection and synchronization (Q761796): Difference between revisions

The notions of process and transition system (as introduced by \textit{M. Nivat} and \textit{A. Arnold} [Les mathématiques de l'informatique, AFCET Colloq., Paris 1982, 35-68 (1982; Zbl 0538.68062)] proved to be a valuable tool both from a theoretical and a practical point of view: they provide a unifying treatment of languages and \(\omega\)-languages and a modelling of the activity of many real systems. Such systems have frequently a limited behaviour: some actions cannot be performed before the accomplishment of other actions and parallel execution depends on certain synchronization restrictions. The central notion of the paper, namely that of ''processing system'', defines a framework in which the concepts described above can be expressed and studied. The purpose of the article is the treatment of the compatibility problem and the safety problem for protection systems [\textit{J. Beauquier}, Program transformations, Proc. 3rd int. Symp. Program., Paris 1978, 110-125 (1978; Zbl 0405.68022)]. The results state the decidability (or unsolvability) of these problems under different ''protection'' conditions.