Lattice - Valued Algebraic System

Since1960s, the context-free grammar has been playing an important role in compilation technology. In recent years, context-free grammar has been also applied in document format description. In the1980s, based on the formal power series, I. Petre, A. Salomaa and W. Kuich built algebraic system with the purpose of studying the context-free grammar. And they found as well as proved the equivalent rela-tionship among algebraic system, context-free grammar and pushdown automata. In another word, algebraic system can be regarded as another form of context-free grammar. At the same time, the lattice-valued context-free grammar and the lattice-valued context-free language have already been studied perfectly. Therefore, it is necessary to generalize the algebraic system to the lattice ordered monoid and make a research on the relationship among the lattice-valued algebraic system, lattice-valued context-free grammar and lattice-valued context-free language.The following are the main contents and findings:1. Firstly, we define the lattice-valued formal power series, introduce several operations, namely the sum, Cauchy product, Hadamard product, Scalar product and Kleene star on lattice-valued formal power series and discuss the operational properties of them. Then, we propose the concept of cycle-free lattice-valued formal power series and discuss their properties. In the end, we define the lattice-valued equations and discuss their solutions.2. Firstly, we introduce the concept of lattice-valued algebraic system on the basis of the algebraic system and discuss the conditions for the existence of a strong solution of the lattice-valued algebraic system by using the properties of lattice-valued formal power series. Then, by presenting of the transduction rules between lattice-valued algebraic system and lattice-valued context-free grammar, we prove that the lattice-valued context-free grammar is equivalent to the lattice-valued alge-braic system. In the end, through discussing the relationship between lattice-valued algebraic system and lattice-valued context-free language, we draw the conclusion that a language is lattice-valued if and only if it is a solution of a lattice-valued algebraic system.