概率有限自动机的代数性质
|
摘要
研究了概率有限自动机的同态(弱同态)、有效划分等代数性质.首先,提出了完全的、不可约的概率有限自动机,概率有限自动机的并积等概念.然后,讨论了两个概率有限自动机的级联积、圈积、并积的有效划分与其因子的有效划分之间的关系,证明了在一定条件下两个概率有限自动机的级联积(并积)的商概率有限自动机与其因子的商概率有限自动机的级联积(并积)是相等的.最后,得到了概率有限自动机的极大有效划分的一个刻画.
In this paper,algebraic properties such as homomorphism(weak homomorphism),effectively partition of probabilistic finite automata are investigated.Firstly,the concepts of complete and irreducible probabilistic finite automata,join of probabilistic finite automata and so on are put forward.Then,the relationship between the effectively partitions of cascade product,wreath product,join of probabilistic finite automata and their factors are given,quotient probabilistic finite automata of cascade product(join) of probabilistic finite automata is equal to cascade product(join) of their factor' s quotient probabilistic finite automata under certain conditions is proved.Finally,a characterization on maximum effectively partition of probabilistic finite automata is obtained.
In this paper,algebraic properties such as homomorphism(weak homomorphism),effectively partition of probabilistic finite automata are investigated.Firstly,the concepts of complete and irreducible probabilistic finite automata,join of probabilistic finite automata and so on are put forward.Then,the relationship between the effectively partitions of cascade product,wreath product,join of probabilistic finite automata and their factors are given,quotient probabilistic finite automata of cascade product(join) of probabilistic finite automata is equal to cascade product(join) of their factor' s quotient probabilistic finite automata under certain conditions is proved.Finally,a characterization on maximum effectively partition of probabilistic finite automata is obtained.
引文
[1]Holcombe W M L.Algebraic automata theory[M].Cambridge:Cambridge University Press,1982.
[2]Malik D S,Mordeson J N,Sen M K.Products of fuzzy finite state machines[J].Fuzzy Sets and Systems,1997,92:95-102.
[3]Kumbhojkar H V,Chaudhari S R.On covering of products of fuzzy finite state machines[J].Fuzzy Sets and Systems,2002,125:215-222.
[4]Maler O.A decomposition theorem for probabilistic transition systems[J].Theoretical Computer Science,1995,145:391-396.
[5]Hwey W S,Smolka S A,Stark E W.Composition and behaviors of probabilistic I/O automata[J].Theoretical Computer Science,1997,176:1-38.
[6]Chattopadhyay I,Ray A.Structural transformations of probabilistic finite state machines[J].International Journal of Control,2008,81(5):820-835.
[7]Pantelic V,Postma S M,Lawford M.Probabilistic supervisory control of probabilistic discrete event systems[J].IEEE Trans on Automatic Control,2009,54(8):2013-2018.
[8]Ravikumar B.On some variations of two-way probabilistic finite automata models[J].Theoretical Computer Science,2007,376:127-136.
[9]吴宗显.概率有限自动机的代数性质[D].桂林:广西师范大学,2008.
[10]吴宗显,邓培民,易忠.概率有限自动机的商和同态[J].工程数学学报,2009,26(5):936-940.
[2]Malik D S,Mordeson J N,Sen M K.Products of fuzzy finite state machines[J].Fuzzy Sets and Systems,1997,92:95-102.
[3]Kumbhojkar H V,Chaudhari S R.On covering of products of fuzzy finite state machines[J].Fuzzy Sets and Systems,2002,125:215-222.
[4]Maler O.A decomposition theorem for probabilistic transition systems[J].Theoretical Computer Science,1995,145:391-396.
[5]Hwey W S,Smolka S A,Stark E W.Composition and behaviors of probabilistic I/O automata[J].Theoretical Computer Science,1997,176:1-38.
[6]Chattopadhyay I,Ray A.Structural transformations of probabilistic finite state machines[J].International Journal of Control,2008,81(5):820-835.
[7]Pantelic V,Postma S M,Lawford M.Probabilistic supervisory control of probabilistic discrete event systems[J].IEEE Trans on Automatic Control,2009,54(8):2013-2018.
[8]Ravikumar B.On some variations of two-way probabilistic finite automata models[J].Theoretical Computer Science,2007,376:127-136.
[9]吴宗显.概率有限自动机的代数性质[D].桂林:广西师范大学,2008.
[10]吴宗显,邓培民,易忠.概率有限自动机的商和同态[J].工程数学学报,2009,26(5):936-940.