The complexity of graph languages generated by hyperedge replacement (Q2277851): Difference between revisions

Latest revision as of 11:11, 30 July 2024

scientific article

Language	Label	Description	Also known as
English	The complexity of graph languages generated by hyperedge replacement	scientific article

Statements

instance of

scholarly article

0 references

title

The complexity of graph languages generated by hyperedge replacement (English)

0 references

published in

Acta Informatica

0 references

publication date

1990

0 references

review text

Hyperedge replacement grammars (HRGs) are a grammatical formalism for generating classes of graphs. The general parsing problem for HRGs is known to be NP-complete. The author analyses the difficulty of HRG parsing and develops certain conditions, on either the grammars or the input graphs, under which the parsing can be done either in polynomial time, or by efficient parallel algorithms.

0 references

zbMATH Keywords

graph grammars

0 references

hyperedge replacement

0 references

NP-complete

0 references

parsing

0 references

0 references

0 references

MaRDI publication profile

0 references

cites work

Complexity of Finding Embeddings in a <i>k</i>-Tree

0 references

Graph expressions and graph rewritings

0 references

Q4734761

0 references

Q3785989

0 references

Alternation

0 references

Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978

0 references

Towards a complexity theory of synchronous parallel computation

0 references

An axiomatic definition of context-free rewriting and its application to NLC graph grammars

0 references

Context-free graph grammars

0 references

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''

0 references

Nonterminal bounded NLC graph grammars

0 references

A comparison of boundary graph grammars and context-free hypergraph grammars

0 references

Plex languages

0 references

Hyperedge replacement: grammars and languages

0 references

Q3774975

0 references

Q3862379

0 references

Nondeterministic Space is Closed under Complementation

0 references

Q3785990

0 references

String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing

0 references

Q3789084

0 references

Q3795250

0 references

On Some Variants of the Bandwidth Minimization Problem

0 references

Linear and Context-Free Graph Grammars

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Boundary NLC graph grammars—Basic definitions, normal forms, and complexity

0 references

Tree-size bounded alternation

0 references

Context-free grammars as a tool for describing polynomial-time subclasses of hard problems

0 references

On the Tape Complexity of Deterministic Context-Free Languages

0 references

Q3815544

0 references

Properties that characterize LOGCFL

0 references

Q4694744

0 references

full work available at URL

https://doi.org/10.1007/bf00289017

0 references

Identifiers

zbMATH Open document ID

0725.68055

0 references

DOI

10.1007/BF00289017

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:2277851

@@ Property / author @@
+Clemens Lautemann
@@ Property / author: Clemens Lautemann / rank @@
+Normal rank
@@ Property / reviewed by @@
+Giora Slutzki
@@ Property / reviewed by: Giora Slutzki / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Complexity of Finding Embeddings in a <i>k</i>-Tree
+Normal rank
@@ Property / cites work @@
+Graph expressions and graph rewritings
@@ Property / cites work: Graph expressions and graph rewritings / rank @@
+Normal rank
@@ Property / cites work @@
+Q4734761
@@ Property / cites work: Q4734761 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3785989
@@ Property / cites work: Q3785989 / rank @@
+Normal rank
@@ Property / cites work @@
+Alternation
@@ Property / cites work: Alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Graph-grammars and their application to computer science and biology. International workshop Bad Honnef, October 30 November 3, 1978
+Normal rank
@@ Property / cites work @@
+Towards a complexity theory of synchronous parallel computation
+Normal rank
@@ Property / cites work @@
+An axiomatic definition of context-free rewriting and its application to NLC graph grammars
+Normal rank
@@ Property / cites work @@
+Context-free graph grammars
@@ Property / cites work: Context-free graph grammars / rank @@
+Normal rank
@@ Property / cites work @@
+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''
+Normal rank
@@ Property / cites work @@
+Nonterminal bounded NLC graph grammars
@@ Property / cites work: Nonterminal bounded NLC graph grammars / rank @@
+Normal rank
@@ Property / cites work @@
+A comparison of boundary graph grammars and context-free hypergraph grammars
+Normal rank
@@ Property / cites work @@
+Plex languages
@@ Property / cites work: Plex languages / rank @@
+Normal rank
@@ Property / cites work @@
+Hyperedge replacement: grammars and languages
@@ Property / cites work: Hyperedge replacement: grammars and languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q3774975
@@ Property / cites work: Q3774975 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3862379
@@ Property / cites work: Q3862379 / rank @@
+Normal rank
@@ Property / cites work @@
+Nondeterministic Space is Closed under Complementation
+Normal rank
@@ Property / cites work @@
+Q3785990
@@ Property / cites work: Q3785990 / rank @@
+Normal rank
@@ Property / cites work @@
+String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
+Normal rank
@@ Property / cites work @@
+Q3789084
@@ Property / cites work: Q3789084 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3795250
@@ Property / cites work: Q3795250 / rank @@
+Normal rank
@@ Property / cites work @@
+On Some Variants of the Bandwidth Minimization Problem
+Normal rank
@@ Property / cites work @@
+Linear and Context-Free Graph Grammars
@@ Property / cites work: Linear and Context-Free Graph Grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
+Normal rank
@@ Property / cites work @@
+Tree-size bounded alternation
@@ Property / cites work: Tree-size bounded alternation / rank @@
+Normal rank
@@ Property / cites work @@
+Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
+Normal rank
@@ Property / cites work @@
+On the Tape Complexity of Deterministic Context-Free Languages
+Normal rank
@@ Property / cites work @@
+Q3815544
@@ Property / cites work: Q3815544 / rank @@
+Normal rank
@@ Property / cites work @@
+Properties that characterize LOGCFL
@@ Property / cites work: Properties that characterize LOGCFL / rank @@
+Normal rank
@@ Property / cites work @@
+Q4694744
@@ Property / cites work: Q4694744 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/bf00289017
+Normal rank
@@ Property / OpenAlex ID @@
+W2088602194
@@ Property / OpenAlex ID: W2088602194 / rank @@
+Normal rank