Dependency Graph Technique Revisited

The dependency graph technique was initially thought as a method to find short paths in the computation tree of a membrane system using weak metrics. It could be used to obtain reasonably fast SAT-solvers, capable of competing with the ones available in the literature. Later on, they were used as a method to demonstrate the non-efficiency of some membrane systems, capturing the dynamics of the systems by a static directed graph structure. Recently, the dependency graphs have also been used to establish negative results in Membrane Computing. Specifically, in this work, demonstrating the inability of a kind of membrane system to solve some decision problems efficiently by means of a single system.