NP-completeness of k-connected hyperedge-replacement languages of order k

DOI10.1016/0020-0190(93)90221-TMaRDI QIDQ1209328zbMATH OpenOpenAlexFDO

Authors 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 graphshyperedge-replacement grammarsNP-complete sets

Mathematics Subject Classification ID

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

Recommendations

• Recognising k-connected hypergraphs in cubic time
• scientific article; zbMATH DE number 809155
• The complexity of graph languages generated by hyperedge replacement
• The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
• The complexity of connectivity problems on context-free graph languages

Cites work

• An axiomatic definition of context-free rewriting and its application to NLC graph grammars
• scientific article; zbMATH DE number 177418 (Why is no real title available?)
• scientific article; zbMATH DE number 177465 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• 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
• The complexity of graph languages generated by hyperedge replacement
• The monadic second-order logic of graphs. V: On closing the gap between definability and recognizability

Cited in

(3)

• The complexity of the \(K_{n,n}\)-problem for node replacement graph languages
• Uniform parsing for hyperedge replacement grammars
• Recognising k-connected hypergraphs in cubic time

This page was built for publication: NP-completeness of \(k\)-connected hyperedge-replacement languages of order \(k\)

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