String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing (Q1089809): Difference between revisions

Latest revision as of 10:38, 30 July 2024

scientific article

Language	Label	Description	Also known as
English	String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing	scientific article

Statements

instance of

scholarly article

0 references

title

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

0 references

published in

Discrete Applied Mathematics

0 references

publication date

1987

0 references

review text

The complexity of languages generated by so-called context-free string grammars with disconnecting is investigated. The result is then applied to a number of graph grammar models with finite Church Rosser property. In particular, it is shown that these graph grammars can generate NP- complete languages.

0 references

zbMATH Keywords

complexity of languages

0 references

graph grammar

0 references

finite Church Rosser property

0 references

NP-complete languages

0 references

0 references

0 references

MaRDI publication profile

0 references

0 references

0 references

0 references

Context-free graph grammars

0 references

Q4194478

0 references

A class of linearly parsable graph grammars

0 references

Q4198056

0 references

On the structure of node-label-controlled graph languages

0 references

Restrictions, extensions, and variations of NLC grammars

0 references

Q3673138

0 references

Q4194482

0 references

Pair grammars, graph languages and string-to-graph translations

0 references

Q4140407

0 references

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

0 references

Developmental systems with interaction and fragmentation

0 references

JL systems with non-fragmented axioms: The hierarchy

0 references

Q5678435

0 references

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

0 references

Q3219131

0 references

full work available at URL

https://doi.org/10.1016/0166-218x(87)90051-5

0 references

Identifiers

zbMATH Open document ID

0619.68064

0 references

DOI

10.1016/0166-218X(87)90051-5

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1089809

@@ Property / author @@
-Klaus-Joern Lange
@@ Property / author: Klaus-Joern Lange / rank @@
-Normal rank
@@ Property / author @@
-Ermo Welzl
@@ Property / author: Ermo Welzl / rank @@
-Normal rank
@@ Property / author @@
+Klaus-Joern Lange
@@ Property / author: Klaus-Joern Lange / rank @@
+Normal rank
@@ Property / author @@
+Ermo Welzl
@@ Property / author: Ermo Welzl / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / cites work @@
+Q3959427
@@ Property / cites work: Q3959427 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3321473
@@ Property / cites work: Q3321473 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3327730
@@ Property / cites work: Q3327730 / rank @@
+Normal rank
@@ Property / cites work @@
+Context-free graph grammars
@@ Property / cites work: Context-free graph grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Q4194478
@@ Property / cites work: Q4194478 / rank @@
+Normal rank
@@ Property / cites work @@
+A class of linearly parsable graph grammars
@@ Property / cites work: A class of linearly parsable graph grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Q4198056
@@ Property / cites work: Q4198056 / rank @@
+Normal rank
@@ Property / cites work @@
+On the structure of node-label-controlled graph languages
+Normal rank
@@ Property / cites work @@
+Restrictions, extensions, and variations of NLC grammars
+Normal rank
@@ Property / cites work @@
+Q3673138
@@ Property / cites work: Q3673138 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4194482
@@ Property / cites work: Q4194482 / rank @@
+Normal rank
@@ Property / cites work @@
+Pair grammars, graph languages and string-to-graph translations
+Normal rank
@@ Property / cites work @@
+Q4140407
@@ Property / cites work: Q4140407 / rank @@
+Normal rank
@@ Property / cites work @@
+Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
+Normal rank
@@ Property / cites work @@
+Developmental systems with interaction and fragmentation
+Normal rank
@@ Property / cites work @@
+JL systems with non-fragmented axioms: The hierarchy
+Normal rank
@@ Property / cites work @@
+Q5678435
@@ Property / cites work: Q5678435 / 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 @@
+Q3219131
@@ Property / cites work: Q3219131 / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1016/0166-218x(87)90051-5
+Normal rank
@@ Property / OpenAlex ID @@
+W2041437718
@@ Property / OpenAlex ID: W2041437718 / rank @@
+Normal rank