李立，江克勤

(1. 安慶廣播電視大學, 安徽 安慶 246003；2. 安慶師范大學計算機與信息學院，安徽 安慶 246133)

使用最小串行策略的均質(zhì)脈沖神經(jīng)膜系統(tǒng)的計算通用性

李立1，江克勤2

(1. 安慶廣播電視大學, 安徽 安慶 246003；2. 安慶師范大學計算機與信息學院，安徽 安慶 246133)

脈沖神經(jīng)膜系統(tǒng)是根據(jù)神經(jīng)網(wǎng)絡中神經(jīng)元相互之間依靠突觸來處理脈沖的生物現(xiàn)象而提出的，具有良好的計算性能及潛在的應用價值。使用最小串行策略的脈沖神經(jīng)膜系統(tǒng)是一類特殊的脈沖神經(jīng)膜計算模型，為了驗證其在均質(zhì)情況下的通用性，引入了帶權值的突觸，構建了均質(zhì)的基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)。使用自動機理論和形式語言，通過模擬注冊機證明了作為數(shù)的產(chǎn)生裝置和接受裝置，使用最小串行策略的均質(zhì)脈沖神經(jīng)膜系統(tǒng)都是通用的。

膜計算；脈沖神經(jīng)膜系統(tǒng)；串行性；均質(zhì)性；注冊機

膜計算模型是由歐洲科學院院士、羅馬尼亞科學院院士Pǎun于1998年在芬蘭圖爾庫計算機中心的研究報告中首次提出，論文于2000年發(fā)表[1]，由于膜計算具有良好的計算性能和潛在的應用價值，該方向已成為計算機科學快速發(fā)展的新興領域之一。2006年Ionescu等[2]提出的脈沖神經(jīng)膜系統(tǒng)是一種特殊的類神經(jīng)膜計算模型。脈沖神經(jīng)膜系統(tǒng)中基本的計算單元是神經(jīng)元，神經(jīng)元之間通過突觸傳遞信號，其中每個神經(jīng)元中含有若干個激發(fā)規(guī)則和遺忘規(guī)則。

脈沖神經(jīng)膜系統(tǒng)提出后，受到國內(nèi)外學者的廣泛關注，基于各種不同的生物動機，提出了一些特殊的脈沖神經(jīng)膜系統(tǒng)[3-7]，Ibarra等[8]在2009年提出的基于脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)就是其中的一種?；谧钚?或最大)脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)的串行性是由最小(或最大)脈沖數(shù)目引起的，同一時刻只有一個擁有最小(或最大)脈沖數(shù)目的活躍神經(jīng)元(即滿足激發(fā)規(guī)則的神經(jīng)元)可以被激發(fā)。Pǎun等[9]研究了基于最大脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)的小通用性。江克勤等研究了基于最小脈沖數(shù)目的小通用串行脈沖神經(jīng)膜系統(tǒng)[10-11]。本文研究的是均質(zhì)情況下基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)的通用性。在系統(tǒng)中引入均質(zhì)性和帶權值的突觸，構造了加法模塊、減法模塊、輸入模塊和輸出模塊，通過模擬注冊機來證明使用最小串行策略的均質(zhì)脈沖神經(jīng)膜系統(tǒng)在產(chǎn)生模式和接受模式下都是通用的。

1 相關定義及概念

1.1 基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)

一個度為m(m≥1)的脈沖神經(jīng)膜系統(tǒng)形式化定義[2]如下：

∏=(O,σ1,σ2,…,σm,syn,in,out)

其中：

(i)O={a}表示脈沖的集合；

(ii)σ1,σ2,…,σm代表m個神經(jīng)元，每個神經(jīng)元的表示形式為σi=(ni,Ri)(1≤i≤m)，其中ni≥0表示神經(jīng)元σi中包含的初始脈沖數(shù)；Ri是由下列兩種形式的規(guī)則構成的有限集合：

①E/ac→a;d(c≥1,d≥0),E為a的正則表達式，d稱為時延，即神經(jīng)元從被激發(fā)到發(fā)送脈沖所間隔的時間。

②as→λ(s≥1)，對Ri中的任意規(guī)則E/ac→a;d，都滿足as?L(E)；

