Handle NLC grammars and r. e. languages

DOI10.1016/0022-0000(87)90012-2MaRDI QIDQ1092670zbMATH OpenOpenAlexFDO

Authors Michael Main, Grzegorz Rozenberg

Publication date 1987

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(87)90012-2

zbMATH Keywords

generating powerhandle NLC grammarsnode-label controlled graph grammarsrecursively enumerable graph language

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Review text

A graph grammar is a mechanism for generating sets of graphs (called graph languages). This paper examines the generating power of a simple extension of the well studied node-label controlled graph grammars. We show that the extension, called handle NLC grammars, gives the ability to generate any recursively enumerable graph language. The proof proceeds in three steps. First we show how a handle NLC grammar can simulate a phrase-structure string grammar, where the strings that the phrase- structure grammar works on are considered to be graphs of a special form. Then we demonstrate a way of encoding graphs as strings. The final step shows how a handle NLC grammar can convert a string encoding of a graph into the graph itself.

Recommendations

• Results of NLC grammars with one-letter terminal alphabets
• scientific article; zbMATH DE number 3890755
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• scientific article; zbMATH DE number 3872712
• scientific article; zbMATH DE number 3846895

Cites work

• A characterization of context-free string languages by directed node- label controlled graph grammars
• A system of graph grammars which generates all recursively enumerable sets of labelled graphs
• Characteristics of graph languages generated by edge replacement
• Decision problems for node label controlled graph grammars
• Graph grammars with neighbourhood-controlled embedding
• Graph-grammars and their application to computer science. 2nd International Workshop, Haus Ohrbeck, Germany, October 4-8, 1982. Under the auspices of the European Association for Theoretical Computer Science
• scientific article; zbMATH DE number 3644498 (Why is no real title available?)
• scientific article; zbMATH DE number 3819112 (Why is no real title available?)
• scientific article; zbMATH DE number 3827211 (Why is no real title available?)
• scientific article; zbMATH DE number 3639163 (Why is no real title available?)
• On the structure of node-label-controlled graph languages
• Restrictions on NLC graph grammars
• Restrictions, extensions, and variations of NLC grammars

Cited in

(6)

• HRNCE grammars -- a hypergraph generating system with an eNCE way of rewriting
• Node replacement graph grammars with dynamic node relabeling
• Handle-rewriting hypergraph grammars
• scientific article; zbMATH DE number 4049106 (Why is no real title available?)
• Results of NLC grammars with one-letter terminal alphabets
• Edge-label controlled graph grammars

This page was built for publication: Handle NLC grammars and r. e. languages

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