On the membership problem for regular DNLC grammars

DOI10.1016/0166-218X(86)90070-3zbMath0602.68064OpenAlexW2029471547WikidataQ57402294 ScholiaQ57402294MaRDI QIDQ1082088

Ijsbrand Jan Aalbersberg, Grzegorz Rozenberg, Andrzej Ehrenfeucht

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0166-218x(86)90070-3

zbMATH Keywords

complexitymembership problemregular directed node-label controlled graph grammars

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (7)

Uniform parsing for hyperedge replacement grammars ⋮ A hierarchy of eNCE families of graph languages ⋮ Graph Parsing as Graph Transformation ⋮ Formalization and correctness of predictive shift-reduce parsers for graph grammars based on hyperedge replacement ⋮ The complexity of regular DNLC graph languages ⋮ On the dimension of polytopes of planar three-index transportation problems ⋮ Linear graph grammars: Power and complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Traces, dependency graphs and DNLC grammars
• A characterization of context-free string languages by directed node- label controlled graph grammars
• Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• An application of the theory of free partially commutative monoids: Asymptotic densities of trace languages

This page was built for publication: On the membership problem for regular DNLC grammars