Deciding non-emptiness of hypergraph languages generated by connection-preserving fusion grammars is NP-complete

DOI10.1007/978-3-030-68195-1_8OpenAlexW3132626418MaRDI QIDQ2232268

Aaron Lye

Publication date: 4 October 2021

Full work available at URL: https://doi.org/10.1007/978-3-030-68195-1_8

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• Context-sensitive fusion grammars are universal
• A simple notion of parallel graph transformation and its perspectives
• Transformation of Petri nets into context-dependent fusion grammars
• `` Strong NP-Completeness Results
• Fusion Grammars: A Novel Approach to the Generation of Graph Languages
• Computationally Related Problems

This page was built for publication: Deciding non-emptiness of hypergraph languages generated by connection-preserving fusion grammars is NP-complete