Modeling NP-Problems with Families of Extended Graph-based Reaction Systems

Abstract In this paper, we continue the investigation of graph-based reaction systems. We extend the notion by input and output states as well as admitted context sequences to model explicitly input-output relations and decision problems on the inputs. Moreover, we combine extended graph-based reaction systems into families to cover infinite input-output relations and decision problems on infinite sets of graphs. This is used to model NP-problems on graphs and reductions between them as well as to prove their correctness.