Nivat's processing systems: decision problems related to protection and synchronization
type: Item
instance of: scholarly article
title: Nivat's processing systems: decision problems related to protection and synchronization
zbMATH Open document ID: 0557.68053
DOI: 10.1016/0304-3975(83)90080-4
published in: Theoretical Computer Science
publication date: 1983-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q45
Mathematics Subject Classification ID: 03D60
zbMATH DE Number: 3888933
zbMATH Keywords: transition system
zbMATH Keywords: processing system
zbMATH Keywords: compatibility
zbMATH Keywords: safety
zbMATH Keywords: protection systems
zbMATH Keywords: unsolvability
author: Sorin Istrail
author: Cristian Masalagiu
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90080-4
OpenAlex ID: W2092410746
cites work: Q4191580
cites work: Q3859267
cites work: Q4198075
cites work: Protection in operating systems
cites work: Complete problems for deterministic polynomial time
cites work: A Linear Time Algorithm for Deciding Subject Security
cites work: Q3673136
cites work: Q3857704
cites work: Q5678435
cites work: Adherences of languages
cites work: Q3325067
cites work: Some remarks on non-algebraic adherences
description: scientific article; zbMATH DE number 3888933