Fusion grammar is a graph grammar formalism introduced in Kreowski et al. (2017), inspired by DNA computing approaches. It enables one to generate hypergraphs using fusion—a transformation that merges two hyperedges with complementary labels and then removes the hyperedges. In Lye et al. (2021), the notion of connection-preserving fusion grammars was introduced. A fusion grammar is connection preserving if, for each hypergraph generated by it, whenever one applies fusion either to its connected component or between two of its connected components, the result is a connected hypergraph. It turns out that several algorithmic and language-theoretic problems are easier to tackle for connection-preserving fusion grammars rather than for general ones. In this work, we study the algorithmic complexity of recognizing the connection preservation property itself. We prove that the problem of checking whether a fusion grammar is connection-preserving is decidable, it belongs to coNEXPTIME and is PSPACE-hard. Bibliography: 11 titles. Illustrations: 5 figures.
