您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (1): 56-61.doi: 10.6040/j.issn.1671-9352.0.2022.596

•   • 上一篇    下一篇

非确定型模糊有限自动机的一种新的极小确定化方法

李平(),杨巨芳,杨艳萍*()   

  1. 陕西师范大学数学与统计学院, 陕西 西安 710119
  • 收稿日期:2022-11-04 出版日期:2024-01-20 发布日期:2024-01-19
  • 通讯作者: 杨艳萍 E-mail:liping@snnu.edu.cn;578818312@qq.com
  • 作者简介:李平(1979—), 女, 副教授, 硕士生导师, 博士, 研究方向为模糊数学、模糊自动机理论与计算智能. E-mail: liping@snnu.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(61673250);陕西省自然科学基金资助项目(2020JM-247);中央高校基础研究基金项目(Gk201803008)

A new minimal determinization method of nondeterministic fuzzy finite automata

Ping LI(),Jufang YANG,Yanping YANG*()   

  1. College of Mathematics and Statistics, Shaanxi Normal University, Xi'an 710119, Shaanxi, China
  • Received:2022-11-04 Online:2024-01-20 Published:2024-01-19
  • Contact: Yanping YANG E-mail:liping@snnu.edu.cn;578818312@qq.com

RichHTML

1

PDF (PC)

312

摘要：

非确定型模糊有限自动机的极小确定化是自动机理论中的一个重要问题。在格序幺半群下, 本文给出一种非确定型模糊有限自动机的新的极小确定化方法, 称为内部构造法。为此, 首先给出了模糊状态的内部的定义及其相关性质, 进一步证明任给一个非确定型模糊有限自动机, 利用模糊状态的内部的性质得到一个极小的确定型模糊有限自动机与之等价, 最后通过例子验证该方法的正确性。

关键词: 格序幺半群, 非确定型模糊有限自动机, 确定型模糊有限自动机, 极小确定化, 内部构造

Abstract:

The minimal determinization of nondeterministic fuzzy finite automata (NFFA) is an important problem in automata theory. A new minimal determinization method for nondeterministic fuzzy finite automata with membership values in lattice-ordered monoids called interior construction is presented. For this reason, the definition of the interior of a fuzzy state and its related properties are given firstly. It is further proved that for any nondeterministic fuzzy finite automata, a minimal deterministic fuzzy finite automata is obtained by using the internal properties of fuzzy states, which is equivalent to it, finally, the correctness of this method is verified by an example.

Key words: lattice-ordered monoids, nondeterministic fuzzy finite automata, deterministic fuzzy finite automata, minimal determinization, interior construction

中图分类号: 

  • TP301

图1

NFFA $\mathscr{N}$的状态转移图"

图2

极小DFFA $\mathscr{D}$的状态转移图"

