COMPUTATION OF RAMSEY NUMBERS BY P SYSTEMS WITH ACTIVE MEMBRANES

被引：29

作者：

Pan, Linqiang ^{[1
]}

Diaz-Pernil, Daniel ^{[2
]}

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

机构：

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

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

来源：

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE | 2011年 / 22卷 / 01期

基金：

中国国家自然科学基金;

关键词：

Membrane computing; P system; Ramsey number;

D O I：

10.1142/S0129054111007800

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

Ramsey numbers deal with conditions when a combinatorial object necessarily contains some smaller given objects. It is well known that it is very difficult to obtain the values of Ramsey numbers. In this work, a theoretical chemical/biological solution is presented in terms of membrane computing for the decision version of Ramsey number problem, that is, to decide whether an integer n is the value of Ramsey number R(k, l), where k and l are integers.

引用

页码：29 / 38

页数：10

共 9 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness

[2]

ERDOS P, 1985, ANN DISCRETE MATH, V28, P1

[3]

Paun G., 2001, Journal of Automata, Languages and Combinatorics, V6, P75

[4] Computing with membranes [J].

Päun, G .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2000, 61 (01) :108-143

[5]

PAUN G, 2002, NAT COMP SER, pR7, DOI 10.1007/978-3-642-56196-2

[6]

Paun Gh., 2010, Handbook of Membrane Computing

[7]

RADZISZOWSKI SP, 2006, ELECT J COMBIN DYNAM, V1

[8] On a problem of formal logic [J].

Ramsey, FP .

PROCEEDINGS OF THE LONDON MATHEMATICAL SOCIETY, 1930, 30 :264-286

[9]

ROSTA V, 2004, ELECT J COMBIN DYNAM, V13

← 1 →