Abstract:
In an earlier paper, we presented an extension to the families of P systems,
called hyperdag P systems (hP systems), by proposing a new underlying topological
structure based on the hierarchical dag structure (instead of trees or digraphs).
In this paper, we develop building-block membrane algorithms for discovery of
the global topological structure from the local cell point of view. In doing so, we
propose more convenient operational modes and transfer modes, that depend only
on each of the individual cell rules.
Additionally, we propose two uniform solutions to an open problem: the Fir-
ing Squad Synchronization Problem (FSSP), for hyperdag and symmetric neural
P systems, with anonymous cells. Our solutions take ec + 5 and 6ec + 7 steps,
respectively, where ec is the eccentricity of the commander cell of the digraph un-
derlying these P systems. The rst and fast solution is based on a novel proposal,
which dynamically extends P systems with mobile channels. The second solution is
solely based on classical rules and static channels. In contrast to the previous solu-
tions, which work for tree-based P systems, our solutions synchronize any subset of
the underlying digraph, and do not require membrane polarizations or conditional
rules, but require states, as typically used in hyperdag and neural P systems.
Finally, by extending our initial work on the visualization of hP system mem-
branes with interconnections based on dag structures without transitive arcs, we
propose several ways to represent structural relationships, that may include transi-
tive arcs, by simple-closed planar regions, which are folded (and possibly twisted)
in three dimensional space.