1 WEE W G. On generalizations of adaptive algorithms and application of the fuzzy sets concept to pattern classification[D]. Lafayette: Purdue University, 1967.
2 WEE W G , FU K S . A formulation of fuzzy automata and its application as a model of learning systems[J]. IEEE Transactions on Systems Science and Cybernetics, 1969, 5 (3): 215- 223.
doi: 10.1109/TSSC.1969.300263
3 SANTOS E S . Maximin automata[J]. Information and Control, 1968, 13 (4): 363- 377.
doi: 10.1016/S0019-9958(68)90864-4
4 SANTOS E S . On reductions of maximin machines[J]. Journal of Mathematical Analysis and Applications, 1972, 40 (1): 60- 78.
doi: 10.1016/0022-247X(72)90031-5
5 SANTOS E S . Fuzzy automata and languages[J]. Information Sciences, 1976, 10 (3): 193- 197.
doi: 10.1016/0020-0255(76)90040-2
6 LEE E T, ZADEH L A. Note on fuzzy languages[M]//Fuzzy Sets, Fuzzy Logic, and Fuzzy Systems: Selected Papers by Lotfi A Zadeh. Singapore: World Scientific, 1996: 69-82.
7 MORDESON J N , MALIK , D S . Fuzzy automata and languages: Theory and applications[M]. New York: Chapman and Hall/CRC, 2002.
8 PWDRYCZ W , GACEK A . Learning of fuzzy automata[J]. International Journal of Computational Intelligence and Applications, 2001, 1 (1): 19- 33.
doi: 10.1142/S1469026801000068
9 LIN F , YING H . Modeling and control of fuzzy discrete event systems[J]. IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics, 2002, 32 (4): 408- 460.
10 YING M . A formal model of computing with words[J]. IEEE Transactions on Fuzzy Systems, 2002, 10 (5): 640- 652.
doi: 10.1109/TFUZZ.2002.803497
11 李永明, 李平. 模糊计算理论[M]. 北京: 科学出版社, 2016: 151- 157.
LI Yongming , LI Ping . Fuzzy calculation theory[M]. Beijing: Science Press, 2016: 151- 157.
12 蒋宗礼, 姜守旭. 形式语言与自动机理论[M]. 3版 北京: 清华大学出版社, 2013: 83- 86.
JIANG Zongli , JIANG Shouxu . Formal language and automata theory[M]. 3rd ed Beijing: Tsinghua University Press, 2013: 83- 86.
13 MOČKOŘ J . Fuzzy and non-deterministic automata[J]. Soft Computing, 1999, 3 (4): 221- 226.
doi: 10.1007/s005000050091
14 BĚLOHLÁVEK R . Determinism and fuzzy automata[J]. Information Sciences, 2002, 143 (1/2/3/4): 205- 209.
15 QIU Daowen . Automata theory based on complete residuated latticed-valued logic[J]. Science in China Series: Information Sciences, 2001, 44 (6): 419- 429.
doi: 10.1007/BF02713945
16 XING Hongyan , QIU Daowen , LIU Fuchun , et al. Equivalence in automata theory based on complete residuated lattice-valued logic[J]. Fuzzy Sets and Systems, 2007, 158, 1407- 1422.
doi: 10.1016/j.fss.2007.01.008
17 LI Yongming , PEDRYCZ W . Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids[J]. Fuzzy Sets and Systems, 2005, 156 (1): 68- 92.
doi: 10.1016/j.fss.2005.04.004
18 LI Y M , PEDRYCZ 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.
doi: 10.1016/j.fss.2007.03.003
19 IGNJATOVIĆ J , ĆIRIĆ M , BOGDANOVIĆ S . Determinization of fuzzy automata with membership values in complete residuated lattices[J]. Information Sciences, 2008, 178 (1): 164- 180.
doi: 10.1016/j.ins.2007.08.003
20 JANČIĆ Z , IGNJATOVIĆ J , ĆIRIĆ M . An improved algorithm for determinization of weighted and fuzzy automata[J]. Information Sciences, 2011, 181 (7): 1358- 1368.
doi: 10.1016/j.ins.2010.12.008
21 JANČIĆ Z , ĆIRIĆ M . Brzozowski type determinization for fuzzy automata[J]. Fuzzy Sets and Systems, 2014, 249, 73- 82.
doi: 10.1016/j.fss.2014.02.021
22 MICIĆ I , JANČIĆ Z , IGNJATOVIĆ J , ĆIRIĆ M . Determinization of fuzzy automata by means of the degrees of language inclusion[J]. IEEE Transactions on Fuzzy Systems, 2015, 23 (6): 2144- 2153.
doi: 10.1109/TFUZZ.2015.2404348
[1] 罗兴隆,贺兴时,周洁,杨新社. 基于非洲秃鹫优化算法改进的密度峰值聚类[J]. 《山东大学学报(理学版)》, 2024, 59(1): 46-55,71.
[2] 刘海燕,拓守恒. 求解全局优化问题的一个新的填充函数算法[J]. 《山东大学学报(理学版)》, 2023, 58(7): 80-87.
[3] 王海辉,赵路瑶,李平. 非确定模糊有穷自动机的ε-语言逼近[J]. 《山东大学学报(理学版)》, 2021, 56(3): 37-43.
[4] 彭家寅. 以十量子纠缠态为信道的循环受控量子隐形传态[J]. 《山东大学学报(理学版)》, 2019, 54(9): 98-104.
[5] 彭家寅. 以真五粒子非最大纠缠态为信道的双向受控隐形传态[J]. 《山东大学学报(理学版)》, 2018, 53(12): 105-113.
[6] 刘利钊,于佳平,刘健,李俊祎,韩哨兵,许华荣,林怀钏,朱顺痣. 基于量子辐射场的大数据安全存储寻址算法[J]. 山东大学学报（理学版）, 2018, 53(7): 65-74.
[7] 宋省身,杨岳湘,江宇. 基于单指令级并行的快速求交算法[J]. 山东大学学报（理学版）, 2018, 53(3): 54-62.
[8] 朱丹,谢晓尧,徐洋,夏梦婷. 基于云模型与贝叶斯反馈的网络安全等级评估方法[J]. 山东大学学报（理学版）, 2018, 53(1): 53-62.
[9] 齐平, 王福成, 王必晴. 一种基于图模型的可信云资源调度算法[J]. 山东大学学报（理学版）, 2018, 53(1): 63-74.
[10] 史佩昀,高兴宝. 基于个体强度的自适应差分多目标免疫算法[J]. 山东大学学报（理学版）, 2017, 52(11): 1-10.
[11] 王峰,曼媛,王幸乐. 基于人工免疫的N最短路径检索算法[J]. 山东大学学报（理学版）, 2017, 52(9): 35-40.
[12] 王霞,张茜,李俊余,刘庆凤. 基于粗糙集的三元概念分析[J]. 山东大学学报（理学版）, 2017, 52(7): 37-43.
[13] 马兰,李伟岸,尹天懿. 基于变邻域搜索改进的冲突解脱粒子群算法[J]. 山东大学学报（理学版）, 2017, 52(1): 23-28.
[14] 杜红乐,张燕,张林. 不均衡数据集下的入侵检测[J]. 山东大学学报（理学版）, 2016, 51(11): 50-57.
[15] 谢建民,姚兵,赵廷刚. 广义太阳图Sm,n奇优雅标号算法及实现[J]. 山东大学学报（理学版）, 2016, 51(4): 79-85.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 黄贤立，罗冬梅. 倾向性文本迁移学习中的特征重要性研究[J]. J4, 2010, 45(7): 13 -17 .
[2] 高正晖,罗李平. 含分布时滞与阻尼项的三阶非线性微分方程的Philos型振动[J]. J4, 2013, 48(4): 85 -90 .
[3] 李志荣 . 广义m阶Bell数和广义m阶有序Bell数的计算公式[J]. J4, 2007, 42(2): 59 -63 .
[4] 许春华,高宝玉*,卢磊,徐世平,曹百川,岳钦艳,张建 . 城市纳污河道废水化学强化一级处理的研究[J]. J4, 2006, 41(2): 116 -120 .
[5] 陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26 -30 .
[6] 梁霄, 王林山 . 一类S分布时滞递归神经网络的全局吸引子[J]. J4, 2009, 44(4): 57 -60 .
[7] 董新梅 . 关于Suryanarayana的若干问题[J]. J4, 2007, 42(2): 83 -86 .
[8] 宋玉丹,王士同*. 基于特征缺省的最小类内方差支持向量机[J]. J4, 2010, 45(7): 102 -107 .
[9] 史艳华1,石东洋2*. 伪双曲方程类Wilson非协调元逼近[J]. J4, 2013, 48(4): 77 -84 .
[10] 刘汝军,曹玉霞,周 平 . 利用小反馈实现离散非线性混沌系统的反控制[J]. J4, 2007, 42(7): 30 -32 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发