Handbook of Automata Theory
Volume I. Theoretical Foundations
Editors
Jean-Éric Pin
Université de Paris and CNRS, France

A subscription is required to access this book.
Automata theory is a subject of study at the crossroads of mathematics, theoretical computer science, and applications. In its core it deals with abstract models of systems whose behaviour is based on transitions between states, and it develops methods for the description, classification, analysis, and design of such systems.
The Handbook of Automata Theory gives a comprehensive overview of current research in automata theory, and is aimed at a broad readership of researchers and graduate students in mathematics and computer science.
Volume I is divided into three parts. The first part presents various types of automata: automata on words, on infinite words, on finite and infinite trees, weighted and maxplus automata, transducers, and two-dimensional models. Complexity aspects are discussed in the second part. Algebraic and topological aspects of automata theory are covered in the third part.
Volume II consists of two parts. The first part is dedicated to applications of automata in mathematics: group theory, number theory, symbolic dynamics, logic, and real functions. The second part presents a series of further applications of automata theory such as message-passing systems, symbolic methods, synthesis, timed automata, verification of higher-order programs, analysis of probabilistic processes, natural language processing, formal verification of programs and quantum computing.
The two volumes comprise a total of thirty-nine chapters, with extensive references and individual tables of contents for each one, as well as a detailed subject index.
pp. i–iv Front matterpp. v–ix Dedication and Prefacepp. xi–xv Contentspp. xvii–xxiii List of contributorspp. 3–38 Finite automataJean-Éric Pin
pp. 39–78 Automata and rational expressionsJacques Sakarovitch
pp. 79–111 Finite transducers and rational transductionsTero HarjuJuhani Karhumäki
pp. 113–150 Weighted automataManfred DrosteDietrich Kuske
pp. 151–188 Max-plus automataSylvain LombardyJean Mairesse
pp. 189–234 -AutomataSven ScheweThomas Wilke
pp. 235–264 Automata on finite treesChristof LödingWolfgang Thomas
pp. 265–302 Automata on infinite treesChristof Löding
pp. 303–333 Two-dimensional modelsStefano Crespi ReghizziDora GiammarresiVioletta Lonati
pp. 337–373 Minimisation of automataJean BerstelLuc BoassonOlivier CartonIsabelle Fagnot
pp. 375–409 Learning algorithmsHenrik BjörklundJohanna BjörklundWim Martens
pp. 411–457 Descriptional complexity of regular languagesHermann GruberMarkus HolzerMartin Kutrib
pp. 459–491 Enumerating regular expressions and their languagesHermann GruberJonathan LeeJeffrey Shallit
pp. 493–523 Circuit complexity of regular languagesMichal Koucký
pp. 525–565 Černý’s conjecture and the road colouring problemJarkko KariMikhail V. Volkov
pp. 569–614 VarietiesHoward StraubingPascal Weil
pp. 615–652 Profinite topologiesJorge AlmeidaAlfredo Costa
pp. 653–693 The factorisation forest theoremThomas Colcombet
pp. 695–728 Wadge–Wagner hierarchiesJacques Duparc
pp. 729–764 Equational theories for automataZoltán Ésik
pp. 765–799 Language equationsMichal KuncAlexander Okhotin
pp. 801–838 Algebra for treesMikołaj Bojańczyk