Authors:
- This thesis is devoted to studying problems of automata theory from the point of view of descriptive set theory
- Providing effective characterisations of regular languages of infinite trees
- For game automata, for languages of thin trees
- Includes supplementary material: sn.pub/extras
Part of the book series: Lecture Notes in Computer Science (LNCS, volume 9802)
Part of the book sub series: Theoretical Computer Science and General Issues (LNTCS)
Buy it now
Buying options
Tax calculation will be finalised at checkout
Other ways to access
This is a preview of subscription content, log in via an institution to check for access.
Table of contents (12 chapters)
-
Front Matter
-
Subclasses of Regular Languages
-
Front Matter
-
-
Thin Algebras
-
Front Matter
-
-
Extensions of Regular Languages
-
Front Matter
-
-
Back Matter
About this book
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.
Reviews
“The book shows how various techniques from descriptive set theory and logic can be effectively used in the study and understanding of automata theory. The interplay between topological and automata-theoretic methods is presented very nicely and should be useful to researchers in this area.” (Rana Barua, Mathematical Reviews, September, 2017)
Authors and Affiliations
-
University of Warsaw , Warsaw, Poland
Michał Skrzypczak
About the author
Michał Skrzypczak completed a double degree master program in Mathematics and Computer Science at University of Warsaw. His PhD thesis, defended in December 2014, was jointly supervised by Prof. Mikołaj Bojańczyk (Warsaw) and Prof. Igor Walukiewicz (Bordeaux). During the academic year 2014/2015 he was a PostDoc at IRIF in Paris, under supervision of Prof. Thomas Colcombet. Currently, Michał Skrzypczak is an assistant Professor at University of Warsaw.
Bibliographic Information
Book Title: Descriptive Set Theoretic Methods in Automata Theory
Book Subtitle: Decidability and Topological Complexity
Authors: Michał Skrzypczak
Series Title: Lecture Notes in Computer Science
DOI: https://doi.org/10.1007/978-3-662-52947-8
Publisher: Springer Berlin, Heidelberg
eBook Packages: Computer Science, Computer Science (R0)
Copyright Information: Springer-Verlag Berlin Heidelberg 2016
Softcover ISBN: 978-3-662-52946-1Published: 06 August 2016
eBook ISBN: 978-3-662-52947-8Published: 05 August 2016
Series ISSN: 0302-9743
Series E-ISSN: 1611-3349
Edition Number: 1
Number of Pages: XIII, 211
Number of Illustrations: 18 b/w illustrations
Topics: 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