Traces, dependency graphs and DNLC grammars

DOI10.1016/0166-218X(85)90080-0zbMath0601.68045OpenAlexW2035234661WikidataQ57402299 ScholiaQ57402299MaRDI QIDQ1081307

Ijsbrand Jan Aalbersberg, Grzegorz Rozenberg

Publication date: 1985

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(85)90080-0

zbMATH Keywords

concurrent systemsgraph grammarstrace languagelanguages of dependency graphsnode-label controlled grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On the membership problem for regular DNLC grammars, On the structure of recognizable languages of dependence graphs, Theory of traces, Trace languages defined by regular string languages, The complexity of regular DNLC graph languages, Monoïde libre et musique, première partie : les musiciens ont-ils besoin des mathématiques ?, Event structures and trace monoids, Finite graph automata for linear and boundary graph languages, Characterizations of the decidability of some problems for regular trace languages

Cites Work

• A characterization of context-free string languages by directed node- label controlled graph grammars
• Trace languages defined by regular string languages
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item