Minimization of deterministic lattice finite automata

doi:10.3778/j.issn.1002-8331.2010.32.014

Computer Engineering and Applications ›› 2010, Vol. 46 ›› Issue (32): 52-54.DOI: 10.3778/j.issn.1002-8331.2010.32.014

• 研究、探讨 • Previous Articles Next Articles

Minimization of deterministic lattice finite automata

LI Bin，SHU Lan

College of Applied Mathematics，University of Electronic Science and Technology of China，Chengdu 610054，China

Received:2009-04-14 Revised:2009-06-22 Online:2010-11-11 Published:2010-11-11
Contact: LI Bin

确定型格值有限自动机的最小化

李斌，舒兰

电子科技大学应用数学学院，成都 610054

通讯作者: 李斌

Abstract

Abstract: The notion of deterministic lattice finite automata is proposed，and the definitions of effectual final states and reachable states are shown.Indicating that the key problem of implementing the minimization algorithm of DLFA is how to solve quotient set Q/R_k.At the base of effectual final states，the equivalence relations R_k，S_k and the quotient set Q/S_k are introduced，and R_k=R_k_-1∩S_k is proved.The elements of Q/R_k are all nonempty intersections with each equivalence class belonging to Q/R_k-1 and each one belonging to Q/R_k.H_k is introduced，and it can solve Q/R_k，and therefore Q/R_k is solved using only set operations.A constructive minimization algorithm of DLFA easy to be implemented is presented based on the above discussion.

Key words: lattice-ordered monoid, deterministic lattice finite automata, equivalence relation, quotient set, minimization, minimization algorithm

摘要： 给出了确定型格值有限自动机的定义，并同时给出了有效终止状态和可达到状态的定义。指出了求取DLFA M=Q,Σ,δ,q₀,σ的实质是求取Q/R_k。由此以可到达状态为基础引入了等价关系R_k、S_k与商集Q/S_k，证明了R_k=R_k_-1∩S_k，由此得到Q/R_k的等价类为Q/R_k-1中等价类与Q/S_k中等价类的非空交集全体。引入了H_k，并证明了可由H_k求取Q/S_k，从而得到仅利用集合运算便可求取Q/R_k的算法，最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。

关键词: 格半群, 确定型有限状态自动机, 等价关系, 商集, 最小化, 最小化算法

CLC Number:

O235
TP23

LI Bin，SHU Lan. Minimization of deterministic lattice finite automata[J]. Computer Engineering and Applications, 2010, 46(32): 52-54.

李斌，舒兰. 确定型格值有限自动机的最小化[J]. 计算机工程与应用, 2010, 46(32): 52-54.

[1]	WANG Jie, JIN Zhengmeng, FENG Can. Adaptive Generalized Total Variation Algorithm for Poisson Noise Removal [J]. Computer Engineering and Applications, 2021, 57(20): 203-209.
[2]	MA Chengqi, LI Xuehua, ZHANG Lanjie, XIANG Wei. Anti-oclusion Monocular Depth Estimation Algorithm [J]. Computer Engineering and Applications, 2021, 57(2): 217-222.
[3]	ZHENG Xinglin, WANG Yue, LIU Wei. Partially Connected Hybrid Precoding Design for Millimeter Wave MIMO System [J]. Computer Engineering and Applications, 2020, 56(18): 97-103.
[4]	YAN Liping1, MA Jiajun1, CHEN Wenxing2. Sparse Structured Least Squares Twin Support Vector Regression Machine [J]. Computer Engineering and Applications, 2019, 55(3): 10-14.
[5]	NIE Dongdong, HE Yueyue. Fast face recognition based on dictionary expansion [J]. Computer Engineering and Applications, 2018, 54(8): 201-206.
[6]	YANG Hairong1, JIN Hui2. Improved IRLS algorithm for nonconvex compressive sensing [J]. Computer Engineering and Applications, 2018, 54(24): 46-51.
[7]	ZHAO Huanhuan1, JIAN Lirong1, LIU Yong2. Variable precision rough set model based on set pair homeopathic similar relationship [J]. Computer Engineering and Applications, 2017, 53(6): 51-56.
[8]	DONG Zemin1, SHI Qiang2. Feature selection using normalized fuzzy joint mutual information maximum [J]. Computer Engineering and Applications, 2017, 53(22): 105-110.
[9]	WU Yajuan, XU Liming. Total variation blind restoration using high-order P-Laplace [J]. Computer Engineering and Applications, 2017, 53(2): 220-224.
[10]	LUO Hao1，2, LIU Yu1，2, WU Sijin3. Comprehensive comparative study of protein-peptide docking algorithms performance [J]. Computer Engineering and Applications, 2017, 53(14): 111-116.
[11]	ZHANG Chen, LI Hongjun, LUO Liuhong, HE Yinghao. Congruent permutation and computation of canonical form on matrix of equivalence relation [J]. Computer Engineering and Applications, 2017, 53(13): 42-48.
[12]	WANG Zhendao, CHEN Yi. Binary Decision Diagram variable ordering based on catastrophe genetic algorithm [J]. Computer Engineering and Applications, 2015, 51(3): 55-60.
[13]	LIN Zhihong, LI Guang, LUO Shouhua. Ring artifact correction via total variation minimization [J]. Computer Engineering and Applications, 2015, 51(21): 195-198.
[14]	AN Qiusheng1, KONG Xiangyu2, SU Qin1. Mathematical foundation of rough relational database [J]. Computer Engineering and Applications, 2015, 51(14): 108-112.
[15]	SONG Jinping, ZHENG Changyan. Fast image inpainting of high-order model [J]. Computer Engineering and Applications, 2015, 51(11): 154-157.

Minimization of deterministic lattice finite automata

确定型格值有限自动机的最小化

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics