Algebraic Theory of Automata and Languages

From MaRDI portal





Group-matrix type automata are representations of strongly connected finite automata. The structure of these automata is studied through an investigation of the endomorphism monoids and automorphism groups. Classes of automata as partially ordered sets are studied and a kind of decomposition theory is developed. For the standard classes of regular and context-free languages the operations of insertion, scattered and ordinary deletion of substrings, shuffle as well as their closures are presented in up to 40 percent of the contents. The book collects and presents a number of old and new results on this subject. It is mathematically oriented, and gives no hints for applications. The contents is presented in eight chapters, shortly sketched as follows: Chapter 1 deals with the representations of strongly connected automata through automorphism groups. Chapter 2 generalizes the results from the preceeding Chapter to general automata. Chapter 3 considers sets of automata, partially ordered by homomorphisms. Chapter 4 presents results concerning the insertion and shuffle operations, while Chapter 5 determines the structure of commutative, regular shuffle closed languages. Chapter 6 is devoted to a detailed presentation of insertion and deletion operations, and Chapter 7 deals with the pair of shuffle and scattered deletion. The final Chapter 8 presents the so-called directable automata. References and a small index, not containing all relevant notions finish the 199 pages.




Cited in
(35)








This page was built for publication: Algebraic Theory of Automata and Languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4826930)