Home > Papers

 
 
Finite Automata Theory with Membership Values in Lattices
Li Yongming * #
College of Computer Science, Shaanxi Normal University
*Correspondence author
#Submitted by
Subject:
Funding: 国家自然科学基金,教育部博士点基金(No.60873119,200807180005)
Opened online: 5 February 2010
Accepted by: none
Citation: Li Yongming.Finite Automata Theory with Membership Values in Lattices[OL]. [ 5 February 2010] http://en.paper.edu.cn/en_releasepaper/content/39974
 
 
In this paper, we study finite automata with membership values in a lattice, which are called lattice-valued finite automata. The extended subset construction of lattice-valued finite automata is introduced, then the equivalences between lattice-valued finite automata, lattice-valued deterministic finite automata and lattice-valued finite automata with varepsilon$-moves are proved. We give a simple characterization of lattice-valued languages recognized by lattice-valued finite automata, then we prove that the Kleene theorem holds in the frame of lattice-setting. A minimization algorithm of lattice-valued deterministic finite automata is presented. In particular, the role of the distributive law for the truth valued domain of finite automata is analyzed: the distributive law is not necessary to many constructions of lattice-valued finite automata, but it indeed provides some convenience in simply processing lattice-valued finite automata.
Keywords:Finite automata;language;language;lattice;subset construction.
 
 
 

For this paper

  • PDF (0B)
  • ● Revision 0   
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags

Add yours

Related Papers

Statistics

PDF Downloaded 759
Bookmarked 0
Recommend 5
Comments Array
Submit your papers