The bounded degree problem for NLC grammars is decidable

DOI10.1016/0022-0000(86)90060-7MaRDI QIDQ579950zbMATH OpenOpenAlexWikidataFDO

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

zbMATH Keywords

bounded degreedecision problemsdegree of a graphnode label controlled graph grammar

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

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

Cites work

• scientific article; zbMATH DE number 3885330 (Why is no real title available?)
• scientific article; zbMATH DE number 3713195 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• 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
• On the structure of node-label-controlled graph languages
• Parallel concepts in graph theory
• Restrictions, extensions, and variations of NLC grammars

Cited in

(12)

• The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
• Graph automata for linear 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
• 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
• The bounded degree problem for non-obstructing eNCE graph grammars
• 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)