加权有穷自动机的代数性质

J4 ›› 2014, Vol. 36 ›› Issue (11): 2186-2190.

加权有穷自动机的代数性质

张丽霞

(安庆师范学院数学与计算科学学院,安徽安庆 246013)

收稿日期:2014-07-10 修回日期:2014-09-16 出版日期:2014-11-25 发布日期:2014-11-25
基金资助:
安庆师范学院青年科研基金项目(KJ201214)；安徽省优秀青年人才基金项目(2011SQRL097)

Algebraic properties of weighted finite state automata

ZHANG Lixia

(School of Mathematics and Computation,Anqing Normal University,Anqing 246013,China)

Received:2014-07-10 Revised:2014-09-16 Online:2014-11-25 Published:2014-11-25

摘要/Abstract

摘要：

在加权有穷自动机理论基础上，利用强同态的概念，证明两个加权有穷自动机在计算能力上是等价的，并在加权有穷自动机的状态集上建立一种等价关系，得到加权有穷自动机的商自动机，证明加权有穷自动机与其商自动机在计算能力上也是等价的。并通过引入加权有穷自动机的可交换性、分离性、(强)连通性及层的概念，讨论在(强)同态的条件下，两个加权有限状态机之间的可交换性、分离性、(强)连通性及层的关系。关键词：

关键词: 形式幂级数, 加权有穷自动机, 同态, 强连通

Abstract:

On the basis of the theory of weighted finite automata,we prove the computing equivalence between two weighted finite automatas under the strong homomorphism of weighted finite automatas, and obtain the quotient weighted automata by establishing the equivalence relation on the states of weighted finite automata.Based on the equivalence relation,the equivalence between weighted finite automata and its quotient automata is also proved.Specifically,the concepts such as commutability,separateness,(strong) connectedness properties and layers of weighted finite automata are introduced,and their relations in two different weighted finite automata are discussed under the homomorphism or strong homomorphism.

Key words: formal power series;weighted finite automata;homomorphism;strong connectedness

张丽霞. 加权有穷自动机的代数性质[J]. J4, 2014, 36(11): 2186-2190.

ZHANG Lixia. Algebraic properties of weighted finite state automata [J]. J4, 2014, 36(11): 2186-2190.

参考文献［12］

［1］	Shannon C E, MeCary J. Automata studies［M］. Prineeton:Prineeton University Press, 1956.
［2］	Hopcroft J E, Ullman J D. Introduction to automata theory, languages and computation［M］. New York:AddisonWesley, 1979.
［3］	Zadeh L A. Outline of a new approach to the analysis of complex systems and decision processes［J］. IEEE Transactions on Systems, Man, and Cybernetics, 1973(1):2844.
［4］	Mordeson J N, Malik D S. Fuzzy and languages:Theory and applications［M］. Boca Paton:Chapman &Hall/CRC, 2002.
［5］	Malik D S, Mordeson J N, Sen M K. On subsystems of a fuzzy finite state machines［J］. Fuzzy Sets and Systems,1994,68(2):8392.
［6］	Schützenberger M P. On the definition of a family of automata［J］. Information and Control,1961(4):245270.
［7］	Salomaa A, Soittola M. Automata theoretic aspects formal power series［M］. Berlin:Springer, 1978.
［8］	Droste M,Kuich W,Vogler H.A Kleene theorem for weighted tree automata［J］. Theory of Computing Systems, 2005,38(1):138.
［9］	Droste M, Gastin P. Weighted automata and weighted logics［J］. Theoretical Computer Science,2007,380(12):6986.
［10］	Berstel J, Reutenauer C. Noncommutative rational series with applications, encyclopedia of mathematics and its applications［M］. Cambridge:Cambridge University Press, 2010.
［11］	Li Y M,Wang Q.The universal fuzzy automation［J］.Fuzzy Sets and Systems,2014,249:2748.
［12］	Li Y M. Analysis of fuzzy systems［M］.Beijing:Science Press,2005.(in Chinese)
［13］	Ong G H, Kai Y. A binary partitioning approach to image compression using weighted finite automata for large images［J］. Computers & Mathematics with Applications, 2006, 51(11):17051714.
［14］	Albert J, Kari J. Digital image compression［M］∥Handbook of Weighted Automata［M］. Berlin:Springer Verlag,2009(Chapter11).
［15］	Bouyer P. Weighted timed automata:Modelchecking and games［J］. Electronic Notes in Theoretical Computer Science, 2006, 158(5):317.
［16］	Kuroki N, Mordeson J N. Successor and source functions［J］. J Fuzzy Math, 1997(5):173182.
［17］	Srivastava, A K, Tiwari S P. A topology for fuzzy automata ［C］∥Proc of AFSS’02, 2002:485490.
［18］	Srivastava A K , Tiwari S P. On another decomposition of fuzzy automata ［J］. Journal of Uncertain Systems, 2011,5(1):3337.
［19］	Tiwari S P, Singh A K, Sharan S. Fuzzy automata based on latticeorder monoid and associated topology［J］. Journal of Uncertain Systems, 2012,6(1):5155.
［20］	Tiwari S P, Sharan S. Fuzzy automata based on latticeordered monoid with algebraic and topological aspects［J］. International Journal of Fuzzy and Information Engineering, 2012, 4(2):155164.
［21］	Tiwari S P,Yadav V K,Anupam K S.On algebraic study of fuzzy automata ［J］. International Journal of Machine Learning and Cybernetics,doi:10.1007/s1304201402335.
［22］	Zamir B. Introduction to the theory of automata［M］. Virginia:Reston Publishing Company, 1983.
	附中文参考文献:
