膜計算是自然計算的一個分支,膜計算中所研究的模型均稱為膜系統(tǒng),而細(xì)胞間通訊是膜系統(tǒng)的一個重要特征。帶膜分裂的通訊膜系統(tǒng)是一種分布式并行計算模型,可以在多項式時間內(nèi)解決計算困難問題。文中將促進(jìn)劑引入帶膜分裂的類細(xì)胞型通訊膜系統(tǒng),提出了膜系統(tǒng)的一種變型——帶膜分裂和促進(jìn)劑的通訊膜系統(tǒng),其中,一個促進(jìn)劑可以同時控制多條規(guī)則,而促進(jìn)劑本身不參與該條規(guī)則的進(jìn)化。文中研究了帶膜分裂和促進(jìn)劑的通訊膜系統(tǒng)的計算效率,證明該類膜系統(tǒng)在使用同向規(guī)則長度為2,每條規(guī)則中促進(jìn)劑的個數(shù)最多為1時,可以在多項式時間內(nèi)求解PSPACE完全問題（QSAT問題）的統(tǒng)一解。 

【文章來源】：計算機科學(xué). 2020,47(05)北大核心CSCD

【文章頁數(shù)】：5 頁

【部分圖文】：

產(chǎn)生階段完成時的膜結(jié)構(gòu)(圓點邊上的數(shù)字代表膜的標(biāo)號)


本文編號：3351052