Article ID Journal Published Year Pages File Type
393876 Information Sciences 2011 15 Pages PDF
Abstract

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 ε-moves are proved. A simple characterization of lattice-valued languages recognized by lattice-valued finite automata is given, then it is proved 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.

Related Topics
Physical Sciences and Engineering Computer Science Artificial Intelligence
Authors
,