zbMATH — the first resource for mathematics

Traces, dependency graphs and DNLC grammars. (English) Zbl 0601.68045
We point out the use of graph grammars for specifying (generating) languages of dependency graphs that arise in theoretical studies of concurrent systems.

68Q45 Formal languages and automata
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Aalbersberg, Ij.J.; Rozenberg, G., Trace theory — a survey, ()
[2] Aalbersberg, Ij.J.; Welzl, E., Trace languages defined by regular string languages, () · Zbl 0612.68071
[3] Bertoni, A.; Brambilla, M.; Mauri, G.; Sabadini, N., An application of the theory of free partially commutative monoids: asymptotic densities of trace languages, (), 205-215 · Zbl 0468.68081
[4] Janssens, D.; Rozenberg, G., A characterization of context-free string languages by directed node-label controlled graph grammars, (), 63-85 · Zbl 0464.68077
[5] Lallement, G., Semigroups and combinatorial applications, (1979), Wiley New York · Zbl 0421.20025
[6] Mazurkiewicz, A., Concurrent program schemes and their interpretations, ()
[7] Mazurkiewicz, A., Semantics of concurrent systems: a modular fixed-point trace approach, () · Zbl 0576.68044
[8] Mazurkiewicz, A., Traces, histories, graphs: instances of a process monoid, (), 115-133
[9] Reisig, W., Petri nets, an introduction, (1985), Springer Berlin · Zbl 0555.68033
[10] Salomaa, A., Theory of automata, (1969), Pergamon Press Oxford-New York · Zbl 0193.32901
[11] Salomaa, A., Formal languages, (1973), Academic Press New York · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.