NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)

DOI10.1016/0020-0190(93)90221-TzbMath0795.68094OpenAlexW2012843178MaRDI QIDQ1209328

Frank Drewes

Publication date: 16 May 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(93)90221-t

zbMATH Keywords

\(k\)-connected graphsNP-complete setshyperedge-replacement grammars

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Uniform parsing for hyperedge replacement grammars

Cites Work

• Hyperedge replacement: grammars and languages
• Recognising \(k\)-connected hypergraphs in cubic time
• String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing
• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability
• The complexity of graph languages generated by hyperedge replacement
• Unnamed Item
• Unnamed Item
• Unnamed Item