The bounded degree problem for NLC grammars is decidable

DOI10.1016/0022-0000(86)90060-7zbMATH Open0625.68057OpenAlexW2041168908WikidataQ54309924 ScholiaQ54309924MaRDI QIDQ579950FDOQ579950

Authors: Dirk Janssens, Grzegorz Rozenberg, Emo Welzl 

Publication date: 1986

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(86)90060-7

Recommendations

• The bounded degree problem for eNCE graph grammars
• The bounded degree problem for non-obstructing eNCE graph grammars
• scientific article; zbMATH DE number 965
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Graph theoretic closure properties of the family of boundary NLC graph languages

zbMATH Keywords

bounded degreedecision problemsdegree of a graphnode label controlled graph grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Parallel concepts in graph theory
• On the structure of node-label-controlled graph languages
• Title not available (Why is that?)
• 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
• ETOL-grammars and N-grammars
• Title not available (Why is that?)
• Title not available (Why is that?)

Cited In (12)

• Graph automata for linear graph languages
• The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
• Decision problems for edge grammars
• Metatheorems for decision problems on hyperedge replacement graph languages
• The equivalence of boundary and confluent graph grammars on graph languages of bounded degree
• Context-free graph languages of bounded degree are generated by apex graph grammars
• The bounded degree problem for non-obstructing eNCE graph grammars
• A pumping lemma and the structure of derivations in the boundary NLC graph languages
• The generating power of boundary NLC graph grammars and cycle graphs
• Lambek Grammars with One Division Are Decidable in Polynomial Time
• The bounded degree problem for eNCE graph grammars
• Graph theoretic closure properties of the family of boundary NLC graph languages

This page was built for publication: The bounded degree problem for NLC grammars is decidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q579950)