Restrictions on NLC graph grammars

DOI10.1016/0304-3975(84)90135-XzbMath0566.68062MaRDI QIDQ1059402

Michael G. Main, Andrzej Ehrenfeucht, Grzegorz Rozenberg

Publication date: 1984

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

normal formconnection relationnode label controlled grammarsreduction of generating power

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (11)

A pumping lemma and the structure of derivations in the boundary NLC graph languages ⋮ Graph theoretic closure properties of the family of boundary NLC graph languages ⋮ The generating power of boundary NLC graph grammars and cycle graphs ⋮ Context-free graph languages of bounded degree are generated by apex graph grammars ⋮ Combinatorial properties of boundary NLC graph languages ⋮ Handle NLC grammars and r. e. languages ⋮ Power properties of NLC graph grammars with a polynomial membership problem ⋮ Boundary graph grammars with dynamic edge relabeling ⋮ Results of NLC grammars with one-letter terminal alphabets ⋮ Finite graph automata for linear and boundary graph languages ⋮ On hyperedge replacement and BNLC graph grammars

Cites Work

• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• A characterization of context-free string languages by directed node- label controlled graph grammars
• Decision problems for node label controlled graph grammars
• Graph grammars with neighbourhood-controlled embedding
• Deriving graphs from graphs by applying a production
• On certain formal properties of grammars
• A New Normal-Form Theorem for Context-Free Phrase Structure Grammars
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Restrictions on NLC graph grammars