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

DOI10.1016/0166-218X(87)90051-5zbMath0619.68064OpenAlexW2041437718WikidataQ54309814 ScholiaQ54309814MaRDI QIDQ1089809

Ermo Welzl, Klaus-Joern Lange

Publication date: 1987

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0166-218x(87)90051-5

zbMATH Keywords

graph grammarcomplexity of languagesfinite Church Rosser propertyNP-complete languages

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of compilers and interpreters (68N20)

Related Items

Uniform parsing for hyperedge replacement grammars, A hierarchy of eNCE families of graph languages, Graph Parsing as Graph Transformation, The complexity of regular DNLC graph languages, On the structure of linear apex NLC graph grammars, Contextual hyperedge replacement, Recognising \(k\)-connected hypergraphs in cubic time, NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\), The complexity of graph languages generated by hyperedge replacement, Rule-based top-down parsing for acyclic contextual hyperedge replacement grammars

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the structure of node-label-controlled graph languages
• Restrictions, extensions, and variations of NLC grammars
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• A class of linearly parsable graph grammars
• Pair grammars, graph languages and string-to-graph translations
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Developmental systems with interaction and fragmentation
• JL systems with non-fragmented axioms: The hierarchy
• Context-free graph grammars