①中表示的是激發(fā)規(guī)則，如果神經(jīng)元σi包含k個脈沖，滿足ak∈L(E)(k≥c),則規(guī)則E/ac→a;d可以被激發(fā)，神經(jīng)元σi將消耗c個脈沖，并在d個單位時間后向與它有突觸連接的每個神經(jīng)元送去一個脈沖。當d=0時，脈沖被立即送出；當d≥1時，若在第t步利用規(guī)則激發(fā)，則在第t、t+1、…、t+d-1步神經(jīng)元σi都是封閉的，不能接收和發(fā)送任何脈沖，到第t+d步，脈沖被送出，神經(jīng)元恢復到開放狀態(tài)。②中的規(guī)則稱為遺忘規(guī)則，如果神經(jīng)元σi包含s個脈沖，則Ri中的遺忘規(guī)則as→λ將被使用，消耗其中的s個脈沖，而且沒有新的脈沖產(chǎn)生。若規(guī)則E/ac→a;d滿足E=ac，則可以寫成ac→a;d若同時d=0，則可以直接簡寫為ac→a。

(iii) syn?{1,2,…,m}×{1,2,…,m}表示神經(jīng)元之間的突觸連接，對每個1≤i≤m，都有(i,i)?syn；

(iv) in,out∈{1,2,…,m}，其中in代表輸入神經(jīng)元，out代表輸出神經(jīng)元。

在標準脈沖神經(jīng)膜系統(tǒng)中，所有神經(jīng)元是并行工作的，在每一個時間單元，所有滿足條件的神經(jīng)元都必須使用對應規(guī)則激發(fā)?；谧钚∶}沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)的工作模式不同于標準的脈沖神經(jīng)膜系統(tǒng)，假設用一個全局時鐘標記整個系統(tǒng)的運行時間，在計算的每一步，當有多個活躍神經(jīng)元時，只有其中擁有最小脈沖數(shù)目的活躍神經(jīng)元可以使用對應規(guī)則激發(fā)。如果同一時刻擁有最小脈沖數(shù)目的活躍神經(jīng)元不止一個，則非確定性地選擇其中之一開始激發(fā)。

1.2 均質(zhì)性

均質(zhì)性是許多計算模型的重要特性之一，如在細胞自動機中，每個細胞取有限的離散狀態(tài)，遵循同樣的作用規(guī)則，大量細胞通過簡單的相互作用而構成動態(tài)系統(tǒng)的演化[12]。2009年曾湘祥等[13]將均質(zhì)性引入標準脈沖神經(jīng)膜系統(tǒng)，并證明了其通用性[13-14]。在均質(zhì)脈沖神經(jīng)膜系統(tǒng)中，所有神經(jīng)元有相同的規(guī)則集合，即對于系統(tǒng)Π中的任意神經(jīng)元σi=(ni,Ri)(1≤i≤m)，有R1=R2=…=Rm，這些神經(jīng)元以一種統(tǒng)一的方式工作。均質(zhì)脈沖神經(jīng)膜系統(tǒng)分為突觸上帶權值和不帶權值兩類，帶權的突觸(i,j,r)∈syn表示如果神經(jīng)元σi向神經(jīng)元σj發(fā)出1個脈沖，則神經(jīng)元σj會接收到r個脈沖。本文中，我們是在基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)中引入均質(zhì)性和帶權的突觸。在下文第2節(jié)的證明中用圖形表示帶權均質(zhì)脈沖神經(jīng)膜系統(tǒng)的各模塊，模塊中的神經(jīng)元用橢圓表示，用帶數(shù)字的箭頭表示突觸，若某個突觸的權值是1，則數(shù)字不用標出。

1.3 注冊機

注冊機M=(m,H,l0,lh,I)[15]，其中m是注冊器的數(shù)目，H是指令的標簽集合，I是指令集合，兩者一一對應，l0是起始指令，lh是終止指令。注冊機有三種形式的指令：

1) 加法指令li:(ADD(r),lj,lk)。先將存儲在注冊器r中的數(shù)值加1，再隨機選擇指令lj或指令lk來執(zhí)行。

