确定型模糊多重集有限自动机的极小化

计算机工程与科学

确定型模糊多重集有限自动机的极小化

王拥兵1,2,李永明1

(1.陕西师范大学计算机科学学院,陕西西安 710062;2.安庆师范大学数学与计算科学学院,安徽安庆 246013)

收稿日期:2016-07-05 修回日期:2016-09-10 出版日期:2016-12-25 发布日期:2016-12-25
基金资助:
国家自然科学基金（11271237,11301321）

Minimization of deterministic fuzzy multiset finite automata

WANG Yongbing1,2,LI Yongming1

(1.College of Mathematics and Information Science,Shaanxi Normal University,Xi’an 710062;

2.College of Mathematics and Computation,Anqing Normal University,Anqing 246013,China)

Received:2016-07-05 Revised:2016-09-10 Online:2016-12-25 Published:2016-12-25

摘要/Abstract

摘要：

主要研究确定型模糊多重集有限自动机的状态极小化问题。给出了模糊多重集有限自动机的同余和同态概念，并利用同余和同态关系研究了确定型模糊多重集有限自动机的极小化问题。进一步从确定型模糊多重集有限自动机自身出发，构造出极小模糊多重集有限自动机，并给出了极小化的算法。

关键词: 多重集, 确定型模糊多重集有限自动机, 同余, 同态, 极小化

Abstract:

We focus on the minimization of deterministic fuzzy multiset finite automata, and define the concepts of congruence and homomorphisms of deterministic fuzzy multiset finite automata. We study the minimization of deterministic fuzzy multiset finite automata based on congruence and homomorphism. We construct the corresponding minimization of deterministic fuzzy multiset finite automata according to its characteristics, and provide a minimization algorithm to achieve the minimal deterministic fuzzy multiset finite automata.

Key words: multiset, deterministic fuzzy multiset finite automata, congreence, homomorphisms, minimization

王拥兵1,2,李永明1. 确定型模糊多重集有限自动机的极小化[J]. 计算机工程与科学.

WANG Yongbing1,2,LI Yongming1. Minimization of deterministic fuzzy multiset finite automata[J]. Computer Engineering & Science.

参考文献［8］

［1］	Zadeh L A.Fuzzy sets［J］.Information and Control,1965,8:338353.
［2］	Wee W G.On generalizations of adaptive algorithm and application of the fuzzy sets concept to pattern classification［D］.Lafeyette:Purdue University,1967.
［3］	Wee W G,Fu K S.A formulation of fuzzy automata and its applications as a model of learning systems［J］.IEEE Transactions on Systems Science and Cybernetics,1969,5(3):215233.
［4］	Hopcroft J E,Ullman J D.Introduction to automata theory,languages and computation［M］.New York:AddisonWesley,1979.
［5］	Mordeson J N,Malik D S.Fuzzy automata and languages:Theory and applications［M］.Boca Raton,London:Chapman &Hall/CRC,2002.
［6］	Li Yongming. Analysis of fuzzy systems［M］.Beijing:Science Press,2005.(in Chinese)
［7］	Li Y M,Pedryczb W.Minimization of lattice finite automata and its application to the decomposition of lattice languages［J］.Fuzzy Sets and Systems,2007,158(13):14231436.
［8］	Tian Jian, Xu Hui. Congruence and minimization of deterministic weighted finite automata［J］.Pure and Applied Mathematics,2015,31(5):468473.(in Chinese)
［9］	Blanco A,Delgado M,Pegalajar M C.Fuzzy automation induction using neural network［J］.International Journal of Approximate Reasoning,2001,27(1):126.
［10］	Rigatos G G. Fault detection and isolation based on fuzzy automata［J］.Information Sciences,2009,179(12):18931902.
［11］	Ko B C,Ham S J,Nam J Y.Modeling and formalization of fuzzy finite automata for detection of irregular fire flames［J］.IEEE Transactions on Circuits and Systems for Video Technology,2011,21(12):19031912.
［12］	Singh D,Shuaibu M.Multiset path orderings and their application to termination of term rewriting systems［J］.Mathematical Theory and Modeling,2013,3(5):96111.
［13］	BlanchetSadri F,Morgan C.Multiset and set decipherable codes［J］.Computers and Mathematics with Applications,2001,41(10):12571262.
［14］	CsuhajVarjú E,MartínVide C,Mitrana V.Multiset automata［M］∥Calude C S,Paun G G,Rozenberg A，et al. Multiset processingmathematical computer science and molecular computing points of view,Berlin:Springer, 2001:123133.
［15］	Ciobanu G.Mealy multiset automata［J］.International Journal of Foundations of Computer Science,2006,17(1):111126.
［16］	Wang J,Yin M,Gu W.Fuzzy multiset finte automata and their languages［J］.Soft Computing,2013,17(3):381390.
［17］	Tiwari S P,Gautam V,Dubey M K.On fuzzy multiset automata［J］.Journal of Applied Mathematics and Computing,2016,5(12):643657.
［18］	Martinek P. Fuzzy multiset finite automata:Determinism,languages,and pumping lemma［C］∥Proc of the 12th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD),2015:6064.
	附中文参考文献：
