Decision problems for node label controlled graph grammars

DOI10.1016/0022-0000(81)90025-8zbMath0466.68067OpenAlexW2079009553MaRDI QIDQ1155373

Grzegorz Rozenberg, Dirk Janssens

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90025-8

Mathematics Subject Classification ID

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

Related Items (18)

Node replacements in embedding normal form. ⋮ Graph theoretic closure properties of the family of boundary NLC graph languages ⋮ Combinatorial properties of boundary NLC graph languages ⋮ Handle NLC grammars and r. e. languages ⋮ Characteristics of graph languages generated by edge replacement ⋮ An axiomatic definition of context-free rewriting and its application to NLC graph grammars ⋮ Decision problems for edge grammars ⋮ Results of NLC grammars with one-letter terminal alphabets ⋮ Edge-label controlled graph grammars ⋮ HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting ⋮ Hypermap rewriting: A combinatorial approach ⋮ Graph grammars according to the type of input and manipulated data: a survey ⋮ Finite graph automata for linear and boundary graph languages ⋮ The bounded degree problem for NLC grammars is decidable ⋮ Linear graph grammars: Power and complexity ⋮ Note on node-rewriting graph grammars ⋮ Restrictions on NLC graph grammars ⋮ Separating \(k\)-separated eNCE graph languages

Cites Work

• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Decision problems for node label controlled graph grammars