Tissue P Systems with Look-ahead Mode

Tissue P systems are a class of distributed and parallel computing models inspired from inter-cellular communication and cooperation between cells. In this work, a variant of tissue P system, named tissue P system with look-ahead mode, is discussed for decreasing the inherent non-determinism of tissue P systems and helping implementing tissue P systems on computers. Such systems are proved to be universal by simulating register machine, and they are also proved to be able to efficiently solve computationally hard problems by means of a spacetime tradeoff, which is illustrated with a polynomial solution to 3-coloring problem.