On Algebraic Theory Of Automata

The theory of automata is an important foundation of computer science. It has comprehensive application on information science, computing science, biology and so on. As we all know, algebra systems play important roles in the study of automata and languages. The algebra systems involved in this dissertation are mainly semigroups and semirings.The dissertation consists of five chapters.Chapter1. Introduction and preliminaries. We introduce the research background and current state of the algebraic theory of automata. Also, some notions and notations are introduced as preliminaries.Chapter2, Normal commutative asynchronous automata. We introduce and study the class of normal commutative asynchronous automata and one of its’ subclass-cyclic commutative asynchronous automata. It is shows that the endomorphism monoids of cyclic commutative asynchronous automata are meet semilattices.Chapter3,Sl-automata. We provide a necessary and sufficient condition for a endomorphism monoid of an automaton to be a meet semilattice. In particular, we give a necessary and sufficient condition for an endomorphism monoid of a commutative automaton to be a group (meet semilattice).Chapter4, Canonical automata. We introduce and study canonical au-tomata. Some properties of canonical automata are established. Also, we provide the necessary and sufficient conditions for an endomorphism monoid of a canonical automaton to be a group, a meet semilattice and a Clifford monoid, respectively. Chapter5, Representations of automata. By using of the endomorphism monoids, we provide some representations of automata, which generalize and extend the representation of strongly connected automata given by Ito.Chapter6, Weighted automata over strong bimonoid. The rational for-mal power series are studied and the Kleene’s Theorem given by Drost etc. are generalized.