Abstract: Miroslav Ćirić

FUZZY AND WEIGHTED AUTOMATA: DETERMINIZATION, STATE REDUCTION, STRUCTURAL EQUIVALENCE

 

 

           We give a short overview of our current research in the algebraic theory of fuzzy and weighted automata. First, we have developed the general Myhill-Nerode type theory for fuzzy languages and deterministic fuzzy recognizers, where the underlying structure of truth values is taken to be an arbitrary set with two distinguished elements 0 and 1, which are needed to take crisp languages in consideration. Such structure is very general and includes all structures used for modelling membership values in the fuzzy set theory, semirings, strong bimonoids, etc. In particular, we have shown that any fuzzy language possess the minimal deterministic fuzzy recognizer recognizing it (if it is finite, then it is unique up to an isomorphism), we have given algorithms for construction of the minimal deterministic fuzzy recognizer of a fuzzy language and for minimization of a deterministic fuzzy recognizer, and we have given various algorithms for determinization of fuzzy automata over complete residuated lattices and lattice-ordered monoids, and for determinization of weighted automata over semirings and strong bimonoids. Next, we have established close relationships between state reduction of a fuzzy recognizer and resolution to a particular system of fuzzy relation equations, and we have given powerful methods for state reduction by means of fuzzy equivalences and fuzzy quasi-orders. Finally, we have introduced the concept of a uniform fuzzy relation, and we have shown that it can be successfully aplied to study of bisimulations and structural equivalence for fuzzy automata over complete residuated lattices, as well as for weighted automata over additively idempotent semirings. We have applied the obtained results in approximate reasoning, especially in fuzzy control, network analysis, fuzzy discrete event systems theory, and other fields.

 

 

 

Joint work with:

J. Ignjatović, S. Bogdanović, T. Petković, A. Stamenković, N. Damljanović, M. Bašić, Z. Jančić,

I. Jančić, M. Droste and H. Vogler.