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   

  1. 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

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

李 斌,舒 兰   

  1. 电子科技大学 应用数学学院,成都 610054
  • 通讯作者: 李 斌

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/Rk.At the base of effectual final states,the equivalence relations RkSk and the quotient set Q/Sk are introduced,and Rk=Rk-1Sk is proved.The elements of Q/Rk are all nonempty intersections with each equivalence class belonging to Q/Rk-1 and each one belonging to Q/Rk.Hk is introduced,and it can solve Q/Rk,and therefore Q/Rk 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,Σ,δ,q0的实质是求取Q/Rk。由此以可到达状态为基础引入了等价关系RkSk与商集Q/Sk,证明了Rk=Rk-1Sk,由此得到Q/Rk的等价类为Q/Rk-1中等价类与Q/Sk中等价类的非空交集全体。引入了Hk,并证明了可由Hk求取Q/Sk,从而得到仅利用集合运算便可求取Q/Rk的算法,最终给出了DLFA最小化算法的一个容易实现的构造型描述和相应示例。

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

CLC Number: