Minimization of lattice finite automata and its application to the decomposition of lattice languages

摘要

In this paper, we study the minimization of lattice-valued finite automata with membership values in a distributive lattice and its relationships to the decomposition of lattice-valued regular languages. First, we establish the equivalence of (nondeterministic) lattice finite automata (LA) and deterministic lattice finite automata (DLA). Furthermore, we provide some characterization of lattice-valued regular languages and regular operations on family of lattice-valued regular languages. In the sequel, we introduce some notions that help clarify the concept of minimal DLAs and present an effective algorithm to obtain a minimal DLA from a given LA. Using the construction of minimal DLA, we introduce some simple classes of lattice-valued regular languages such as L-unitary and L-prefix ones. We demonstrate that any lattice-valued regular language can be decomposed as disjoint joins of such kinds of simple languages.