دانلود کتاب اتوماتای وزنی، سری رسمی قدرت و منطق وزنی

A basic concept from Theoretical Computer Science for the speci_cation of formal languages are _nite automata. By equipping the states and transitions of these _nite automata with weights, one obtains the quantitative model of weighted automata. The included weights may model e.g. the amount of resources needed for the execution of a transition, the involved costs, or the reliability of its successful execution. To obtain a uniform model, the underlying weight structure is usually modeled by an abstract semiring. The behavior of a weighted automaton is then represented by a formal power series. A formal power series is de_ned as a map assigning to each word over a given alphabet an element of the semiring, i.e. some weight associated with the respective word. In this work, we put emphasis on the expressive power of weighted automata. More precisely, the main objective is to represent the behaviors of weighted automata by expressively equivalent formalisms. These formalisms include rational operations on formal power series, linear representations by means of matrices, and weighted monadic second-order logic. To this end, we _rst exhibit the classical language-theoretic results of Kleene, Büchi, Elgot and Trakhtenbrot, which concentrate on the expressive power of _nite automata. We further derive a generalized version of the Büchi_Elgot_Trakhtenbrot Theorem addressing formulas, which may have free variables, whereas the original statement concerns only sentences. Then we use the language-theoretic approaches and methods as starting point for our investigations with regard to formal power series. We establish Schützenberger’s extension of Kleene’s Theorem, referred to as Kleene_Schützenberger Theorem. Moreover, we introduce a weighted version of monadic second-order logic, which is due to Droste and Gastin, and analyze its expressive power. By means of this weighted logic, we derive an extension of the Büchi_Elgot_Trakhtenbrot Theorem. Thus, we point out relations among the di_erent speci_cation approaches for formal power series. Further, we relate the notions and results concerning formal power series to their respective counterparts in Language Theory.