Logic and Games on Automatic Structures

Name: Logic and Games on Automatic Structures
Brand: Springer, Berlin
SKU: 9783642228063
Price: 296.72 RON
Availability: InStock

Playing with Quantifiers and Decompositions

Autor: ukasz Kaiser

Limbă:

Legare: Carte broșată

Editura: Springer, Berlin

Disponibilitate: În depozitul extern în cantități mici

Expediem în 11-15 zile

296.72 lei

The evaluation of a logical formula can be viewed as a game played by two opponents, one trying to s...

Informații despre carte

Autor

ukasz Kaiser

Limbă

engleză

Legare

Carte - Carte broșată

Publicat

2011

Pagini

118

EAN

9783642228063

ISBN

3642228062

Enbook ID

01658513

Editura

Springer, Berlin

Greutate

217

Dimensiuni

159 x 235 x 11

Descriere completă

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 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 Ph.D thesis of ukasz Kaiser, that was awarded with the E.W. Beth award for outstanding dissertations in the fields of logic, language, and information in 2009. The work is 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.

S-ar putea să te intereseze

Clienții care au cumpărat această carte au mai cumpărat și

Cele mai căutate

Categories

Authors

Publishers

Produse

Produse

Cele mai căutate

Categories

Authors

Publishers

Produse

Produse

Logic and Games on Automatic Structures

Playing with Quantifiers and Decompositions

Informații despre carte

Descriere completă

S-ar putea să te intereseze

Clienții care au cumpărat această carte au mai cumpărat și