·姓名张葛祥(ZhangGexiang)·性别男
·职称教授·导师类型博导
·所在系电子信息工程系·民族汉
·出生年月1974/4/5(公历)·籍贯四川(Sichuan)
·学位博士·学历研究生
·电子邮件请登陆系统查看·联系电话请登陆系统查看
·个人简历2009-西南交通大学电气工程学院博士研究生导师；2007.11-2008.11英国谢菲尔德大学访问教授；2006-西南交通大学电气工程学院硕士研究生导师；2005-西南交通大学电气工程学院电子信息工程系教授；.(Positions:11/2007-11/2008VisitingProfessorattheUniversityofSheffield;2005-ProfessorattheSchoolofElectricalEngineering,SouthwestJiaotongUniversity)
·获奖情况2008年入选四川省杰出青年学科带头人培养计划和西南交通大学“竢实之星”培养计划；2007年四川省优秀博士论文；2006年西南交通大学优秀博士论文
·科研方向1.理论:(1)现代信号处理，包括信号检测、时频分析、数字信号处理、识别等；(2)软计算：膜计算、进化计算、支持向量机等；(3)数字图像处理：预处理、压缩、特征分析和识别等；(4)模式识别：特征分析、特征选择、分类器设计；(5)软件测试和验证；2.应用：(1)雷达；(2)电力系统；(3)交通。(Researchinterests:1.Theory:(1)Modernsignalprocessing,suchasdetection,time-frequencyanalysis,digitalsignalprocessingandrecognition;(2)Softcomputing:membranecomputing,evolutionarycomputationandsupportvectormachines;(3)Digitalimageprocessing:preprocessing,compression,featureanalysisandrecognition;(4)Patternrecognition:featureexactionandselection,classifiers;(5)Softwaretestingandverification;2.Applications:(1)Radarsystems;(2)Powersystems;(3)Trafficsystems.)
·学术兼职及称号中国电子学会高级会员；霍英东青年教师基金及青年教师奖评审专家；教育部学位论文评审、学科建设和评估专家；教育部科研基金和科技奖励评审专家；成都市科技评估专家；Member:IEEE,IIISandIRSS;Reviewers:IEEETEC,IEEESMC,WCMC,CJE,etc;ProgramCommitteeMember:ICAL2007,KGCM2007,KGCM2008,MDAI2008,MDAI2009;TechnicalCommitteemember:WCCI2008,WMSCI2009.
·主持项目主要科研项目：
1.国家自然科学基金项目:复杂体制雷达辐射源信号本征时频原子特征挖掘模型与算法,2008-2010,主持;
2.四川省杰出青年基金项目:复杂体制雷达辐射源信号分选识别模型与算法研究,2009-2011,主持;
3.教育部工程研究中心开放式基金,交通系统的数学物理模型与方法,2008-2010,主持;
4.智能交通图像处理技术，横向课题，2009-2011,主持;
5.国家自然科学基金项目:复杂体制雷达辐射源信号分选识别机理与模型,2006-2008,主研;
6.国家电子对抗国防科技重点实验室基金项目:雷达辐射源信号分选识别新算法研究,2004-2006,主研;
Partsoffundedresearchprojects(Englishversion):
1.Modelsandalgorithmsforextractingintrinsicaltime-frequencyatomfeaturesofadvancedradaremittersignals,NationalNaturalScienceFoundationofChina,2008-2010,principalinvestigator;
2.Modelsandalgorithmsfordeinterleavingandrecognizingadvancedradaremittersignals,ScientificFundsforOutstandingYoungScientistsofSichuan,2009-2011,principalinvestigator;
3.Mathematical/physicalmodelsandmethodsfortrafficsystems,OpenFoundationofEngineeringResearchCenteroftheMinistryofEducationofChina,2008-2010,principalinvestigator;
4.Imageprocessingtechniquesforintelligenttransportationsystems,fundedbyacorporation,2009-2011,principalinvestigator;
5.Mechanismandmodelsfordeinterleavingandrecognizingadvancedradaremittersignals,NationalNaturalScienceFoundationofChina,2006-2008,Projectpartners;
6.Novelalgorithmsfordeinterleavingandrecognizingadvancedradaremittersignals,NationalEWLaboratoryFoundation,2004-2006,Projectpartners.
·发表论文以第一作者发表学术论文50余篇,其中SCI论文20余篇、EI论文30余篇；合作者论文30余篇.
Listofselectedpapers
1.Ge-XiangZhang,MarianGheorghe,Chao-ZhongWu,Aquantum-inspiredevolutionaryalgorithmbasedonPsystemsforknapsackproblem,FundamentaInformaticae,IOSPress,2008,87(1):93-116.
2.Ge-XiangZhang,Time-FrequencyAtomDecompositionwithQuantum-InspiredEvolutionaryAlgorithms,Circuits,Systems&SignalProcessing,Springer,2009,accepted.
3.GexiangZhang,XuLi.ANewRecognitionSystemforRadarEmitterSignals.Kybernetes,Emeraldpress,2009,accepted.
4.GexiangZhang,WeidongJin,LaizhaoHu.Resemblancecoefficientbasedintrapulsefeatureextractionapproachforradaremittersignals.ChineseJournalofElectronics,2005,14(2):337-341.
·出版专著1.MATLAB仿真技术与应用.北京:清华大学出版社,2003.
2.经牛津大学出版社和编者允许，与英国谢菲尔德大学计算机系MarianGheorghe博士和两个学生刘春秀、胡炳谦合作，将《膜计算手册》的前言、目录、各章节摘要翻译成中文如下(PermittedbytheOxfordUniversityPress(www.oup.co.uk)andtheeditors,Dr.MarianGheorghe,attheDepartmentofComputerScience,UniversityofSheffield,U.K.,twostudents,ChunxiuLiuandBingqianHu,andIcooperatedtotranslatethepreface,contentsandabstractofeachchapterofthebookentitled“HandbookofMembraneComputing”intoChineseasfollows):
译者按:该书是由膜计算的提出者，罗马尼亚科学院和欧洲科学院院士GheorghePaun、荷兰莱顿大学终身教授GrzegorzRozenberg和欧洲科学院院士，芬兰图尔库大学教授ArtoSalomaa合作编著，全球膜计算领域几十位顶尖学者共同编写的最新著作，涵盖膜计算理论与应用研究的最新进展。
膜计算手册
编者:GheorghePaun(布加勒斯特,罗马尼亚);GrzegorzRozenberg(莱顿,荷兰);ArtoSalomaa(图尔库,芬兰)
顾问委员会:
E.Csuhaj-Varju(布达佩斯,匈牙利);R.Freund(维也纳,奥地利);M.Gheorghe(谢菲尔德,英国);O.H.Ibarra(圣芭芭拉,美国);V.Manca(维罗纳,意大利);G.Mauri(米兰,意大利);M.J.Perez-Jimenez(塞维利亚,西班牙)
译者:张葛祥(成都,中国);M.Gheorghe(谢菲尔德,英国);刘春秀(成都,中国);胡炳谦(成都,中国)
出版社:牛津大学出版,2009年12月.
编者联系信息:
(1)GheorghePaun
InstituteofMathematicsoftheRomanianAcademy
POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing
DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla
Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
(2)GrzegorzRozenberg
LeidenInstituteofAdvancedComputerScience(LIACS)
LeidenUniversity
NielsBohrweg1,2333CALeiden,TheNetherlands,and
DepartmentofComputerScience
UniversityofColoradoatBoulder
Boulder,CO80309,U.S.A.
rozenber@liacs.nl
(3)ArtoSalomaa
TurkuCentreforComputerScience—TUCS
Lemminkaisenkatu14A,20520Turku,Finland
asalomaa@utu.fi
前言
膜计算是自然计算的一个分支,旨在从生物细胞的结构和功能中,以及从组织、器官等细胞群的细胞协作中,抽象出计算模型,即膜系统.该研究方向于1998年创建,并已迅速发展成具有勃勃生机的科学领域.2003年美国汤姆森科学情报所(ISI)已经将该领域称为计算机科学中快速新起的研究前沿.的确如此，自从第一篇膜计算文章在网上发表(2000年在学术期刊上正式发表)至今约10年时间,已有相关参考文献1200多篇,包括约25篇博士论文,30本论文集和15本国际期刊专刊.许多种P系统(当前称为膜系统)已经从数学,计算机科学或者生物学角度建立起来了.相当宽领域的膜计算理论已经创建.其应用不仅渗透到生物和生物医学,还涉及到一些出乎意料的领域,如经济学,近似优化,计算机图形学等.大量膜系统的实现也正在尝试.
每年组织两个关于膜计算的专题国际会议:一个是膜计算研讨会,2000年开始于罗马尼亚的克提阿吉(2008年在英国的爱丁堡举行);另一个是膜计算的集体讨论会,每年二月初在西班牙塞尔维亚举行.几个关于生物计算的国际会议,要么有膜计算的专题,要么有膜计算的额外研讨会.这些会议均有论文集或国际期刊专刊出版.有关膜计算的研究成果迅速增加,以至于不可能被某一位作者或几位作者编写的单行本所涵盖(2002年,这种情况仍是可能的,当时我们编者中的一位撰写并由德国施普林格出版社出版了膜计算单行本).由此,我们决定编写这书“膜计算手册”.
该手册旨在提供主流学者研究进展(截至2008年)的概况,应该成为膜计算一般/非正式级和技术水平级的主要参考资料.通过每一章的参考文献,该手册还提供广泛的文献导引.而且,该手册也是膜计算领域感兴趣/具有挑战性研究问题和方向的参考文献.
本手册内容组织方式为:各章之间相互独立,每一章有单独的必备知识和参考文献.为方便各章阅读,我们准备了一章关于基本概念,符号和可计算性与形式语言理论的相关内容(第三章)?这些知识可用于全书的阅读.此外,还专门为初学者撰写了膜计算的绪论和综述.
更具体地说,本手册包含20章(其中一章有辅助章节)和三个介绍性/必备知识章节.它们一起描述了膜计算研究的主要方向,涵盖理论,应用和实现/软件问题.最后,此书还提供了有价值的参考书目列表,其中包括书籍,论文集,博士学位论文和国际期刊专辑等.
有兴趣的读者可以在网站http://ppage.psystems.eu(或者http://psystems.disco.unimib.it,该网页已建立10来年了)上找到膜计算的完整参考书目列表(包含大量该领域的额外信息).
编者深深感谢所有对此书做过贡献的人,感谢此次愉快的合作和他们对此书及时出版所做的一切.
我们还要感谢牛津大学出版社,特别感谢AlisonJones和DewiJackson为此书出版的高效率合作.
GheorghePaun,GrzegorzRozenberg,ArtoSalomaa
2008年9月
目录
1.膜计算绪言和概述
Gh.Paun,G.Rozenberg(1)
2.膜计算中的细胞生物学
D.Besozzi,I.I.Ardelean(25)
3.膜计算中的可计算性要素
Gh.Paun,G.Rozenberg,A.Salomaa(53)
4.催化P系统
R.Freund,O.H.Ibarra,A.Paun,P.Sosik,H.-C.Yen(77)
5.通信P系统
R.Freund,A.Alhazov,Y.Rogozhin,S.Verlan(109)
6.P自动机
E.Csuhaj-Varju,M.Oswald,G.Vaszil(133)
7.字符串型P系统
C.Ferretti,G.Mauri,C.Zandron(155)
8.拼接型P系统
S.Verlan,P.Frisco(183)
9.组织和种群型P系统
F.Bernardini,M.Gheorghe(209)
10.ConformonP系统
P.Frisco(231)
11.活性膜
Gh.Paun(259)
12.复杂性—膜分裂,膜创建
M.J.Perez-Jimenez,A.Riscos-Nunez,A.Romero-Jimenez,D.Woods(277)
13.尖峰神经型P系统
O.H.Ibarra,A.Leporati,A.Paun,S.Woodworth(311)
14.膜对象P系统
M.Cavaliere,S.N.Krishna,A.Paun,Gh.Paun(335)
15.Petri网与膜计算
J.Kleijn,M.Koutny(359)
16.P系统语义学
G.Ciobanu(381)
17.P系统软件
D.Diaz-Pernil,C.Graciani,M.A.Gutierrez-Naranjo,I.Perez-Hurtado,M.J.Perez-Jimenez(403)
18.概率/随机模型
P.Cazzaniga,M.Gheorghe,N.Krasnogor,G.Mauri,D.Pescini,F.J.Romero-Campero(421)
19.代谢P系统的基本原理
V.Manca(439)
20.代谢P动态性
V.Manca(461)
21.膜算法
T.Y.Nishida,T.Shiotani,Y.Takahashi(489)
22.膜计算与计算机科学
R.Ceterchi,D.Sburlan(511)
23.其它方面
23.1.P群
A.Kelemenova(539)
23.2.膜计算时间
M.Cavaliere,D.Sburlan(548)
23.3.膜计算与自动装配
M.Gheorghe,N.Krasnogor(558)
23.4.膜计算与X-机
P.Kefalas,I.Stamatopoulou,M.Gheorghe,G.Eleftherakis(564)
23.5.Q-UREMP系统
A.Leporati(572)
23.6.膜计算与经济学
Gh.Paun,R.A.Paun(582)
23.7.移动膜与移动环境
B.Aman,G.Ciobanu(593)
23.8.其它议题
Gh.Paun,G.Rozenberg(600)
代表性参考书目(611)
概念索引(617)
第一章膜计算绪言和概述
GheorghePaun1,GrzegorzRozenberg2
1InstituteofMathematicsoftheRomanianAcademy,POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
2LeidenInstituteofAdvancedComputerScience(LIACS),LeidenUniversity,
NielsBohrweg1,2333CALeiden,TheNetherlands,and
DepartmentofComputerScience,UniversityofColoradoatBoulder,Boulder,CO80309,U.S.A.
rozenber@liacs.nl
摘要:本章旨在介绍膜计算的基本概念(以及概念产生的动机)和形式,以及概括主要研究方向.这样,本章是膜计算和本书的指南.在阅读其它章节前,最好先阅读本章(第2和3章除外).
第二章膜计算中的细胞生物学
DanielaBesozzi1,IoanI.Ardelean2
1UniversitadegliStudidiMilano,DipartimentodiInformaticaeComunicazione
ViaComelico39,20135Milano,Italy
besozzi@dico.unimi.it
2InstituteofBiologyoftheRomanianAcademy,CentreofMicrobiology,SplaiulIndependentei296
POBox56-53,Bucharest060031,Romania,and
OvidiusUniversity,BulevardulMamaia124,900527Constanta,Romania
ioan.ardelean@ibiol.ro
摘要:本章提供理解细胞结构和膜计算模型产生过程的一些有用必备知识.先详细描述原核与真核两种细胞之间的差异,随后重点讨论细胞膜(组成、传输和受体蛋白、电化学势)和细胞内过程(代谢、基因表达,信号转导)的某些特点.然后,给出两种超细胞级生物组织,即多细胞生物体组织结构和细菌细胞群类似种群行为.
第三章膜计算中的可计算性要素
GheorghePaun1,GrzegorzRozenberg2,ArtoSalomaa3
1InstituteofMathematicsoftheRomanianAcademy,POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
2LeidenInstituteofAdvancedComputerScience(LIACS),LeidenUniversity
NielsBohrweg1,2333CALeiden,TheNetherlands,and
DepartmentofComputerScience,UniversityofColoradoatBoulder,Boulder,CO80309,U.S.A.
rozenber@liacs.nl
3TurkuCentreforComputerScience—TUCS,Lemminkaisenkatu14A,20520Turku,Finland
asalomaa@utu.fi
摘要:本章介绍后续章节必需的大部分可计算性要素(概念,定义和结果).回顾从语言到自动机,以及从计算复杂性到自动机理论的基本知识.本章最后的参考文献给出在膜计算中较少使用的详细且更为专业的概念和结果.
第四章催化P系统
RudolfFreund1,OscarH.Ibarra2,AndreiPaun3,4,PetrSosik4,5,Hsu-ChunYen6
1InstituteofComputerLanguages,ViennaUniversityofTechnologyFavoritenstrabe9-11,A-1040Vienna,Austria
rudi@emcc.at
2DepartmentofComputerScience,UniversityofCalifornia,SantaBarbara,CA93106,USA
ibarra@cs.ucsb.edu
3NationalInstituteofResearchandDevelopmentforBiologicalSciences,BioinformaticsDepartment
SplaiulIndependentei,Nr.296,Sector6,Bucharest,Romania
andreipaun@gmail.com
4UniversidadPolitecnicadeMadrid,DepartamentodeInteligenciaArtificial
CampusdeMontegancedoS/N,BoadillodelMonte,28660Madrid,Spain
5InstituteofComputerScience,SilesianUniversity,74601Opava,CzechRepublic
petr.sosik@fpf.slu.cz
6Dept.ofElectricalEngineering,NationalTaiwanUniversity,Taipei,Taiwan106,ROC
yen@cc.ee.ntu.edu.tw
摘要:本章描述基本P系统和个别改进型催化P系统的计算能力,特别是仅采用催化规则时的情况.给出一些具有普遍性的结果,而且还考虑仅产生正则集的转移模型.再者,不仅将催化P系统作为产生自然数集(或向量)的装置考虑,且作为接收器和产生形式语言的装置考虑.最后,讨论了几种确定性系统和功能更强的多种催化规则.
第五章通信P系统
RudolfFreund1,ArtiomAlhazov2,YuriiRogozhin2,3,SergeyVerlan2,4
1InstituteofComputerLanguages,ViennaUniversityofTechnology
Favoritenstrabe9-11,A-1040Vienna,Austria
rudi@emcc.at
2AcademyofSciencesofMoldova,InstituteofMathematicsandComputerScience
Academiei,MD-2028,Chisinau,Moldova
fartiom,rogozhing@math.md
3RoviraiVirgiliUniversity,ResearchGrouponMathematicalLinguistics
Pl.ImperialTarraco1,43005Tarragona,Spain
4UniversiteParis12,LACL,DepartmentInformatique,61av.GeneraldeGaulle,94010Creteil,France
verlan@univ-paris12.fr
摘要:本章讨论仅通过区域间通信对象进化的各种P系统模型.探讨不同过渡模式与停止条件的组合方式下的计算功率.研究了正运输和逆运输规则系统的描述复杂性,以及在不同膜数,符号数和规则数目与大小情况下的结果.
第六章P自动机
ErzsebetCsuhaj-Varju1,MarionOswald2,GyorgyVaszil1
1ComputerandAutomationResearchInstitute,HungarianAcademyofSciences
Kendeu.13-17,H-1111Budapest,Hungary
{fcsuhaj,vaszilg}@sztaki.hu
2FacultyofInformatics,ViennaUniversityofTechnology,Favoritenstr.9,A-1040Vienna,Austria
marion@emcc.at
摘要:P自动机是多数情况下只有通信规则的接受P系统.P自动机结合了经典自动机和与环境相互作用的分布式自然系统的特点.这些P系统把表示环境对象的多重集送入到表层膜中.P自动机的行为可由接受语言描述.而接受语言可由环境进入系统的对象多重集的接受序列集映射得到.本章描述了几种最重要的P自动机以及它们的性质,特别强调其计算能力.
第七章字符串型P系统
ClaudioFerretti,GiancarloMauri,ClaudioZandron
DipartimentodiInformatica,SistemisticaeComunicazione
UniversitadegliStudidiMilano-BicoccavialeSarca336,I-20126,Milano,Italy
mauri/zandron@disco.unimib.it
摘要:本章介绍用字符串描述和用重写规则(普通规则或复制规则)处理对象的P系统.讨论了这种P系统的计算能力.
第八章拼接型P系统
SergeyVerlan1,PierluigiFrisco2
1LACL,DepartementInformatique,UniversiteParis-Est61,av.GeneraldeGaulle,94010,Creteil,France
verlan@univ-paris12.fr
2SchoolofMathematicalandComputerSciences,Heriot-WattUniversity,Edinburgh,EH144AS,U.K.
pier@macs.hw.ac.uk
摘要:概括一类将拼接操作(含DNA分子和酶的生物过程的抽象)用于字符串的P系统.讨论了多种拼接(组织)P系统模型及其最重要结果.还描述了通用拼接P系统.
第九章组织和种群型P系统
FrancescoBernardini1,MarianGheorghe2
1LeidenInstituteofAdvancedComputerScience-LIACS,LeidenUniversity
NielsBohrweg1,2333CALeiden,TheNetherlands
bernardi@liacs.nl
2DepartmentofComputerScience,TheUniversityofSheffield
RegentCourt,PortobelloStreet,SheffieldS14DP,UK
m.gheorghe@dcs.shef.ac.uk
摘要:介绍作用于符号和字符串对象的组织和群体P系统的主要类型及其广义类型和应用.
第十章ConformonP系统
PierluigiFrisco
Heriot-WattUniversity,SchoolofMathematicalandComputerSciences
Riccartoncampus,EdinburghEH144AS,UnitedKingdom
pier@macs.hw.ac.uk
摘要:作为计算装置和生物建模平台的两种ConformonP系统都已经进行了研究.本章完整地概括了其计算能力的研究结果,并描述了它们如何成功用于对艾滋病病毒感染的动力学特性进行建模.
第十一章活性膜
GheorghePaun
InstituteofMathematicsoftheRomanianAcademy,POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
摘要:本章介绍规则直接作用于膜及使计算过程中膜结构进化的一类P系统,称为活性膜P系统.其重要规则是使膜的数目增加,特别地,使膜分裂.除了介绍活性膜的各种规则,还简要讨论了此类P系统的计算能力.本书其它章节将利用活性膜P系统的增强并行性,如膜分裂,求解计算难问题.
第十二章计算复杂性—膜分裂,膜创建
MarioJ.Perez-Jimenez,AgustinRiscos-Nunez,AlvaroRomero-Jimenez,DamienWoods
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
marper@us.es;ariscosn@us.es
alvaro.romero@cs.us.es;dwoods@us.es
摘要:本章讨论了P系统框架下的计算复杂性理论,修改了经典复杂性理论中的概念.更准确地说,采用问题可求解性概念和识别机P系统,定义了不同P系统模型中的复杂性类型.
基本转移P系统计算效率局限性致使需要考虑能在多项式时间内产生指数计算资源的其它特性(用于膜分裂和膜创建的规则).全面概述了已有结果,就(高效地)解决计算难问题所需(最小)要素特别分析了有效率与无效率间的前沿问题.
这些非传统计算模型引起了P≠NP假设的许多有趣特性.
第十三章尖峰神经型P系统
OscarH.Ibarra1,AlbertoLeporati2,AndreiPaun3,SaraWoodworth1
1DepartmentofComputerScience,UniversityofCalifornia,SantaBarbara,CA93106,USA
fibarra,swoodg@cs.ucsb.edu
2DipartimentodiInformatica,SistemisticaeComunicazione
UniversitμadegliStudidiMilano-BicoccavialeSarca336/14,20126,Milano,Italy
ttleporati@disco.unimib.it
3NationalInstituteofResearchandDevelopmentforBiologicalSciences
BioinformaticsDepartment,SplaiulIndependentei,Nr.296,Sector6,Bucharest,Romania,and
UniversidadPolitecnicadeMadrid,DepartimentodeInteligenciaArtificial,FacultaddeInformatica
CampusdeMontegancedoS/N,BoadillodelMonte,28660Madrid,Spain
andreipaun@gmail.com
摘要:本章介绍了P系统的变体,即尖峰神经型P系统(简写为SNP系统).SNP系统用于我们所知的网络中神经元相互作用完成“计算”的方式进行建模.先给出基本定义及例子,然后讨论了广义型SNP系统,并导出一些重要性质.特别地,回顾了由SNP系统获得的几种正规形式.接着,探讨了“异步”方式作用的几类系统:普通型,无约束和有约束异步系统.不同情况得到不同的结果.一种相关模型是顺序SNP系统.给出这类系统普遍性的结果:顺序无约束系统具有普遍性,强顺序普通系统具有普遍性,但强顺序无约束系统不具有普遍性.随后,简短地讨论了这些系统的封闭性和可判定性,结果显示,这些SNP系统计算得到的数集族在合并,相交和互补情况下是封闭的,且集合元素,空集,无穷集和可达集是可判定的.其它性质是不可判定的.接下来给出了由尖峰数导出的顺序性方面的近期结果,即最大顺序性(甚至在强顺序模式下)仍具有普遍性.再其次,探讨了将SNP系统作为语言产生器方面的应用和产生字符串的两种方式,并给出多种结果.最后,讨论了如何将SNP系统用来求解计算难(NP完全)决策问题,包括数值(子集求和)和非数值(SAT和3-SAT)问题.由于采用自然数编码构成实例,数值问题更受关注.
第十四章膜对象P系统
MatteoCavaliere1,ShankaraNarayananKrishna2,AndreiPaun3,GheorghePaun4
1TheMicrosoftResearch-UniversityofTrento
CentreforComputationalandSystemsBiology,CoSBi,Trento,Italy
cavaliere@cosbi.eu
2DepartmentofComputerScienceandEngineering
IndianInstituteofTechnology,Bombay,Poway,Mumbai,400076India
krishnas@cse.iitb.ac.in
3NationalInstituteofResearchandDevelopmentforBiologicalSciences,BioinformaticsDepartment
SplaiulIndependentei,Nr.296,Sector6,Bucharest,Romania,and
UniversidadPolitecnicadeMadrid,DepartimentodeInteligenciaArtificial,FacultaddeInformatica
CampusdeMontegancedoS/N,BoadillodelMonte,28660Madrid,Spain
andreipaun@gmail.com
4InstituteofMathematicsoftheRomanianAcademy,POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
摘要:本章讨论对象只置于膜上或同时置于膜上和放在膜分隔的区域内的几类P系统.这来源于生物学的观察,在基本P系统中,这些情况被忽略了,对象仅在膜结构的区域内演化.考虑了三种主要类型的系统:(i)源自凯德利膜微积分系统(对象与膜一起进化,通过外吞噬与内吞噬操作,称为膜(mem)系统或(brane)膜系统),(ii)束缚在膜上的对象控制邻近区域内对象演化的系统(称为“Ruston模型”),(iii)对象同时置于膜上和区域内且能改变位置的系统(称为“Trento模型”).除了介绍这些模型,本章还给出了典型结果和证明,并提供了完整的参考文献,以供读者查找详细信息.
第十五章Petri网与膜计算
JettyKleijn1,MaciejKoutny2
1LeidenInstituteofAdvancedComputerScience-LIACS
LeidenUniversity,NielsBohrweg1,2333CALeiden,TheNetherlands
kleijn@liacs.nl
2SchoolofComputingScience,NewcastleUniversity,NewcastleuponTyne,NE17RU,UnitedKingdom
maciej.koutny@ncl.ac.uk
摘要:Petri网是一种公认的并行分布式计算模型,提供了多种分析和验证Petri网行为特性的工具.与膜系统类似,Petri网本质上是多重集重写系统.用此共性,描述了从基本膜系统到Petri网的可靠转换.还讨论了能处理助催化剂与抑制剂以及动态改变膜结构的变换.为了俘获膜系统的隔间,采用区域将Petri网模型进行拓展,并给出如何修改以适合Petri网过程的概念.这使得根据正在发生的反应之间的因果关系描述膜系统中正发生的并行行为成为可能.
第十六章P系统语义学
GabrielCiobanu
RomanianAcademy,InstituteofComputerScience
and“A.I.Cuza”UniversityofIasi,Blvd.CarolIno.8,700505Iasi,Romania
gabriel@info.uaic.ro,gabriel@iit.tuiasi.ro
摘要:本章致力于P系统语义学,特别是P系统操作语义学.先阐述膜系统的抽象语法,采用与最大并行重写,并行通信和并行解除相对应的三个推理法则集定义P系统的结构化操作语义学.然后给出基于操作语义学的P系统实现,以及纠错的一些结果.
采用给定的寄存器膜表示法,可以描述包括催化和抑制规则在内的演化过程.该过程使用动态和静态分配资源给规则的方式进行表示,并证明了这些语义学是等价的.动态分配允许膜规则的最大并行应用转化成顺序重写.
第十七章P系统软件
DanielDiaz-Pernil,CarmenGraciani,MiguelA.Gutierrez-Naranjo,
IgnacioPerez-Hurtado,MarioJ.Perez-Jimenez
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
{sbdani,cgdiaz,magutier,perezh,marper}@us.es
摘要:近年来,报道了大量仿真P系统的软件工具.本章将概述这些软件的研究现状.
第十八章概率/随机模型
PaoloCazzaniga1,MarianGheorghe2,NatalioKrasnogor3,
GiancarloMauri1,DarioPescini1,FranciscoJ.Romero-Campero3
1DipartimentodiInformatica,SistemisticaeComunicazione
UniversitμadegliStudidiMilano-Bicocca,VialeSarca336,20126Milano,Italy
fcazzaniga,mauri,pescinig@disco.unimib.it
2DepartmentofComputerScience,TheUniversityofSheffield
RegentCourt,PortobelloStreet,SheffieldS14DP,UK
m.gheorghe@dcs.shef.ac.uk
3SchoolofComputerScience,TheUniversityofNottingham,JubileeCampus,NottinghamNG81BB,UK
natalio.krasnogor@nottingham.ac.uk,fxc@cs.nott.ac.uk
摘要:介绍概率/随机P系统和与细胞生物学主要分子相互作用相关的建模原则.讨论了支持形式验证和分析的方法,以及表明这些模型能力和适用性的许多案例.
第十九章代谢P系统的基本原理
VincenzoManca
DepartmentofComputerScience,VeronaUniversity,StradaLeGrazie,15-37134Verona,Italy
vincenzo.manca@univr.it
摘要:代谢P系统(简称MP系统)是一类特殊的确定性P系统,用于表示生物新陈代谢.通过一类特殊的正则多重集重写分析其动态特性.本章给出MP系统的基本结果和由观测的动态特性的时间序列构建生物过程的MP模型的程序.
第二十章代谢P动态性
VincenzoManca
DepartmentofComputerScience,VeronaUniversity,StradaLeGrazie,15-37134Verona,Italy
vincenzo.manca@univr.it
摘要:概括了分析动态问题的一般框架,根据半确定性和波动性,提出与生物学相关联的动态概念的一些定义.通过振动模式的重要例子,用代谢P系统详述了P系统的动态性.给出合成代谢和分解代谢的离散化方法,以从生化反应的能量方面证明了代谢P系统的通用性.
第二十一章膜算法
TaishinY.Nishida,TatsuyaShiotani,YoshiyukiTakahashi
FacultyofEngineering,ToyamaPrefecturalUniversity
Kosugi-machi,Toyama939-0398,Japan
nishida@pu-toyama.ac.jp
摘要:本章给出构成近似计算框架的膜算法.解释了膜算法从P系统继承了什么和膜算法给P系统带来了什么新的想法.简要讨论了膜算法的五种应用:旅行商问题,车间作业调度问题,最小存贮问题和两种函数优化应用问题.
第二十二章膜计算与计算机科学
RodicaCeterchi1,DragosSburlan2
1FacultyofMathematicsandComputerScience,UniversityofBucharest,Academiei14,Bucharest,Romania
rceterchi@gmail.com
2FacultyofMathematicsandInformatics,OvidiusUniversity,124MamaiaBd.,Constantza,Romania
dsburlan@univ-ovidius.ro
摘要:本章围绕P系统一般框架的主要应用领域进行组织,包括分类,计算机图形学,密码学和并行结构.这些应用说明了如何将P系统的一般理论与应用技术结合以求解一些重要的计算机科学问题.
第二十三章其他发展
23.1.P群
AlicaKelemenova
InstituteofComputerScience,SilesianUniversity,Bezrucovonam.13,74601Opava,CzechRepublic,and
DepartmentofComputerScience,CatholicUniversity,Nam.A.Hlinku56,03401Ruzomberok,Slovakia
alica.kelemenova@fpf.slu.cz
摘要:P群是由在共享环境中反应性地作用和演化的单个独立的膜代理组成的抽象计算装置.本节讨论以并行和顺序模式工作的P群,以及在对规则和细胞使用的程序有不同限制情况下的P群.本节旨在论述P群的生长能力,以确定P群的参数,从而保证P群的一般生长能力,以及估计P群在某些非一般情况下的生长能力.
23.2.膜计算时间
MatteoCavaliere1,DragosSburlan2
1MicrosoftResearch-UniversityofTrento,CentreforComputationalandSystemsBiology,CoSBi,Trento,Italy
cavaliere@cosbi.eu
2FacultyofMathematicsandInformatics,OvidiusUniversity,124MamaiaBd.,Constantza,Romania
dsburlan@univ-ovidius.ro
摘要:从定时P系统的想法开始,简短地综述了膜计算中时间的使用.在定时P系统中,每一条规则有一定的执行时间.接着介绍了与时间无关P系统的概念,并给出与时间无关P系统的通用性和可判定性结果.然后讨论时间如何用于支持计算,特别是考虑把两个具体事件间的时间作为计算结果的系统的计算能力的情况.在这方面,本节也分析了如何用时间构造能求解(图灵)不可判定问题的系统.
23.3.膜计算与自动装配
MarianGheorghe1,NatalioKrasnogor2
1DepartmentofComputerScience,TheUniversityofSheffield
RegentCourt,PortobelloStreet,SheffieldS14DP,UK
m.gheorghe@dcs.shef.ac.uk
2SchoolofComputerScience,TheUniversityofNottingham,JubileeCampus,NottinghamNG81BB,UK
natalio.krasnogor@nottingham.ac.uk
摘要:本节给出多种计算模型(粘贴系统,P系统,进化计算)与自动装配之间相互作用的一些最新研究进展,支持充分,直观,但完全形式化的模型及其在描述自动装配系统中的效率.
23.4.膜计算与X-机
PetrosKefalas1,IoannaStamatopoulou1,MarianGheorghe2,GeorgeEleftherakis1
1DepartmentofComputerScience,CITYCollege,13Tsimiskistr.,54624,Thessaloniki,Greece
fkefalas,eleftherakisg@city.academic.gr,istamatopoulou@seerc.org
2DepartmentofComputerScience,UniversityofSheffield
RegentCourt,211Portobellostr.,SheffieldS14DP,UK
M.Gheorghe@dcs.shef.ac.uk
摘要:本节讨论P系统与状态模型间的关系.在非常多的状态模型中,选择X机的原因是它具有对复杂数据结构,通过转移函数作用的复杂操作和用元素间通信机制实现的复杂相互作用进行建模的能力.简要描述了某些类型的P系统如何转换来完成X机通信及其反过程,获得的转换之外的好处,以及结合两种模型求解复杂问题或者有效说明如多代理系统之类的动态系统的潜力.
23.5.Q-UREMP系统
AlbertoLeporati
DipartimentodiInformatica,SistemisticaeComunicazione
UniversitadegliStudidiMilano–Bicocca,VialeSarca336/14,20126Milano,Italy
alberto.leporati@unimib.it
摘要:Q-UREMP系统是尝试将量子力学中的概念和技术,如态叠加和量子并行性,引入到膜计算中来探讨相应的概念和技术.本节将简要回顾Q-UREMP系统的定义和计算能力方面的结果.我们将进一步看到,Q-UREMP系统的定义和作用不同于通常见到的量子计算文献.这对Q-UREMP系统的计算能力有重要作用:可能实现任何非幺正操作和执行系统的态的特殊投影.所有这些特点有助于在多项式时间内求解NP完全问题3-SAT,而这个问题目前被认为在“传统”量子计算机上是不可能解决的.
23.6.膜计算与经济学
GheorghePaun1,RaduA.Paun2
1InstituteofMathematicsoftheRomanianAcademy,POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence,
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
2DepartmentofEconomics,UniversityofMarylandatCollegePark
3105TydingsHall,CollegePark,MD20742,USA,and
CompetitionCouncilofRomania,ResearchDepartment
1,PiataPreseiLibere,BuildingD,013701Bucharest,Romania
paun@econ.umd.edu,radu.paun@consiliulconcurentei.ro
摘要:本节给出采用膜计算对经济过程进行建模的两点尝试:一是讨论了建模的可能性;二是讨论了看似可行的生产商—零售商—消费者之间相互作用的表示方法.
23.7.移动膜与移动环境
BogdanAman,GabrielCiobanu
RomanianAcademy,InstituteofComputerScienceand“A.I.Cuza”UniversityofIasi
Blvd.CarolIno.8,700505Iasi,Romania
fbaman,gabrielg@iit.tuiasi.ro
摘要:将移动环境与移动膜关联起来,作为联系P系统与各种过程代数学的更为一般的方法的一部分.
23.8.其他议题
GheorghePaun1,GrzegorzRozenberg2
1InstituteofMathematicsoftheRomanianAcademy,POBox1-764,014700Bucharest,Romania,and
ResearchGrouponNaturalComputing,DepartmentofComputerScienceandArtificialIntelligence
UniversityofSevilla,Avda.ReinaMercedess/n,41012Sevilla,Spain
george.paun@imar.ro,gpaun@us.es
2LeidenInstituteofAdvancedComputerScience(LIACS),LeidenUniversity
NielsBohrweg1,2333CALeiden,TheNetherlands,and
DepartmentofComputerScience,UniversityofColoradoatBoulder,Boulder,CO80309,U.S.A.
rozenber@liacs.nl
摘要:本节简要列出书中未能包括而我们认为应该提到的许多议题,以便呈现出更为完整的P系统研究现状.
·教师寄语态度决定一切