Pseudo-semirings And Their Applications In Automata Theory

Weighted finite automata are classical nondeterministic automata in which the transitions carry weights. The weights often form the algebraic structure of a semir-ing. Weighted finite automata valued in semirings have both a well studied and theory as well as practical applications.Recently, a number of authors investigated weighted automata with weights in more general structures-pseudo semirings (which are also called strong bimonoids). Pseudo semirings can be viewed as semirings which might lack distributivity. Semir-ings, lattice-ordered moboids, complete (orthomodular) lattices are all the special cases of pseudo semirings. Manfred Droste have given the behavior of pseudo weighted finite automata (which are also called weighted finite automata over strong bimonoids, P-NFA, for short) based on three semantics. And some properties of pseudo weighted finite automata and the determinization of them have been studied respectively. In this thesis, we investigate the other properties of pseudo weighted finite automata.The main contributions in this thesis are listed as follows:(1) Based on seven semantics, the relationships among some typies of pseudo weighted finite automata are studied.Firstly, we have introduced the definitions of ordered pseudo semirings, positive-ordered pseudo semirings, pseudo weighted subsets, pseudo weighted matrices.Secondly, based on the three semantics given by Manfred Droste, the new four semantics are given in this thesis, then we have seven semantics:initial algebra semantics (I), finial algebra semantics(F), initial transition semantics (IT), finial transition semantics (FT), initial hybrid semantics (IH), finial hybrid semantics (FH) and run semantics (R).The definitions of quivalent, left equivalent, right equivalent, right equivalent-?, M-right equivalent, and M-right equivalent-?(where,??M?{I,F,IT,FT,Th, FH,R}). With these definitions, we study the relationships among P - NFA1,P -NFA2, P-NFA3, P-NFA4 and among P-DFA1, P-DFA2, P-DFA3. And the complete conclusions are given.Lastly, we introduced some properties of the reversal of pseudo weighted finite automata based on the seven semantics.(2) The properties of some kinds of pseudo weighted finite automata with output are studied.Some kinds of pseudo weighted finite automata with output are intruduced, such as pseudo weighted transducers, pseudo weighted synchronous machines, pseudo weighted sequential-like machines, pseudo weighted Mealy machines, pseudo weighted Moore machines. Moreover, the realization of delay functions of pseudo weighted transiders, the realization of output-functions and input-functions of pseudo weighted transiders, the minimal-deterministic realization of pseudo weighted transiders and the realization with single-transition of pseudo weighted synchronous machines are given. And by the help of pseudo weighted sequential-like machines, we shown that pseudo weighted Mealy machines and pseudo weighted Moore are not equivalent.(3) The properties of pseudo weighted Turning machines are investigated.In Chapter 4, firstly, based on width-first and depth-first ways, we study the re-lationships between pseudo weighted Turning machines P-TM and pseudo weighted Turning machines with crisp-transition P-TMc, the relationships between pseudo weighted Turning machines with crisp-transition P-TMc and deterministic pseudo weighted Turning machines P-DTM. We show that, P-TM and P-TMc are not equivalent neither based on width-first way nor based on depth-first way, but if P is multiplicatively local finite, P-TM and P-TMc are equivalent based on depth-first way. And we provided that, P-TMc and P-DTM are also not equiv-alent, even if P is additively local finite, but if P is an ordered pseudo semiring, as the recognition machines of finite pseudo weighted recursive languages, P-TMc and P-DTM are equivalent.Secondly, we studied the universality of pseudo weighted Turning machines and proved that the universal P-TM (P-TMc) and the universal P-DTM are exist if P is finite. The universal P-DTM are not exist if P is infinite.