# Handbook of Automata Theory

Volume II

## 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. 841–869 Rational subsets of groupsLaurent BartholdiPedro Silva

DOI 10.4171/AUTOMATA-2/1pp. 871–911 Groups defined by automataLaurent BartholdiPedro Silva

DOI 10.4171/AUTOMATA-2/2pp. 913–945 Automata in number theoryBoris AdamczewskiJason Bell

DOI 10.4171/AUTOMATA-2/3pp. 947–986 On Cobham’s theoremFabien DurandMichel Rigo

DOI 10.4171/AUTOMATA-2/4pp. 987–1030 Symbolic dynamicsMarie-Pierre BéalJean BerstelSøren EilersDominique Perrin

DOI 10.4171/AUTOMATA-2/5pp. 1031–1070 Automatic structuresSasha Rubin

DOI 10.4171/AUTOMATA-2/6pp. 1071–1103 Automata and finite model theoryWouter GeladeThomas Schwentick

DOI 10.4171/AUTOMATA-2/7pp. 1105–1143 Finite automata, image manipulation, and automatic real functionsJuhani KarhumäkiJarkko Kari

DOI 10.4171/AUTOMATA-2/8pp. 1147–1188 Communicating automataDietrich KuskeAnca Muscholl

DOI 10.4171/AUTOMATA-2/9pp. 1189–1215 Symbolic methods and automataBernard Boigelot

DOI 10.4171/AUTOMATA-2/10pp. 1217–1260 Synthesis with finite automataIgor Walukiewicz

DOI 10.4171/AUTOMATA-2/11pp. 1261–1294 Timed automataPatricia Bouyer

DOI 10.4171/AUTOMATA-2/12pp. 1295–1341 Higher-order recursion schemes and their automata modelsArnaud CarayolOlivier Serre

DOI 10.4171/AUTOMATA-2/13pp. 1343–1382 Analysis of probabilistic processes and automata theoryKousha Etessami

DOI 10.4171/AUTOMATA-2/14pp. 1383–1413 Natural language parsingMark-Jan NederhofGiorgio Satta

DOI 10.4171/AUTOMATA-2/15pp. 1415–1456 VerificationJavier EsparzaOrna KupfermanMoshe Y. Vardi

DOI 10.4171/AUTOMATA-2/16pp. 1457–1493 Automata and quantum computingAndris AmbainisAbuzer Yakaryılmaz

DOI 10.4171/AUTOMATA-2/17