Brzozowski type determinization for fuzzy automata
Preprint
Abstract
In this paper we adapt the well-known Brzozowski determinization method to fuzzy automata. This method gives better results than all previously known methods for determinization of fuzzy automata developed by B\v{e}lohl\'avek [Inform Sciences 143 (2002) 205--209], Li and Pedrycz [Fuzzy Set Syst 156 (2005) 68--92], Ignjatovi\'c et al. [Inform Sciences 178 (2008) 164--180], and Jan\v{c}i\'c et al. [Inform Sciences 181 (2011) 1358--1368]. Namely, as in the case of ordinary nondeterministic automata, Brzozowski type determinization of a fuzzy automaton results in a minimal crisp-deterministic fuzzy automaton equivalent to the starting fuzzy automaton, and we show that there are cases when all previous methods result in infinite automata, while Brzozowski type determinization results in a finite one. The paper deals with fuzzy automata over complete residuated lattices, but identical results can also be obtained in a more general context, for fuzzy automata over lattice-ordered monoids, and even for weighted automata over commutative semirings.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Automata theory based on complete residuated lattice-valued logic: Reduction and minimizationFuzzy Sets and Systems, 2010
- Myhill–Nerode type theory for fuzzy languages and automataFuzzy Sets and Systems, 2010
- Automata theory based on complete residuated lattice-valued logic: Pushdown automataFuzzy Sets and Systems, 2009
- On the recognizability of fuzzy languages IIFuzzy Sets and Systems, 2008
- Determinization of fuzzy automata with membership values in complete residuated latticesInformation Sciences, 2008
- Minimization of lattice finite automata and its application to the decomposition of lattice languagesFuzzy Sets and Systems, 2007
- On the recognizability of Fuzzy languages IFuzzy Sets and Systems, 2006
- Pumping lemma in automata theory based on complete residuated lattice-valued logic: A noteFuzzy Sets and Systems, 2006
- Fuzzy finite automata and fuzzy regular expressions with membership values in lattice-ordered monoidsFuzzy Sets and Systems, 2005
- Automata theory based on complete residuated lattice-valued logicScience China Information Sciences, 2001