Equivalence in automata theory based on complete residuated lattice-valued logic

Automata theory based on complete residuated lattice-valued logic, called L-valued finite automata (abbr. L-VFAs), was introduced by the second author in 2001. In this paper we deal with the problems of equivalence between L-valued sequential machines (abbr. L-VSMs) and L-VFAs. We define L-VSMs, and particularly present a method for deciding the equivalence between L-VSMs as well. An algorithm procedure for deciding the equivalence between L-VSMs is constructed. We analyze the complexity and efficiency of the algorithm procedure and obtain the relative results to L-VFAs. Moreover, the definitions of L-valued languages (abbr. L-VLs), and L-valued regular languages (abbr. L-VRLs) recognized by L-VFAs are given, and some related properties are also discussed. We show an equivalent relation between L-VRLs and conventional regular languages. By using L-valued pumping lemma, we get a necessary and sufficient condition for an L-VL to be nonconstant.