Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoids

We study fuzzy finite automata in which all fuzzy sets are defined by membership functions whose codomain forms a lattice-ordered monoid L. For these L-fuzzy finite automata (L-FFA, for short), we provide necessary and sufficient conditions for the extendability of the state-transition function. It is shown that nondeterministic L-FFA (NL-FFA, for short) are more powerful than deterministic L-FFA (DL-FFA, for short). Then, we give necessary and sufficient conditions for the simulation of an NL-FFA by an equivalent DL-FFA. Next, we turn to the closure properties of languages defined by L-FFAs: we establish closure under the regular operations and provide conditions for closure under intersection and reversal, in particular we show that the family of fuzzy languages accepted by DL-FFAs is not closed under Kleene closure operation, and the family of fuzzy languages accepted by NL-FFAs is not closed under complement operation. Furthermore, we introduce the notions of L-fuzzy regular expressions and give the Kleene theorem for NL-FFAs. The description of DL-FFAs by L-fuzzy regular expressions is also given. Finally, we investigate the level structures of L-FFAs. Our results provide some insight as to what extend properties of L-FFAs and their languages depend on the algebraic properties of L. (c) 2005 Elsevier B.V. All rights reserved.