Is parallelism already concurrency? II: Non-sequential processes in graph grammars. (English) Zbl 0643.68024

Graph-grammars and their application to computer science, 3rd Int. Workshop, Warrenton/Va. 1986, Lect. Notes Comput. Sci. 291, 361-377 (1987).
Summary: [For the entire collection see Zbl 0636.00013. Part I: ibid., 343-360 (see the preceding review).]
Non-sequential processes in graph grammars are introduced extending the repertoire of parallelism and concurrency known for graph grammar derivations. They are intended to describe the behaviour of systems explicitly where states or data may be distributed and actions may take place concurrently. Our notion of a process is liberal enough to include conflicts among actions so that it reflects potential activities rather than actual running of the system in general. The problem of detecting conflicts in a process is solved by a procedure transforming arbitrary conflicts into local and hence observable ones. For special situations conflict solutions are investigated by applying techniques and results from graph grammar theory.


68N25 Theory of operating systems
68Q45 Formal languages and automata