Descriptive Set Theoretic Methods in Automata Theory: Decidability and Topological Complexity

✍ Scribed by Michał Skrzypczak (auth.)

Publisher: Springer-Verlag Berlin Heidelberg
Year: 2016
Tongue: English
Leaves: 212
Series: Lecture Notes in Computer Science 9802
Edition: 1
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

The book is based on the PhD thesis “Descriptive Set Theoretic Methods in Automata Theory,” awarded the E.W. Beth Prize in 2015 for outstanding dissertations in the fields of logic, language, and information. The thesis reveals unexpected connections between advanced concepts in logic, descriptive set theory, topology, and automata theory and provides many deep insights into the interplay between these fields. It opens new perspectives on central problems in the theory of automata on infinite words and trees and offers very impressive advances in this theory from the point of view of topology.

"…the thesis of Michał Skrzypczak offers certainly what we expect from excellent mathematics: new unexpected connections between a priori distinct concepts, and proofs involving enlightening ideas.” Thomas Colcombet.

✦ Table of Contents

Front Matter....Pages I-XIII
Basic Notions....Pages 1-26
Front Matter....Pages 27-27
Introduction....Pages 29-36
Collapse for Unambiguous Automata....Pages 37-43
When a Büchi Language Is Definable in wmso ....Pages 45-69
Index Problems for Game Automata....Pages 71-89
Front Matter....Pages 91-91
When a Thin Language Is Definable in wmso ....Pages 93-119
Recognition by Thin Algebras....Pages 121-135
Uniformization on Thin Trees....Pages 137-156
Front Matter....Pages 157-157
Descriptive Complexity of mso+u ....Pages 159-171
Undecidability of mso+u ....Pages 173-181
Separation for (\omega \mathrm {B}) - and (\omega \mathrm {S}) -regular Languages....Pages 183-203
Conclusions....Pages 205-206
Back Matter....Pages 207-211

✦ Subjects

Mathematical Logic and Formal Languages;Logics and Meanings of Programs;Computation by Abstract Devices;Algorithm Analysis and Problem Complexity;Discrete Mathematics in Computer Science;Software Engineering

📜 SIMILAR VOLUMES

Topology and Borel Structure: Descriptiv

📁 Topology and Borel Structure: Descriptive topology and set theory with applications to functional analysis and measure theory

✍ J.P.R. Christensen (Eds.) 📂 Library 📅 1974 🏛 North Holland 🌐 English

Topology and Borel structure; descriptiv

📁 Topology and Borel structure; descriptive topology and set theory with applications to functional analysis and measure theory

✍ J.P.R. Christensen (Eds.) 📂 Library 📅 1974 🏛 North-Holland Pub. Co.; American Elsevier Pub. Co 🌐 English

Set-Theoretic Topology

📁 Set-Theoretic Topology

✍ George M. Reed 📂 Library 📅 1977 🏛 Elsevier Inc, Academic Press Inc 🌐 English

Decidability and Essential Undecidabilit

📁 Decidability and Essential Undecidability

📂 Fiction

Morse Theoretic Methods in Nonlinear Ana

📁 Morse Theoretic Methods in Nonlinear Analysis and in Symplectic Topology

✍ Paul Biran 📂 Library 📅 2006 🏛 Springer Netherlands 🌐 English

This volume contains contributions to the Séminaire de Mathématiques Supérieures – NATO Advanced Study Institute on "Morse theoretic Methods in non-linear Analysis and Symplectic Topology" which was held at the Université de Montréal in the summer of 2004.

Set Theory and Syntactic Description

📁 Set Theory and Syntactic Description

✍ William S. Cooper 📂 Library 📅 1974 🏛 De Gruyter Mouton 🌐 English