首页 | 本学科首页   官方微博 | 高级检索  
     


Non-confluence in divisionless P systems with active membranes
Authors:Antonio E Porreca  Giancarlo Mauri
Affiliation:a Dipartimento di Informatica, Sistemistica e Comunicazione, Università degli Studi di Milano-Bicocca, viale Sarca 336, 20126 Milano, Italy
Abstract:We describe a solution to the SAT problem via non-confluent P systems with active membranes, without using membrane division rules. Furthermore, we provide an algorithm for simulating such devices on a nondeterministic Turing machine with a polynomial slowdown. Together, these results prove that the complexity class of problems solvable non-confluently and in polynomial time by this kind of P system is exactly the class View the MathML source.
Keywords:Membrane computing  Complexity theory
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号