Affiliations: Dep. of Math. and Comp. Sc. Saint Mary's
University Halifax B3H 3C3, NS, Canada. E-mail: [email protected] | School of Computer Science, University of Waterloo,
Waterloo N2L 3G1, ON, Canada. E-mail: [email protected] | Department of Computer Science, University of Western
Ontario London N6A 5B8, ON, Canada. E-mail: [email protected]
Abstract: In this paper we present a different framework for the study of
fuzzy finite machines and their fuzzy languages. Unlike the previous work on
fuzzy languages, characterized by fuzzification at the level of their
acceptors/generators, here we follow a top-down approach by starting our
fuzzification with more abstract entities: monoids and particular families in
monoids. Moreover, we replace the unit interval (in fact, a finite subset of
the unit interval) as support for fuzzy values with the more general structure
of a lattice. We have found that completely distributive complete lattices
allow the fuzzification at the highest level, that of recognizable and rational
sets. Quite surprisingly, the fuzzification process has not followed thoroughly
the classical (crisp) theory. Unlike the case of rational sets, the
fuzzification of recognizable sets has revealed a few remarkable exceptions
from the crisp theory: for example the difficulty of proving closure properties
with respect to complement, meet and inverse morphisms. Nevertheless, we
succeeded to prove the McKnight and Kleene theorems for fuzzy sets by making
the link between fuzzy rational/recognizable sets on the one hand and fuzzy
regular languages and FT-NFA languages (languages defined by NFA with fuzzy
transitions) on the other. Finally, we have drawn the attention to fuzzy
rational transductions, which have not been studied extensively and which bring
in a strong note of applicability.
