000 04344nam a22005775i 4500
001 978-3-642-22807-0
003 DE-He213
005 20240730185141.0
007 cr nn 008mamaa
008 110720s2011 gw | s |||| 0|eng d
020 _a9783642228070
_9978-3-642-22807-0
024 7 _a10.1007/978-3-642-22807-0
_2doi
050 4 _aQ334-342
050 4 _aTA347.A78
072 7 _aUYQ
_2bicssc
072 7 _aCOM004000
_2bisacsh
072 7 _aUYQ
_2thema
082 0 4 _a006.3
_223
100 1 _aKaiser, Lukasz.
_eauthor.
_4aut
_4http://id.loc.gov/vocabulary/relators/aut
_9138136
245 1 0 _aLogic and Games on Automatic Structures
_h[electronic resource] :
_bPlaying with Quantifiers and Decompositions /
_cby Lukasz Kaiser.
250 _a1st ed. 2011.
264 1 _aBerlin, Heidelberg :
_bSpringer Berlin Heidelberg :
_bImprint: Springer,
_c2011.
300 _aXII, 118 p.
_bonline resource.
336 _atext
_btxt
_2rdacontent
337 _acomputer
_bc
_2rdamedia
338 _aonline resource
_bcr
_2rdacarrier
347 _atext file
_bPDF
_2rda
490 1 _aLecture Notes in Artificial Intelligence,
_x2945-9141 ;
_v6810
505 0 _a1 Logics, Structures and Presentations -- 2 Game Quantifiers on Automatic Presentations -- 3 Games for Model Checking on Automatic Structures -- 4 Memory Structures for Infinitary Games -- 5 Counting Quantifiers on Automatic Structures -- 6 Cardinality Quantifiers in MSO on Linear Orders -- 7 Cardinality Quantifiers in MSO on Trees -- 8 Outlook.
520 _aThe 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.
650 0 _aArtificial intelligence.
_93407
650 0 _aMachine theory.
_9138137
650 0 _aComputer science
_xMathematics.
_93866
650 0 _aMathematical logic.
_92258
650 1 4 _aArtificial Intelligence.
_93407
650 2 4 _aFormal Languages and Automata Theory.
_9138138
650 2 4 _aSymbolic and Algebraic Manipulation.
_955589
650 2 4 _aMathematical Logic and Foundations.
_934712
710 2 _aSpringerLink (Online service)
_9138139
773 0 _tSpringer Nature eBook
776 0 8 _iPrinted edition:
_z9783642228063
776 0 8 _iPrinted edition:
_z9783642228087
830 0 _aLecture Notes in Artificial Intelligence,
_x2945-9141 ;
_v6810
_9138140
856 4 0 _uhttps://doi.org/10.1007/978-3-642-22807-0
912 _aZDB-2-SCS
912 _aZDB-2-SXCS
912 _aZDB-2-LNC
942 _cELN
999 _c92673
_d92673