| ¡¡ | Chinese Journal of Computers Full Text |
| Title | Fuzzy Finite Automata and Monadic Second-Order Lukasiewicz Logic |
| Authors | LI Yong-Ming |
| Address | (College of Computer Science, Shaanxi Normal University, Xi¡¯an 710062) |
| Year | 2008 |
| Issue | No.10(1788¡ª1794) |
| Abstract & Background | Abstract The authors introduce monadic second-order (MSO-) Lukasiewicz logic and prove that the behaviors of fuzzy finite automata are precisely the fuzzy languages definable with sentences of the MSO Lukasiewicz logic. This generalizes B¨¹chi¡¯s and Elgot¡¯s fundamental theorems to fuzzy logic setting. The authors also consider first-order Lukasiewicz logic and show that star-free fuzzy languages and aperiodic fuzzy languages introduced here coincide with the first-order definable ones. Keywords fuzzy logic£» finite automata; monadic second-order Lukasiewicz logic; fuzzy language; fuzzy computation Background Early in the history of theoretical computer science, it came to light that formal languages would be one of the foundations of further research. Therefore characterizing all languages, or even better sorting them in some hierarchy, was an important issue. For example, the regular languages can be characterized by finite automata and by regular expressions. Myhill and Nerode independently showed that this is equivalent to a characterization by finite monoids. The equivalence to monadic second-order logic is given by B¨¹chi and Elgot. They further give a sort of regular languages definable by first-order logic. Recently, Droste and Gastin gave a further generalization to monadic second-order logic characterization of regular languages in the frame of formal power series. Classical formal languages are precise defined languages, they are very useful in the describing of machine languages. But it is not powerful in the processing of human languages. For this, Zadeh introduced the notion of fuzzy languages and gave some characterizations. For example, fuzzy regular languages can be characterized by fuzzy finite automata, fuzzy regular expressions, fuzzy grammars, etc. While there is no any results on the monadic second-order logic characterization of fuzzy regular languages. How to characterize fuzzy regular languages by monadic second-order logic in fuzzy setting is an open problem. The author and his collaborators have done some work in this way. In the frame of well-known residual-logic-Lukasiewicz fuzzy logic, they gave the definition of fuzzy finite automata, and presented the corresponding syntactic and semantics of monadic second-order logic, the fuzzy B¨¹chi-Elgot theorem is set up. Furthermore, they give the characterization of fuzzy languages definable by first-order Lukasiewicz-logic, and a sort of fuzzy regular languages is given. The workgroup has studied fuzzy automata for many years. In particular, they introduced the notion of lattice-valued automata£Û9£Ý, which forms one of the main topics in the study of fuzzy automata. Many interesting results have been obtained in this field. The study of monadic second-order fuzzy logic of fuzzy automata is one of these results. |