资源描述：
《R. Time-varying H Systems Revisited》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、JournalofUniversalComputerScience,vol.12,no.10(2006),1455-1463submitted:8/3/06,accepted:24/10/06,appeared:28/10/06©J.UCSTime-varyingHSystemsRevisitedRemcoLoosResearchGrouponMathematicalLinguisticsRoviraiVirgiliUniversityP¸caImperialT`arraco1,43005Tarragona,SpainE-mai
2、l:remcogerard.loos@urv.netAbstract:Wecastanewlookontime-varyingdistributedHsystems.Intheiroriginaldefinition,whereonlynewstringsarepassedtothenextcomponent,thislanguagedefinitioninitselfisalreadyenoughtoobtaincomputationalcompleteness.Here,weconsidertwotypesoftime-vary
3、ingHsystemswithweakerlanguagedefinitions,basedontheusualdefinitionofsplicingsystems:Thenextgenerationofstringsconsistsoftheunionofallexistingstringsandthenewlycreatedstrings.Weshowthatifallstrings,botholdandnew,arepassedtothenextcomponentthesesystemsareregularinpower.I
4、fhowever,thenewstringspasstothenextcomponentandtheexistingonesremainaccessibletothecurrentone,weprovethatsystemswith4componentsarealreadycomputationallycomplete.KeyWords:DNAcomputing,Molecularcomputing,SplicingsystemsCategory:F.1.1,F.4.21IntroductionTime-varyingdistr
5、ibutedHsystemswereintroducedin[9].Theyhaveadis-tributedarchitectureinwhichdifferentsetsofsplicingrulesareusedperiodically.In[9]itwasshownthattime-varyingdistributedHsystemsarecomputationallycomplete.Moreover,inaseriesofpapers,including[10],[7]and[5],thedegree(i.e.then
6、umberofdifferentsetsofsplicingrules)ofthetime-varyingHsystemsneededtoobtaincomputationalcompletenesshasbeendecreasedprogressively.Finally,in[4],itwasshownthattime-varyingdistributedHsystemsofdegree1cangenerateallrecursivelyenumerablelanguages.Suchsystemsarereallynolon
7、gerdistributednortime-varying,havingonlyasinglesetofsplicingrules.Thisresultcanbeexplainedbythewaythelanguageisdefinedintime-varyingHsystems:Fromonesplicingsteptothenext,onlythenewlycreatedstringsarekept.Theresultin[4]showsthatthiswayofdefiningthesplicinglanguagealonei
8、ssufficienttoobtaincomputationalcompleteness.Recently([2]and[3]),thisdefinitionhasalsobeenstudiedinthecontextofbasicfinitesplicingsyste