2) 減法指令li:(SUB(r),lj,lk)。如果注冊器r中存儲的數(shù)值不為0，則先將該數(shù)減1，再執(zhí)行指令lj；如果注冊器r中存儲的數(shù)是0，則執(zhí)行指令lk。

3) 終止指令lh:HALT。注冊機M能在產(chǎn)生和接受兩種模式下運行。在產(chǎn)生模式下，計算初始狀態(tài)時，各注冊器都為空。M首先執(zhí)行的是l0，然后按照相應的指令進行操作，每一步執(zhí)行一條指令。當注冊機執(zhí)行到lh時，表示M的計算停止，則存放在注冊器1中的數(shù)值即為M所產(chǎn)生的數(shù)。在接受模式下，計算初始狀態(tài)時，先把一個自然數(shù)n存儲在某個注冊器中，其余的都是空注冊器。M首先執(zhí)行l(wèi)0，然后按照相應的指令進行操作，如果計算能夠終止于lh，則稱M可以接受數(shù)n。注冊機在產(chǎn)生模式和接受模式下都具有計算完備性。

本文將在基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)中引入均質(zhì)性和帶權值的突觸，通過模擬注冊機來證明這類所有神經(jīng)元中規(guī)則相同且含帶權突觸的系統(tǒng)在產(chǎn)生模式和接受模式下的通用性。

2 基于最小脈沖數(shù)目的均質(zhì)串行脈沖神經(jīng)膜系統(tǒng)的計算通用性

本節(jié)研究基于最小脈沖數(shù)目的均質(zhì)串行脈沖神經(jīng)膜系統(tǒng)的計算能力，證明該系統(tǒng)是通用的產(chǎn)生裝置和接受裝置。用NαHSNP(weightk)表示使用最小串行策略的均質(zhì)脈沖神經(jīng)膜系統(tǒng)產(chǎn)生或接受的數(shù)的集合簇，其中α∈{gen,acc}(gen表示系統(tǒng)工作在產(chǎn)生模式，acc表示系統(tǒng)工作在接受模式)，weightk表示系統(tǒng)中的突觸的權不超過k。當系統(tǒng)工作在產(chǎn)生模式時，系統(tǒng)可以產(chǎn)生形如0b104n-21的脈沖串；當系統(tǒng)工作在接受模式時，要計算(接受)的數(shù)n編碼為t2-t1-1的形式，其中t1,t2分別是輸入神經(jīng)元輸入前兩個脈沖的時刻。

2.1 產(chǎn)生模式下基于最小脈沖數(shù)目的均質(zhì)串行脈沖神經(jīng)膜系統(tǒng)

定理1NgenHSNP(weight17)=NRE。

證明由Turing-Church猜想可知：NgenHSNP(weight17)?NRE，因此只需要證明NRE?NgenHSNP(weight17)即可。

構建一個基于最小脈沖數(shù)目的均質(zhì)串行脈沖神經(jīng)膜系統(tǒng)Π來模擬運行M=(m,H,l0,lh,I)，假設在停機格局時，注冊機M中除了注冊器1之外，其余注冊器都為空，并且在計算過程中，注冊器1中的內(nèi)容只增不減。在系統(tǒng)Π中，所有神經(jīng)元具有相同的規(guī)則集，如圖1所示。系統(tǒng)Π由加法、減法和輸出三個模塊組成，分別如圖2、圖3和圖4所示。

圖1 系統(tǒng)Π中的神經(jīng)元Fig.1 The neurons of system Π

對M中的各注冊器r，系統(tǒng)Π都有一個神經(jīng)元σr與之對應，其中的脈沖數(shù)對應r中存儲的數(shù)。如果r中存儲的數(shù)為n≥0，則神經(jīng)元σr中包含5n+5個脈沖，即當神經(jīng)元σr中的脈沖數(shù)為5時，表示此時r為空。對M中的每個指令li，系統(tǒng)Π都有一個神經(jīng)元σli與之對應。一旦神經(jīng)元σli收到一個脈沖后，達到激發(fā)條件，就開始模擬M中的指令li:(op(r),lj,lk)：通過op(r)(對注冊器r進行加或減操作)，最后送出一個脈沖到神經(jīng)元σlj或σlk。當激發(fā)神經(jīng)元σlh后，系統(tǒng)Π就完成了模擬M的工作，此時兩次激發(fā)神經(jīng)元σout的時間間隔就對應為存儲在注冊器1中所產(chǎn)生的數(shù)。

