JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (1): 56-61.doi: 10.6040/j.issn.1671-9352.0.2022.596

Previous Articles     Next Articles

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)

324

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

CLC Number: 

  • TP301

Fig.1

State transition diagram of NFFA $\mathscr{N}$"

Fig.2

State transition diagram of the minimal NFFA $\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] Hai-hui WANG,Lu-yao ZHAO,Ping LI. ε-language approximation of nondeterministic fuzzy finite automata [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(3): 37-43.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] HUANG Xian-li，LUO Dong-mei. Feature impprtance study on  transfer learning of  sentiment  text  classification[J]. J4, 2010, 45(7): 13 -17 .
[2] GAO Zheng-hui, LUO Li-ping. Philos-type oscillation criteria for third-order nonlinear functional differential equations with distributed delays and damped terms[J]. J4, 2013, 48(4): 85 -90 .
[3] LI Zhi-rong . Computational formulae of generalized m-th-order Bell numbers and generalized m-order orderd Bell numbers[J]. J4, 2007, 42(2): 59 -63 .
[4] XU Chun-hua,GAO Bao-yu,LU Lei,XU Shi-ping,CAO Bai-chuan,YUE Qin-yan and ZHANG Jian . Study of chemically enhanced primary treatment of wastewater received by urban rivers[J]. J4, 2006, 41(2): 116 -120 .
[5] CHEN Hong-yu1, ZHANG Li2. The linear 2-arboricity of planar graphs without 5-, 6-cycles with chord[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(06): 26 -30 .
[6] LIANG Xiao, WANG Linshan. Global attractor of a class of recurrent neural network with Stype distributed delays[J]. J4, 2009, 44(4): 57 -60 .
[7] DONG Xin-mei . On problems of Suryanarayana[J]. J4, 2007, 42(2): 83 -86 .
[8] SONG Yu-dan, WANG Shi-tong*. Minimum within-class variance SVM with absent features[J]. J4, 2010, 45(7): 102 -107 .
[9] SHI Yan-hua1, SHI Dong-yang2*. The quasi-Wilson nonconforming finite element approximation to  pseudo-hyperbolic equations[J]. J4, 2013, 48(4): 77 -84 .
[10] LIU Ru-jun,CAO Yu-xia,ZHOU Ping . Anti-control for discrete chaos systems by small feedback[J]. J4, 2007, 42(7): 30 -32 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd