The bounded degree problem for NLC grammars is decidable

DOI10.1016/0022-0000(86)90060-7zbMath0625.68057OpenAlexW2041168908WikidataQ54309924 ScholiaQ54309924MaRDI QIDQ579950

Dirk Janssens, Grzegorz Rozenberg, Ermo 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

zbMATH Keywords

decision problemsbounded degreedegree of a graphnode label controlled graph grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

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, The equivalence of boundary and confluent graph grammars on graph languages of bounded degree, The bounded degree problem for eNCE graph grammars, Metatheorems for decision problems on hyperedge replacement graph languages, Decision problems for edge grammars, The bounded degree problem for non-obstructing eNCE graph grammars, Graph automata for linear graph languages, The complexity of the \(K_{n,n}\)-problem for node replacement graph languages

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
• ETOL-grammars and N-grammars
• Parallel concepts in graph theory
• Unnamed Item
• Unnamed Item
• Unnamed Item