Read While You Wait - Get immediate ebook access, if available*, when you order a print book

Lecture Notes in Artificial Intelligence

Logic and Games on Automatic Structures

Playing with Quantifiers and Decompositions

Authors: Kaiser, Lukasz

Free Preview
  • <p>Innovative study in the area of algorithmic model theory </p>  <p>Based on awarded dissertation </p> <p>State-of-the-art research</p>

Buy this book

eBook $44.99
price for USA in USD (gross)
  • ISBN 978-3-642-22807-0
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $59.99
price for USA in USD
  • ISBN 978-3-642-22806-3
  • Free shipping for individuals worldwide
  • Immediate ebook access, if available*, with your print order
  • Usually dispatched within 3 to 5 business days.
About this book

The evaluation of a logical formula can be viewed as a game played by two opponents, one trying to show that the formula is true and the other trying to prove it is false. This correspondence has been known for a very long time and has inspired numerous research directions. In this book, the author extends this connection between logic and games to the class of automatic structures, where relations are recognized by synchronous finite automata.

In model-checking games for automatic structures, two coalitions play against each other with a particular kind of hierarchical imperfect information. The investigation of such games leads to the introduction of a game quantifier on automatic structures, which connects alternating automata with the classical model-theoretic notion of a game quantifier. This study is then extended, determining the memory needed for strategies in infinitary games on the one hand, and characterizing regularity-preserving Lindström quantifiers on the other. Counting quantifiers are investigated in depth: it is shown that all countable omega-automatic structures are in fact finite-word automatic and that the infinity and uncountability set quantifiers are definable in MSO over countable linear orders and over labeled binary trees.

This book is based on the PhD thesis of Lukasz Kaiser, which was awarded with the E.W. Beth award for outstanding dissertations in the fields of logic, language, and information in 2009. The work constitutes an innovative study in the area of algorithmic model theory, demonstrating the deep interplay between logic and computability in automatic structures. It displays very high technical and presentational quality and originality, advances significantly the field of algorithmic model theory and raises interesting new questions, thus emerging as a fruitful and inspiring source for future research.

Table of contents (8 chapters)

Table of contents (8 chapters)

Buy this book

eBook $44.99
price for USA in USD (gross)
  • ISBN 978-3-642-22807-0
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $59.99
price for USA in USD
  • ISBN 978-3-642-22806-3
  • Free shipping for individuals worldwide
  • Immediate ebook access, if available*, with your print order
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
Logic and Games on Automatic Structures
Book Subtitle
Playing with Quantifiers and Decompositions
Authors
Series Title
Lecture Notes in Artificial Intelligence
Series Volume
6810
Copyright
2011
Publisher
Springer-Verlag Berlin Heidelberg
Copyright Holder
Springer-Verlag GmbH Berlin Heidelberg
eBook ISBN
978-3-642-22807-0
DOI
10.1007/978-3-642-22807-0
Softcover ISBN
978-3-642-22806-3
Edition Number
1
Number of Pages
XII, 118
Topics

*immediately available upon purchase as print book shipments may be delayed due to the COVID-19 crisis. ebook access is temporary and does not include ownership of the ebook. Only valid for books with an ebook version. Springer Reference Works are not included.