计算机研究与发展
計算機研究與髮展
계산궤연구여발전
JOURNAL OF COMPUTER RESEARCH AND DEVELOPMENT
2013年
12期
2691-2698
,共8页
谢正卫%翟莹%邓培民%易忠
謝正衛%翟瑩%鄧培民%易忠
사정위%적형%산배민%역충
概率有限状态自动机%概率转移矩阵%同余%同态%同构%交换
概率有限狀態自動機%概率轉移矩陣%同餘%同態%同構%交換
개솔유한상태자동궤%개솔전이구진%동여%동태%동구%교환
probabilistic finite state automata%probabilistic transition matrix%congruence%homomorphism%isomorphism%commutativity
利用矩阵、同态、同构、同余等代数工具研究概率有限状态自动机的代数性质.首先定义了输入集上两个字符串同余的概念,并利用概率转移矩阵给出2个字符串同余的一些等价刻画.进而提出概率有限状态自动机同态和同构的概念,并给出了概率有限状态自动机同态定理.证明了2个概率有限状态自动机同构的充要条件是它们的概率转移矩阵可以通过第1种行列初等变换相互转化;同时提出了2个概率有限状态自动机积与和的概念,并得到了积自动机、和自动机的同态关系.最后将模糊自动机中交换的概念引入到概率有限状态自动机中,并利用概率转移矩阵给出了此类自动机交换的一些等价刻画以及和自动机、积自动机交换的充要条件.
利用矩陣、同態、同構、同餘等代數工具研究概率有限狀態自動機的代數性質.首先定義瞭輸入集上兩箇字符串同餘的概唸,併利用概率轉移矩陣給齣2箇字符串同餘的一些等價刻畫.進而提齣概率有限狀態自動機同態和同構的概唸,併給齣瞭概率有限狀態自動機同態定理.證明瞭2箇概率有限狀態自動機同構的充要條件是它們的概率轉移矩陣可以通過第1種行列初等變換相互轉化;同時提齣瞭2箇概率有限狀態自動機積與和的概唸,併得到瞭積自動機、和自動機的同態關繫.最後將模糊自動機中交換的概唸引入到概率有限狀態自動機中,併利用概率轉移矩陣給齣瞭此類自動機交換的一些等價刻畫以及和自動機、積自動機交換的充要條件.
이용구진、동태、동구、동여등대수공구연구개솔유한상태자동궤적대수성질.수선정의료수입집상량개자부천동여적개념,병이용개솔전이구진급출2개자부천동여적일사등개각화.진이제출개솔유한상태자동궤동태화동구적개념,병급출료개솔유한상태자동궤동태정리.증명료2개개솔유한상태자동궤동구적충요조건시타문적개솔전이구진가이통과제1충행렬초등변환상호전화;동시제출료2개개솔유한상태자동궤적여화적개념,병득도료적자동궤、화자동궤적동태관계.최후장모호자동궤중교환적개념인입도개솔유한상태자동궤중,병이용개솔전이구진급출료차류자동궤교환적일사등개각화이급화자동궤、적자동궤교환적충요조건.
