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

DOI10.1016/0166-218X(87)90051-5MaRDI QIDQ1089809zbMATH OpenOpenAlexWikidataFDO

Authors Klaus-Jörn Lange, Emo Welzl

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

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

Recommendations

• Publication:3692891
• Graph Transformations
• Nonterminal separation in graph grammars
• Publication:3830541
• Publication:3219131
• Publication:3339312
• Parsing and generation with static discontinuity grammars
• Graph grammars with string-regulated rewriting
• Structure graphs and structure graph grammars
• Disambiguating grammars by exclusion of sub-parse trees

Cites work

• scientific article; zbMATH DE number 3885330 (Why is no real title available?)
• scientific article; zbMATH DE number 3852433 (Why is no real title available?)
• scientific article; zbMATH DE number 3860410 (Why is no real title available?)
• scientific article; zbMATH DE number 3827238 (Why is no real title available?)
• scientific article; zbMATH DE number 3780558 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• scientific article; zbMATH DE number 3633737 (Why is no real title available?)
• scientific article; zbMATH DE number 3633740 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• A class of linearly parsable graph grammars
• Boundary NLC graph grammars—Basic definitions, normal forms, and complexity
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Context-free graph grammars
• Developmental systems with interaction and fragmentation
• JL systems with non-fragmented axioms: The hierarchy
• On the structure of node-label-controlled graph languages
• Pair grammars, graph languages and string-to-graph translations
• Restrictions, extensions, and variations of NLC grammars

Cited in

(13)

• NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)
• Contextual hyperedge replacement
• Recognising \(k\)-connected hypergraphs in cubic time
• String Generating Hypergraph Grammars with Word Order Restrictions
• Rule-based top-down parsing for acyclic contextual hyperedge replacement grammars
• The complexity of regular DNLC graph languages
• Uniform parsing for hyperedge replacement grammars
• On the structure of linear apex NLC graph grammars
• Graph parsing as graph transformation. Correctness of predictive top-down parsers
• scientific article; zbMATH DE number 3917735 (Why is no real title available?)
• The complexity of graph languages generated by hyperedge replacement
• Graph Transformations
• A hierarchy of eNCE families of graph languages

This page was built for publication: String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1089809)