Notes on Automata, Logics, Games and Algebra
by K Narayan Kumar
Publisher: Chennai Mathematical Institute 2007
Description:
Contents: Regular Languages and Monoids; Languages via Logical Formulae; MSO to Regular Languages; EF Games and First-order Definability; Schutzenberger's Theorem; Alternating Automata; Buchi Automata; Buchi Games over Infinite Graphs; Complementation via Alternating Automata; Safra's Determinization Construction; From Streett Automata to Rabin Automata and Back; etc.
Download or read it online for free here:
Download link
(multiple PDF files)
Similar books
Automata Theory: An Algorithmic Approachby Javier Esparza
These notes introduce the theory of finite- and omega-automata from an algorithmic point of view. They present automata as a data structure for sets that allows for efficient implementations of the basic set-theoretical operations.
(3434 views)
Cellular Automata: Simplicity Behind Complexityby Alejandro Salcido - InTech
Cellular automata make up a class of discrete dynamical systems, which are a core subject in the sciences of complexity due to their conceptual simplicity, easiness of implementation for computer simulation, and their amazingly complex behavior.
(13076 views)
Tree Automata Techniques and Applicationsby H. Comon, M. Dauchet, R. Gilleron
This textbook presents the basics of tree automata, focusing on the operational aspects. It should appeal the reader who wants a simple presentation of the basics, and to see how some variations of tree automata provide a tool for difficult problems.
(17387 views)
Automata and Rational Expressionsby Jacques Sakarovitch - arXiv.org
From the table of contents: A new look at Kleene's theorem; Rationality and recognisability (Rational expressions); From automata to expressions; From expressions to automata; Changing the monoid; Introducing weights; Notes; References.
(8137 views)