Pebble Lattice-valued Automata And Bounded Transitive Closure Logic

As a mathematical model of computation, finite automata has many impor-tant 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 au-tomaton. As usual, the membership value of fuzzy finite-state automata is taken in the unit interval [0,1]with max-min composition, in order to enhance the pro-cessing ability of fuzzy automata, the membership grades were extended to much general algebraic structures. Fuzzy automaton is an expansion of the mathemati-cal 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 lattice-valued finite automata, lattice-valued deterministic fi-nite automata and lattice-valued finite automata with ε—moves. It was proved that the Kleene theorem holds in the frame of lattice-setting. There are so abundant theoretical achievements about the connections between logical and state-based for-malisms, 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 lattice-valued finite automata and lattice-valued logic. The content of this paper is arranged as follows:1. We introduce monadic second-order lattice-valued logic and prove that the behaviors of finite automata based on lattice-valued logic are precisely the lattice- valued languages definable with sentences of our monadic second-order lattice-valued logic. This generalizes Buchi and Elgot’s fundamental theorems to lattice-valued logic setting. We also consider first-order lattice-valued logic and show that star-free lattice-valued languages and aperiodic lattice-valued languages introduced here coin-cide with the first-order lattice-valued definable ones. This generalizes Schutzenberger’s fundamental theorems to lattice-valued logic setting.2. We introduce first-order logic with bounded transitive closure operator under the general lattice, and give the new logical characterizations of lattice-valued finite automata.3. We introduce two classes of lattice-valued automata:pebble lattice-valued finite automata and lattice-valued nested finite automata. Both kinds of lattice-valued finite automata are expressively equivalence with the fuzzy first-order logic with bounded transitive closure operator.