Издательство Springer, 2011, -125 pp.
Since 2002, FoLLI, the Association for Logic, Language, and Information (www.folli.org), has awarded an annual prize for an outstanding dissertation in the fields of logic, language, and information.
The prize is named after the well-known Dutch logician Evert Willem Beth, whose interdisciplinary interests are in many ways exemplary of the aims of FoLLI. It is sponsored by the E.W. Beth Foundation. Dissertations submitted for the prize are judged on technical depth and strength, originality, and impact made in at least two of the three fields of logic, language, and computation. Every year the competition is strong and the interdisciplinary character of the award stimulates lively debate in the Beth Prize Committee.
Recipients of the award are offered the opportunity to prepare a book version of their thesis for publication in the FoLLI Publications on Logic, Language and Information.
This volume is based on the PhD thesis of ?ukasz Kaiser, who was a joint winner of the E.W. Beth dissertation award in 2009.
We wish to quote here the Committee’s motivation for co-awarding the prize to him.
?ukasz Kaiser’s thesis on ‘Logic and Games on Automatic Structures’ is a very rich, technically highly involved, and innovative study in the area of algorithmic model theory, demonstrating the deep interplay between logic and computability in automatic structures.
In his thesis Dr. Kaiser solves several open problems, some of them in a surprising way and with very original ideas. In particular, he shows that first order logic extended with regular game quantifiers is decidable in automatic structures and develops model-checking games for automatic structures. He also characterizes completely the unary generalized Lindstrom quantifiers that preserve regularity of relations in all omega-automatic structures, inter alia showing that all countable omega-automatic structures are in fact finite-word automatic.
Further, he proves the definability of the infinity and uncountability set quantifiers in MSO over countable linear orders and over labelled binary trees. The thesis of ?ukasz Kaiser displays very high technical and presentational quality, depth, originality, and rigor. It advances significantly the field of algorithmic model theory and raises interesting new questions, thus emerging as a fruitful and inspiring source for future research.
Logics, Structures and Presentations
Game Quantifiers on Automatic Presentations
Games for Model Checking on Automatic Structures
Memory Structures for Infinitary Games
Counting Quantifiers on Automatic Structures
Cardinality Quantifiers in MSO on Linear Orders
Cardinality Quantifiers in MSO on Trees
Outlook
Since 2002, FoLLI, the Association for Logic, Language, and Information (www.folli.org), has awarded an annual prize for an outstanding dissertation in the fields of logic, language, and information.
The prize is named after the well-known Dutch logician Evert Willem Beth, whose interdisciplinary interests are in many ways exemplary of the aims of FoLLI. It is sponsored by the E.W. Beth Foundation. Dissertations submitted for the prize are judged on technical depth and strength, originality, and impact made in at least two of the three fields of logic, language, and computation. Every year the competition is strong and the interdisciplinary character of the award stimulates lively debate in the Beth Prize Committee.
Recipients of the award are offered the opportunity to prepare a book version of their thesis for publication in the FoLLI Publications on Logic, Language and Information.
This volume is based on the PhD thesis of ?ukasz Kaiser, who was a joint winner of the E.W. Beth dissertation award in 2009.
We wish to quote here the Committee’s motivation for co-awarding the prize to him.
?ukasz Kaiser’s thesis on ‘Logic and Games on Automatic Structures’ is a very rich, technically highly involved, and innovative study in the area of algorithmic model theory, demonstrating the deep interplay between logic and computability in automatic structures.
In his thesis Dr. Kaiser solves several open problems, some of them in a surprising way and with very original ideas. In particular, he shows that first order logic extended with regular game quantifiers is decidable in automatic structures and develops model-checking games for automatic structures. He also characterizes completely the unary generalized Lindstrom quantifiers that preserve regularity of relations in all omega-automatic structures, inter alia showing that all countable omega-automatic structures are in fact finite-word automatic.
Further, he proves the definability of the infinity and uncountability set quantifiers in MSO over countable linear orders and over labelled binary trees. The thesis of ?ukasz Kaiser displays very high technical and presentational quality, depth, originality, and rigor. It advances significantly the field of algorithmic model theory and raises interesting new questions, thus emerging as a fruitful and inspiring source for future research.
Logics, Structures and Presentations
Game Quantifiers on Automatic Presentations
Games for Model Checking on Automatic Structures
Memory Structures for Infinitary Games
Counting Quantifiers on Automatic Structures
Cardinality Quantifiers in MSO on Linear Orders
Cardinality Quantifiers in MSO on Trees
Outlook