Ito M. Algebraic Theory of Automata and Languages

World Scientific, 2004. — 202 p.The theory of formal languages began with the classification of languages by N. Chomsky in Syntactic Structures in 1957. Now, this classification is called the Chomsky hierarchy of languages. On the other hand, the theory of automata was initiated by M.O. Rabin and D. Scott in 1959. Their work can be regarded as the most important first step in the theory of automata in spite of its simplicity.
Since then, these two fields have been developed by many researchers as two important theoretical foundations of computer science.
In this book, we will mainly handle formal languages and au- tomata from the algebraic point of view. In the first two chapters, we will investigate the algebraic structure of automata and then we will deal with a kind of global theory, i.e. partially ordered sets of automata. In the following four chapters, we will study grammars, languages and operations on languages. In the last section, we will introduce special kinds of automata, i.e. directable automata. The subjects in the book seem to be unique compared to other books with similar titles. The contents of the book are based on the author's work which started in the mid 1970s.Group-Matrix Type Automata
General Automata
Classes of Automata as Posets
Languages and Operations
Shuffle Closed Languages
Insertions and Deletions
Shuffles and Scattered Deletions
Directable Automata