Pebble Latticevalued Automata and Bounded Transitive Closure Logic 

Author  FanYanHuan 
Tutor  LiYongMing 
School  Shaanxi Normal University 
Course  Basic mathematics 
Keywords  Latticevalued finite automata MSO Firstorder logic Bounded transitive closure logic Pebble latticeorder finite automata 
CLC  TP301.1 
Type  Master's thesis 
Year  2013 
Downloads  8 
Quotes  0 
As a mathematical model of computation, finite automata has many important applications such as in learning systems, the model of computing with words, pattern recognition and data base theory. Also, automaton can act as a language recognizer for studying various forms of languages. With Zadeh proposed the fuzzy set theory, the ability of linguistic recognition for automaton has been expanded to the application range of the fuzzy set theory, and then produced the fuzzy automaton. As usual, the membership value of fuzzy finitestate automata is taken in the unit interval [0,1]with maxmin composition, in order to enhance the processing ability of fuzzy automata, the membership grades were extended to much general algebraic structures. Fuzzy automaton is an expansion of the mathematical model of automaton, including the concept like "fuzzy""inaccurate", which makes the languages recognized by automata are closer to nature languages, and have been widely used in the field of artificial intelligence. Especially, Li Yongming introduced the fuzzy finite automata based on the general lattice, and proved the equivalence between latticevalued finite automata, latticevalued deterministic finite automata and latticevalued finite automata with ε—moves. It was proved that the Kleene theorem holds in the frame of latticesetting. There are so abundant theoretical achievements about the connections between logical and statebased formalisms, The line of classical results started with the equivalence of MSO logic and finite automata. Recently, Droste generalized these results to the weighted logic Li Yongming generalized these results to the Lukasieuicz logic. In this paper, we will study the relationship between latticevalued finite automata and latticevalued logic. The content of this paper is arranged as follows:1. We introduce monadic secondorder latticevalued logic and prove that the behaviors of finite automata based on latticevalued logic are precisely the lattice valued languages definable with sentences of our monadic secondorder latticevalued logic. This generalizes Buchi and Elgot’s fundamental theorems to latticevalued logic setting. We also consider firstorder latticevalued logic and show that starfree latticevalued languages and aperiodic latticevalued languages introduced here coincide with the firstorder latticevalued definable ones. This generalizes Schutzenberger’s fundamental theorems to latticevalued logic setting.2. We introduce firstorder logic with bounded transitive closure operator under the general lattice, and give the new logical characterizations of latticevalued finite automata.3. We introduce two classes of latticevalued automata:pebble latticevalued finite automata and latticevalued nested finite automata. Both kinds of latticevalued finite automata are expressively equivalence with the fuzzy firstorder logic with bounded transitive closure operator.