圖2 系統(tǒng)Π的加法模塊Fig.2 The ADD module of system Π

因此，從神經(jīng)元σli的激發(fā)開始，系統(tǒng)向注冊器r的神經(jīng)元σr送入5個脈沖，然后非確定性地選擇激發(fā)神經(jīng)元σlj或σlk，系統(tǒng)Π正確地模擬了加法指令li:(ADD(r),lj,lk)。

圖3 系統(tǒng)Π的減法模塊Fig.3 The SUB module of system Π

因此，從神經(jīng)元σli的激發(fā)開始，如果注冊器r中存儲的數(shù)大于0，則減去1，系統(tǒng)Π結束于神經(jīng)元σlj；如果注冊器r中存儲的數(shù)等于0，系統(tǒng)結束于神經(jīng)元σlk。系統(tǒng)Π正確地模擬了減法指令li:(SUB(r),lj,lk)。

對某個注冊器r來說，可能會存在多個減法指令和加法指令作用其上，加法模塊和減法模塊之間可能的相互影響分析如下：

在如圖2所示的加法模塊中，神經(jīng)元σr每次都是收到5個脈沖，不會激發(fā)其中的任何規(guī)則，因此在加法模塊之間以及加法模塊和減法模塊之間都沒有相互影響。

2.1.3 輸出模塊 系統(tǒng)Π中使用最小串行策略的輸出模塊如上所示，當系統(tǒng)Π執(zhí)行到了終止指令lh，此時神經(jīng)元σ1中的脈沖數(shù)為5n+5(即注冊器1中存儲的數(shù)為n)。當神經(jīng)元σlh收到一個脈沖后，開始激發(fā)，向神經(jīng)元σout和σ1各發(fā)送一個脈沖。下一步，由于突觸(lh,1,8)的權為8，神經(jīng)元σout和σ1分別擁有1個和5n+13個脈沖，都可以激發(fā)，根據(jù)最小串行的使用策略，神經(jīng)元σout優(yōu)先激發(fā)，使用規(guī)則a→a，向環(huán)境送出第一個脈沖，假設此時是第t步。第t+1步神經(jīng)元σ1開始激發(fā)，使用規(guī)則a8(a5)+/a5→a，向神經(jīng)元σout和σd1各發(fā)送一個脈沖。由于突觸(1,out,7)和突觸(1,d1,17)的權分別為7和17，第t+2步神經(jīng)元σout和σ1分別擁有7個和17個脈沖，神經(jīng)元σ1擁有5n+8個脈沖，神經(jīng)元σ1和σd1都可以激發(fā)。根據(jù)神經(jīng)元σ1中脈沖數(shù)的不同，分析如下：

圖4 系統(tǒng)Π的輸出模塊Fig.4 The OUTPUT module of system Π

(i) 若n=1，神經(jīng)元σ1中的脈沖數(shù)是13個，將優(yōu)先激發(fā)，使用規(guī)則a8(a5)+/a5→a，剩余8個脈沖，不再激發(fā)，同時向神經(jīng)元σout和σd1各發(fā)送一個脈沖。由于突觸(1,out,7)和突觸(1,d1,17)的權分別為7和17，第t+3步神經(jīng)元σout和σd1分別擁有14個和34個脈沖，神經(jīng)元σout是系統(tǒng)中當前唯一的活躍神經(jīng)元，使用規(guī)則a14→a，向環(huán)境送出第二個脈沖，計算停止，此時產(chǎn)生的脈沖串為0b1021。

