Open Access
Adjusting fuzzy automata for string similarity measuring
(EUSFLAT, 2001) Astrain Escola, José Javier; Villadangos Alonso, Jesús; González de Mendívil Moreno, José Ramón; Garitagoitia Padrones, José Ramón; Fariña Figueredo, Federico; Ingeniería Matemática e Informática; Matematika eta Informatika Ingeniaritza; Automática y Computación; Automatika eta Konputazioa
In this paper, we introduce a fuzzy automaton for computing the similarity between pairs of strings and a genetic method for adjusting its parameters. The fuzzy automaton models the edit operations needed to transform any string into another one. The selection of appropriate fuzzy operations and fuzzy membership values for the transitions leads to improve the system performance for a particular application.
Open Access
Reduction graph for minimal determinization of fuzzy automata
(Springer, 2023-08-21) González de Mendívil Grau, Aitor; Stanimirovic, Stefan; Fariña Figueredo, Federico; Estadística, Informática y Matemáticas; Estatistika, Informatika eta Matematika
We introduce a minimal determinization procedure for fuzzy finite automata (FfAs) with membership values in a complete residuated lattice (CRL). The method is based on the well-known determinization method via factorization of fuzzy states. However, different to other determinization methods, we do not assume that the CRL is zero divisors free. This fact requires modifying the functions that define the factorization to avoid the zero divisor values when creating the fuzzy states in the determinization procedure. After generating a right-irreducible fuzzy deterministic finite automaton (FDfA) equivalent to the original FfA by determinization via factorization, we construct the so-called reduction graph of this fuzzy automaton, where each arc represents the notion that a fuzzy state is left-reducible by another fuzzy state. By making these left-reductions, we obtain the equivalent minimal FDfA. It is worth mentioning that an empty fuzzy state is always reducible by a nonempty fuzzy state. This behavior, specific for a CRL with zero divisors, has also to be taken into account when the state reduction is carried out.
Embargo
Polynomial crisp-minimization algorithm for fuzzy deterministic automata
(Elsevier, 2024-11-01) González de Mendívil Grau, Aitor; Fariña Figueredo, Federico; Stanimirovic, Stefan; Micic, Ivana; González de Mendívil Moreno, José Ramón; Estadística, Informática y Matemáticas; Estatistika, Informatika eta Matematika; Institute of Smart Cities - ISC
Designing automata minimization algorithms is a significant topic in Automata Theory and Languages with practical applications. In this paper, we develop an efficient minimization algorithm for deterministic fuzzy finite automata over locally finite lattices. More precisely, the algorithm outputs an equivalent minimal crisp-deterministic fuzzy finite automaton for an input fuzzy deterministic finite automaton (FDfA). The running time of the proposed algorithm is polynomial for particular types of locally finite lattices, specifically for max-min-based complete residuated lattices. The intuition behind the proposed algorithm relies on the polynomial minimization algorithm's intuition for ordinary deterministic automata developed by Vazquez de Parga, Garcia, and Lopez (2013) [35]. The motivation for this study comes from the fact that the original algorithm's notions and meanings are lost in the context of fuzzy automata. Thus, we establish a new theoretical foundation that provides the correctness and the polynomial-time nature of this new crisp-minimization algorithm for FDfAs.
Open Access
Minimal determinization algorithm for fuzzy automata
(IEEE, 2023) González de Mendívil Grau, Aitor; Stanimirovic, Stefan; Fariña Figueredo, Federico; Estadística, Informática y Matemáticas; Estatistika, Informatika eta Matematika
The determinization of fuzzy automata is a well-studied problem in theoretical computer science celebrated for its practical applications. Indeed, in the fields of fuzzy discrete event systems, fault diagnosis, clinical monitoring, decision-making systems, and model checking, when a suitable model of a fuzzy automaton is employed, it is desirable to find its language-equivalent deterministic version because of its computational efficiency. Although many methods have been developed to convert a fuzzy automaton to its language equivalent fuzzy deterministic finite automaton (FDfA), they can be applied only for fuzzy automata defined over specific underlying sets of truth values. For example, recently developed determinization methods employ the concept of maximal factorization, which can be defined only on non-locally finite lattices or the Boolean lattice. In addition, not all such determinization methods result in a minimal FDfA. On the other hand, even though such determinization methods have been developed for fuzzy automata over specific underlying structures, these methods cannot be generalized for fuzzy automata over locally finite lattices. This article focuses on filling this gap and develops a novel method for computing a minimal FDfA for a fuzzy automaton defined over a locally finite and divisible residuated lattice. Our method uses the new concept of a reduction graph that emerges from the strict order relation on the resulting fuzzy states, according to which we can construct all minimal FDfAs equivalent to a given fuzzy automaton.

Fariña Figueredo, Federico

Email Address

person.page.identifierURI

Birth Date

Job Title

Last Name

First Name

person.page.departamento

person.page.instituteName

ORCID

person.page.observainves

person.page.upna

Name

Filters

Author

Subject

Date

Has files

Item Type

Type

Settings

Sort By

Results per page

Search Results