A Tissue P Systems Based Uniform Solution to Tripartite Matching Problem

被引：22

作者：

Niu, Yunyun ^{[1
]}

Pan, Linqiang ^{[1
]}

Perez-Jimenez, Mario J. ^{[2
]}

Rius Font, Miguel ^{[3
]}

机构：

[1] Huazhong Univ Sci & Technol, Dept Control Sci & Engn, Key Lab Image Proc & Intelligent Control, Wuhan 430074, Peoples R China

[2] Univ Seville, Dept Comp Sci & Artificial Intelligence, Res Grp Nat Comp, E-41012 Seville, Spain

[3] Univ Politecn Cataluna, Dept Appl Math 4, Casteldefels 08860, Spain

来源：

FUNDAMENTA INFORMATICAE | 2011年 / 109卷 / 02期

基金：

中国国家自然科学基金;

关键词：

Membrane Computing; Tissue P System; Cell Division; Tripartite Matching Problem; LINEAR-TIME;

D O I：

10.3233/FI-2011-503

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

A tissue P system with cell division is a computing model which has two basic features: intercellular communication and the ability of cell division. The ability of cell division allows us to obtain an exponential amount of cells in linear time and to design cellular solutions to computationally hard problems in polynomial time. In this work we present an efficient solution to the tripartite matching problem by a family of such devices. This solution leads to an interesting open problem whether tissue P systems with cell division and communication rules of length 2 can solve NP-complete problems. An answer to this open problem will provide a borderline between efficiency and non-efficiency in terms of the lengths of communication rules.

引用

页码：179 / 188

页数：10

共 13 条

[1]

Alhazov A, 2003, FUND INFORM, V58, P67

[2]

Alhazov A, 2007, LECT NOTES COMPUT SC, V4664, P122

[3]

[Anonymous], 2002, Membrane Computing. An Introduction

[4] A Linear-time Tissue P System Based Solution for the 3-coloring Problem [J].