Parallel algorithms for a class of graphs generated recursively (Q582922): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
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 / 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 | |||
Property / reviewed by | |||
Property / reviewed by: Jürgen Ebert / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0020-0190(89)90199-3 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2070146374 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallelism in random access machines / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3992991 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel O(log n) time edge-colouring of trees and Halin graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Tree-like parse and polynomial subclasses of search problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3759947 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3700838 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5753770 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On efficient parallel computations for some dynamic programming problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of parallel parsing of general context-free languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Parallel time O(log n) recognition of unambiguous context-free languages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Context-free grammars as a tool for describing polynomial-time subclasses of hard problems / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 12:56, 20 June 2024
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