(ii) 若n≥2，神經(jīng)元σd1優(yōu)先激發(fā)，使用規(guī)則a17→a，向神經(jīng)元σout和σd2各發(fā)送一個脈沖。由于突觸(d1,out,3)的權為3，第t+3步，神經(jīng)元σout和σd2各擁有10個和1個脈沖，神經(jīng)元σd2可以激發(fā)，使用規(guī)則a→a，向神經(jīng)元σout發(fā)送一個脈沖,由于突觸(d2,out,2)的權為2，第t+4步，神經(jīng)元σout擁有12個脈沖，使用遺忘規(guī)則a12→λ，移去收到的12個脈沖。第t+5步，神經(jīng)元σ1激發(fā)，接著神經(jīng)元σd1、神經(jīng)元σd2、神經(jīng)元σout和神經(jīng)元σ1依次激發(fā)，不斷重復，直到第t+4n-2步，神經(jīng)元σ1、σd1和σout中的脈沖數(shù)分別為13、17和7，神經(jīng)元σ1和σd1都可以激發(fā)，根據(jù)最小串行策略，神經(jīng)元σ1再次激發(fā)，使用規(guī)則a8(a5)+/a5→a，剩余8個脈沖，神經(jīng)元σ1不再激發(fā)，同時向神經(jīng)元σout和σd1各發(fā)送一個脈沖。由于突觸突觸(1,out,7)和突觸(1,d1,17)的權分別為7和17，第t+4n-1步，神經(jīng)元σout和σd1分別擁有14個和34個脈沖，此時神經(jīng)元σout是系統(tǒng)中當前唯一的活躍神經(jīng)元，使用規(guī)則a14→a，向環(huán)境送出第二個脈沖，計算停止，此時產(chǎn)生的脈沖串為0b104n-21。

綜合以上對加法、減法和輸出3個模塊的描述，我們得到在使用最小串行策略下，系統(tǒng)Π正確地模擬了注冊機M，并且系統(tǒng)各模塊中突觸的權最大為17，因此，NRE?NgenHSNP(weight17)成立，定理1得證。

2.2 接受模式下基于最小脈沖數(shù)目的均質(zhì)串行脈沖神經(jīng)膜系統(tǒng)

定理2NaccHSNP(weight5)=NRE。

證明由Turing-Church猜想可知：NaccHSNP(weight5)?NRE，因此只需要證明NRE?NaccHSNP(weight5)即可。在接受模式下，構造一個基于最小脈沖數(shù)目的帶權均質(zhì)串行脈沖神經(jīng)膜系統(tǒng)Π′來模擬注冊機M=(m,H,l0,lh,I)，系統(tǒng)Π′中各模塊所含神經(jīng)元的規(guī)則如圖1組成。注冊器1中存儲一個數(shù)，其余注冊器都是空的，如果計算最終停止，則該數(shù)就被接受。系統(tǒng)Π′由輸入模塊、加法模塊和減法模塊組成，其中加法模塊和減法模塊與定理1中的圖2和圖3相同，輸入模塊如圖5所示。系統(tǒng)Π′要計算(接受)的數(shù)n編碼為t2-t1-1的形式，其中t1,t2分別是輸入神經(jīng)元輸入前兩個脈沖的時刻。

圖5 系統(tǒng)Π′的輸入模塊Fig.5 The INPUT module of system Π′

系統(tǒng)Π′中使用最小串行策略的輸入模塊如圖5所示，初始時神經(jīng)元σd1，σd2，σd3和σ1分別含有7個、8個、8個和5個脈沖。假設第t步輸入神經(jīng)元σin從環(huán)境收到第一個脈沖，利用規(guī)則a→a開始激發(fā)，向神經(jīng)元σd1和σd3各發(fā)送一個脈沖。由于突觸(in,d3,5)的權為5，第t+1步神經(jīng)元σd1和σd3分別擁有8個和13個脈沖，只有神經(jīng)元可以σd3激發(fā)，利用規(guī)則a8(a5)+/a5→a，向神經(jīng)元σd2和σ1各發(fā)送1個脈沖，由于突觸(d3,d2,5)和(d3,1,5)的權都為5，此步神經(jīng)元σd2和σ1都收到5個脈沖。第t+2步神經(jīng)元σd2擁有13個脈沖，可以激發(fā)，利用規(guī)則a8(a5)+/a5→a，向神經(jīng)元σd3和σ1各發(fā)送1個脈沖，由于突觸(d2,d3,5)和(d2,1,5)的權都為5，此步神經(jīng)元σd3和σ1都收到5個脈沖。第t+3步神經(jīng)元σd3擁有13個脈沖，是系統(tǒng)中唯一的活躍神經(jīng)元，恢復到第t+1步時的狀態(tài)，之后，神經(jīng)元σd2和σd3將交替激發(fā)，神經(jīng)元σ1每步均收到5個脈沖。