［12］	李永明. 模糊系统分析［M］.北京:科学出版社,2005.

[1]	李文卿, 马锐, 张文涛. 基于共用密钥的高效多密钥同态加密方案研究[J]. 计算机工程与科学, 2023, 45(02): 252-260.
[2]	赵路瑶, 王海辉, 李平. 几类带空转移的n元伪加权自动机的关系[J]. 计算机工程与科学, 2022, 44(02): 364-371.
[3]	杨竞，范明钰，王光卫. 基于消息认证混合同态签名的无线网络抗污染攻击方案[J]. 计算机工程与科学, 2019, 41(03): 458-465.
[4]	杨燕,张宝山,周杰,陈高科. 结合暗通道先验的光补偿快速去雾算法[J]. 计算机工程与科学, 2018, 40(11): 2033-2039.
[5]	付伟1，李墨泚2，赵华容2，吴勇2. CRSHE：基于同态加密的新型密文检索方案[J]. 计算机工程与科学, 2018, 40(09): 1540-1545.
[6]	娄宇，朱更明. RLWE同态加密算法的多候选人电子投票协议[J]. 计算机工程与科学, 2018, 40(03): 472-480.
[7]	江小平，张巍，李成华，周航，孙婧. 面向云存储的基于全同态密码技术的文档相似度计算方法[J]. 计算机工程与科学, 2017, 39(10): 1807-1811.
[8]	谢鲲，施文. 一种隐私保护的可逆布鲁姆过滤器[J]. 计算机工程与科学, 2017, 39(06): 1104-1111.
[9]	王拥兵1,2,李永明1. 确定型模糊多重集有限自动机的极小化[J]. 计算机工程与科学, 2016, 38(12): 2574-2578.
[10]	齐永锋1，火元莲2. 一种基于同态滤波器与Radon变换的光照不变人脸识别方法[J]. J4, 2015, 37(12): 2393-2398.
[11]	张维1,2，曹发生2，余泉1,2，王驹3. 描述逻辑系统εLN中概念最小公共包含推理研究[J]. J4, 2012, 34(2): 139-145.
[12]	阮鸥1,2,周靖2,郑明辉3. 一种高效的同态时控承诺方案[J]. J4, 2012, 34(10): 28-31.
[13]	唐春明1,徐茂智1, 2,亓延峰1. Jacobi交上的配对计算[J]. J4, 2011, 33(10): 25-29.