概率有限自动机积的覆盖性
|
摘要
提出了概率有限自动机的覆盖的定义,然后利用代数的方法讨论了概率有限自动机的全直积(限制直积)、级联积、圈积、并积的覆盖关系,证明了2个概率有限自动机的级联积(限制直积)覆盖它们的圈积(全直积),概率有限自动机的圈积的全直积覆盖它们的全直积的圈积,给出了概率有限自动机的弱同态与覆盖的关系,研究了概率有限自动机的积的覆盖关系的传递性质.
The concept of covering of probabilistic finite automata was introduced,covering relationship on several kinds of products of probabilistic finite automata,such as full direct product(restricted direct product),cascade product,wreath product and join were discussed,it was proved that the cascade product(restricted direct product) of two probabilistic finite automata covered their wreath product(full direct product),full direct product of wreath product of probabilistic finite automata covered their wreath product of full direct product,the relations between weak homomorphism of probabilistic finite automata and covering of probabilistic finite automata were given,transitivity of covering of product of probabilistic finite automata were investigated.
The concept of covering of probabilistic finite automata was introduced,covering relationship on several kinds of products of probabilistic finite automata,such as full direct product(restricted direct product),cascade product,wreath product and join were discussed,it was proved that the cascade product(restricted direct product) of two probabilistic finite automata covered their wreath product(full direct product),full direct product of wreath product of probabilistic finite automata covered their wreath product of full direct product,the relations between weak homomorphism of probabilistic finite automata and covering of probabilistic finite automata were given,transitivity of covering of product of probabilistic finite automata were investigated.
引文
[1]Hierons R M,Merayo M G.Mutation testing from probabilistic and stochastic finite state Machines[J].The Journal of Systems and Software,2009,82:1804-1818.
[2]Palmer N,Goldberg P W.PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance[J].Theoretical Computer Science,2007,387:18-31.
[3]Pantelic V,Postma S M,Lawford M.Probabilistic supervisory control of probabilistic discrete event systems[J].IEEE Transactions on Automatic Control,2009,54(8):2013-2018.
[4]Jin X,Gupta S,Mukherjee K,Ray A.Wavelet—based feature extraction using probabilistic finite state aut-omata for pattern classification[J].Pattern Recognition,2011,44:1343-1356.
[5]Holcombe W M L.Algebraic automata theory[M].Cambridge:Cambridge University Press,1982.
[6]Malik D S,Mordeson J N,Sen M K.Products of fuzzy finite state machines[J].Fuzzy Sets and Systems,1997,92:95-102.
[7]Kumbhojkar H V,Chaudhari S R.On covering of products of fuzzy finite state machines[J].Fuzzy Sets and Systems,2002,125:215-222.
[8]Maler O.A decomposition theorem for probabilistic transition systems[J].Theoretical Computer Science,1995,145:391-396.
[9]吴宗显,邓培民,易忠.概率有限自动机的积和分解[J].计算机工程与应用,2009,45(15):47-50.
[10]谢正卫,翟莹,邓培民,等.概率有限状态自动机的代数性质[J].计算机研究与发展,2013,50(12):2691-2698.
[2]Palmer N,Goldberg P W.PAC-learnability of probabilistic deterministic finite state automata in terms of variation distance[J].Theoretical Computer Science,2007,387:18-31.
[3]Pantelic V,Postma S M,Lawford M.Probabilistic supervisory control of probabilistic discrete event systems[J].IEEE Transactions on Automatic Control,2009,54(8):2013-2018.
[4]Jin X,Gupta S,Mukherjee K,Ray A.Wavelet—based feature extraction using probabilistic finite state aut-omata for pattern classification[J].Pattern Recognition,2011,44:1343-1356.
[5]Holcombe W M L.Algebraic automata theory[M].Cambridge:Cambridge University Press,1982.
[6]Malik D S,Mordeson J N,Sen M K.Products of fuzzy finite state machines[J].Fuzzy Sets and Systems,1997,92:95-102.
[7]Kumbhojkar H V,Chaudhari S R.On covering of products of fuzzy finite state machines[J].Fuzzy Sets and Systems,2002,125:215-222.
[8]Maler O.A decomposition theorem for probabilistic transition systems[J].Theoretical Computer Science,1995,145:391-396.
[9]吴宗显,邓培民,易忠.概率有限自动机的积和分解[J].计算机工程与应用,2009,45(15):47-50.
[10]谢正卫,翟莹,邓培民,等.概率有限状态自动机的代数性质[J].计算机研究与发展,2013,50(12):2691-2698.