若第t+n+1(n≥1)步，神經(jīng)元σin從環(huán)境收到第二個脈沖，此時神經(jīng)元σin、σd1和σ1的脈沖數(shù)分別為1、8和5n+5，神經(jīng)元σd2和σd3的脈沖數(shù)是13和8(當n為奇數(shù)時)或者8和13(當n為偶數(shù)時)，根據(jù)最小串行的使用策略，神經(jīng)元σin優(yōu)先激發(fā)，利用規(guī)則a→a開始激發(fā)，向神經(jīng)元σd1和σd3各發(fā)送一個脈沖。第t+n+2步神經(jīng)元σd1和σd3的脈沖數(shù)分別為9和13(或18)，神經(jīng)元σd1激發(fā)，利用規(guī)則a9/a2→a，向神經(jīng)元σl0、σd2和σd3各發(fā)送1個脈沖。第t+n+3步，由于突觸(d1,d2,2)和(d1,d3,2)的權都為2，此步神經(jīng)元σl0脈沖數(shù)為1，σd2和σd3分別擁有脈沖數(shù)為15和15，或者是10和20。神經(jīng)元σl0是系統(tǒng)中唯一的活躍神經(jīng)元，利用規(guī)則a→a開始激發(fā)，系統(tǒng)Π′開始模擬注冊機M中的起始指令σl0。系統(tǒng)從環(huán)境收到前兩個脈沖的時刻分別為第t步和第t+n+1步，表明系統(tǒng)要接收的數(shù)為(t+n+1)-t-1=n。 綜合以上對加法、減法和輸入三個模塊的描述，我們得到在使用最小串行策略下，系統(tǒng)Π′正確地模擬了注冊機M，并且系統(tǒng)各模塊中突觸的權最大為5，因此，NRE?NaccHSNP(weight5)成立，定理2得證。

3 結 論

本文在基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)中引入均質(zhì)性和帶權值的突觸，證明了這類所有神經(jīng)元中規(guī)則相同且含帶權突觸的系統(tǒng)在產(chǎn)生模式和接受模式下都是通用的。本文解決了文獻[16]提出的均質(zhì)脈沖神經(jīng)膜系統(tǒng)在最小串行策略下是否具有通用性的問題。

對于使用最小串行策略的脈沖神經(jīng)膜系統(tǒng)，還有許多問題值得做進一步的探究，比如：將該系統(tǒng)與數(shù)據(jù)挖掘中的聚類算法相結合[17-19]，構建新的模型；利用該系統(tǒng)來有效解決計算困難問題；設計應用型的均質(zhì)脈沖神經(jīng)膜系統(tǒng)等。這些都是基于最小脈沖數(shù)目的串行脈沖神經(jīng)膜系統(tǒng)以后的研究方向。

[2] IONESCU M, PUN G, YOKOMORI T. Spiking neural P systems [J]. Fundamenta Informaticae, 2006, 71(2/3): 279-308.

[3] 潘林強，張興義，曾湘祥，等. 脈沖神經(jīng)膜計算系統(tǒng)的研究進展及展望[J]. 計算機學報, 2008, 31(12): 2090-2096.

PAN L Q, ZHANG X Y, ZENG X X, et al. Research advances and prospect of spiking neural P systems [J]. Chinese Journal of Computers, 2008, 31(12): 2090-2096.

[4] IONESCU M, PUN G,YOKOMORI T. Spiking neural P systems with an exhaustive use of rules [J]. International Journal of Unconventional Computing, 2007, 3(2): 135-154.

[5] PAN L Q, HOOGEBOOM H J. Spiking neural P systems with astrocytes [J]. Neural Computation, 2012, 24(3): 805-825.

[6] SONG T, PAN L Q, PUN G. Asynchronous spiking neural P systems with local synchronization [J]. Information Sciences, 2013, 21(9): 197-207.

