Parallel algorithms for a class of graphs generated recursively (Q582922): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / author | |||
Property / author: Wojciech Rytter / rank | |||
Normal rank | |||
Property / review text | |||
A star graph (G,R) is a kernel graph G and a set of additional pending edges R called legs each having exactly one common vertex with G. The vertices of G are labelled by a terminal and nonterminal symbols. A grammar is given by an axiom star graph \(X_ 0\) with no legs and a set of production \(X\to Y\). Here X is a star graph, whose kernel consists of only one vertex labelled by a nonterminal, and Y is a star graph with the same number of legs as X. The language of graphs defined by such a grammar is the set of all graphs (with only terminal labels) which are derivable from \(X_ 0\) by using the productions. Let \(NC^ i\) be the class of problems coumputable by a parallel random access machine. Then, recognition and parsing of graphs generated by such a grammar is i \(NC^ 2\), and several NP-complete problems are in \(NC^ 1\), if the parsing tree is given. | |||
Property / review text: A star graph (G,R) is a kernel graph G and a set of additional pending edges R called legs each having exactly one common vertex with G. The vertices of G are labelled by a terminal and nonterminal symbols. A grammar is given by an axiom star graph \(X_ 0\) with no legs and a set of production \(X\to Y\). Here X is a star graph, whose kernel consists of only one vertex labelled by a nonterminal, and Y is a star graph with the same number of legs as X. The language of graphs defined by such a grammar is the set of all graphs (with only terminal labels) which are derivable from \(X_ 0\) by using the productions. Let \(NC^ i\) be the class of problems coumputable by a parallel random access machine. Then, recognition and parsing of graphs generated by such a grammar is i \(NC^ 2\), and several NP-complete problems are in \(NC^ 1\), if the parsing tree is given. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Jürgen Ebert / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q45 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68Q25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68R10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 03D15 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 4131695 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
graph grammar | |||
Property / zbMATH Keywords: graph grammar / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
NC | |||
Property / zbMATH Keywords: NC / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
NP-completeness | |||
Property / zbMATH Keywords: NP-completeness / rank | |||
Normal rank |
Revision as of 18:14, 1 July 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Parallel algorithms for a class of graphs generated recursively |
scientific article |
Statements
Parallel algorithms for a class of graphs generated recursively (English)
0 references
1989
0 references
A star graph (G,R) is a kernel graph G and a set of additional pending edges R called legs each having exactly one common vertex with G. The vertices of G are labelled by a terminal and nonterminal symbols. A grammar is given by an axiom star graph \(X_ 0\) with no legs and a set of production \(X\to Y\). Here X is a star graph, whose kernel consists of only one vertex labelled by a nonterminal, and Y is a star graph with the same number of legs as X. The language of graphs defined by such a grammar is the set of all graphs (with only terminal labels) which are derivable from \(X_ 0\) by using the productions. Let \(NC^ i\) be the class of problems coumputable by a parallel random access machine. Then, recognition and parsing of graphs generated by such a grammar is i \(NC^ 2\), and several NP-complete problems are in \(NC^ 1\), if the parsing tree is given.
0 references
graph grammar
0 references
NC
0 references
NP-completeness
0 references