Finite automata theory with membership values in lattices |
| |
Authors: | Yongming Li |
| |
Affiliation: | College of Computer Science, Shaanxi Normal University, Xi’an 710062, China |
| |
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. |
| |
Keywords: | Finite automata Language Lattice Subset construction |
本文献已被 ScienceDirect 等数据库收录! |
|