[7] SONG T, PAN L Q, PUN G. Spiking neural P systems with rules on synapses [J]. Theoretical Computer Science, 2014, 529(1): 82-95.

[8] IBARRA O H, PUN A, RODRíGUEZ-PATN A. Sequential SNP systems based on min/max spike number [J]. Theoretical Computer Science, 2009, 410(30): 2982-2991.

[10] JIANG K Q, SONG T, PAN L Q. Universality of sequential spiking neural P systems based on minimum spike number [J]. Theoretical Computer Science, 2013, 499(12): 88-97.

[11] JIANG K Q, HUANG Y F, XU J B, et al. Small universal sequential spiking neural P systems based on minimum spike number [J]. Romanian Journal of Information， 2014, 17(1): 5-18.

[12] WOLFRAM S. Cellular automata as models of complexity [J]. Nature, 1984, 311(4): 419-424.

[13] ZENG X X, ZHANG X Y, PAN L Q. Homogeneous spiking neural P systems [J]. Fundamenta Informaticae, 2009, 97(1): 275-294.

[14] 彭獻武，樊曉平，劉建勛，等. 通用的不帶延遲的同質(zhì)脈沖神經(jīng)膜系統(tǒng)[J]. 計算機工程與科學, 2013, 35(3): 1-7.

PENG X W, FANG X P, LIU J X, et al. Universal homogeneous spiking neural P systems without delays [J]. Computer Engineering & Science, 2013, 35(3): 1-7.

[15] KOREC I. Small universal register machines [J].Theoretical Computer Science, 1996, 168(2):267-301.

[16] JIANG K Q, SONG T, PAN L Q. Homogeneous spiking neural P systems working in sequential mode induced by maximum spike number [J]. International Journal of Computer Mathematics, 2013, 90(4): 831-844.

[17] 楊發(fā)權，李贊，羅中良. 基于聚類與神經(jīng)網(wǎng)絡的無線信號聯(lián)合調(diào)制識別新方法[J]. 中山大學學報(自然科學版), 2015, 54(2):24-29.

YANG F Q, LI Z, LUO Z L. A new specific combination method of wireless communication modulation recognition based on clustering and neural network [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(2):24-29.

[18] 黃敏，李爾達，袁媛，等. 基于路網(wǎng)拓撲的聚類分析算法研究與實現(xiàn)[J]. 中山大學學報(自然科學版), 2015, 54(6):99-103.

HUANG M, LI E D, YUAN Y, et al. Research and implementation of clustering analysis algorithm based on road network topology [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2015, 54(6):99-103.

[19] 朱俊勇，逯峰. 基于稀疏子空間聚類的跨域人臉遷移學習方法[J]. 中山大學學報(自然科學版), 2016, 55(5):1-7.

ZHU J Y, LU F. Cross-domain face transfer learning based on sparse subspace clustering [J]. Acta Scientiarum Naturalium Universitatis Sunyatseni, 2016, 55(5):1-7.

ComputationaluniversalityofhomogeneousspikingneuralPsystemsworkinginsequentialmodeinducedbyminimumspikenumber

LILi1,JIANGKeqin2

(1.Anqing Radio and Television University, Anqing 246003, China;2.School of Computer and Information, Anqing Normal University, Anqing 246133, China)

Spiking neural P system is proposed based on the biological phenomenon that the neurons in the neural network are processed by synapses. It has good performance and potential application value. Spiking neural P system working in sequential mode induced by minimum spike number is a special kind of spiking neural computational models. In order to verify the universality of the homogeneous system, weighted synapses are introduced, and the homogeneous spiking neural P systems working in sequential mode induced by minimum spike number are constructed. It is proved that such systems are universal as both generative and acceptive devices by using automata theory, formal language and register machines.

membrane computing; spiking neural P system; sequentiality; homogeneity;register machine

TP301

A

0529-6579(2017)05-0034-07

10.13471/j.cnki.acta.snus.2017.05.005

2016-12-16

國家自然科學基金(61033003)；安徽省自然科學基金(1408085MF131)；安徽高校自然科學研究重點項目(KJ2017A942)

李立(1980年生)，女；研究方向膜計算和數(shù)據(jù)挖掘；E-mail：lily@aqtvu.cn