［6］	李永明.模糊系统分析［M］.北京:科学出版社,2005.
［8］	田径,徐慧.确定权重有限自动机的同余及极小自动机［J］.纯粹数学与应用数学,2015,31(5):468473.

[1]	李文卿, 马锐, 张文涛. 基于共用密钥的高效多密钥同态加密方案研究[J]. 计算机工程与科学, 2023, 45(02): 252-260.
[2]	杨竞，范明钰，王光卫. 基于消息认证混合同态签名的无线网络抗污染攻击方案[J]. 计算机工程与科学, 2019, 41(03): 458-465.
[3]	杨燕,张宝山,周杰,陈高科. 结合暗通道先验的光补偿快速去雾算法[J]. 计算机工程与科学, 2018, 40(11): 2033-2039.
[4]	付伟1，李墨泚2，赵华容2，吴勇2. CRSHE：基于同态加密的新型密文检索方案[J]. 计算机工程与科学, 2018, 40(09): 1540-1545.
[5]	娄宇，朱更明. RLWE同态加密算法的多候选人电子投票协议[J]. 计算机工程与科学, 2018, 40(03): 472-480.
[6]	江小平，张巍，李成华，周航，孙婧. 面向云存储的基于全同态密码技术的文档相似度计算方法[J]. 计算机工程与科学, 2017, 39(10): 1807-1811.
[7]	谢鲲，施文. 一种隐私保护的可逆布鲁姆过滤器[J]. 计算机工程与科学, 2017, 39(06): 1104-1111.
[8]	齐永锋1，火元莲2. 一种基于同态滤波器与Radon变换的光照不变人脸识别方法[J]. J4, 2015, 37(12): 2393-2398.
[9]	张丽霞. 加权有穷自动机的代数性质[J]. J4, 2014, 36(11): 2186-2190.
[10]	张维1,2，曹发生2，余泉1,2，王驹3. 描述逻辑系统εLN中概念最小公共包含推理研究[J]. J4, 2012, 34(2): 139-145.
[11]	阮鸥1,2,周靖2,郑明辉3. 一种高效的同态时控承诺方案[J]. J4, 2012, 34(10): 28-31.
[12]	李孟婷,赵泽茂. 基于线性同余比较器和混沌系统的伪随机序列生成方法[J]. J4, 2011, 33(8): 63-69.
[13]	唐春明1,徐茂智1, 2,亓延峰1. Jacobi交上的配对计算[J]. J4, 2011, 33(10): 25-29.
[14]	李苏妮1，李天朝2，李永明1,3. 加权Moore机的同余与最小化[J]. J4, 2010, 32(9): 165-168.
[15]	徐子珊. 一个实用的图同构判定算法[J]. J4, 2008, 30(10): 24-26.