Muutke küpsiste eelistusi

E-raamat: Descriptive Set Theoretic Methods in Automata Theory: Decidability and Topological Complexity

Teised raamatud teemal:
  • Formaat - PDF+DRM
  • Hind: 55,56 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Lisa ostukorvi
  • Lisa soovinimekirja
  • See e-raamat on mõeldud ainult isiklikuks kasutamiseks. E-raamatuid ei saa tagastada.
Descriptive Set Theoretic Methods in Automata Theory: Decidability and Topological ComplexitySuurem pilt
Teised raamatud teemal:

DRM piirangud

  • Kopeerimine (copy/paste):

    ei ole lubatud

  • Printimine:

    ei ole lubatud

  • Kasutamine:

    Digitaalõiguste kaitse (DRM)
    Kirjastus on väljastanud selle e-raamatu krüpteeritud kujul, mis tähendab, et selle lugemiseks peate installeerima spetsiaalse tarkvara. Samuti peate looma endale  Adobe ID Rohkem infot siin. E-raamatut saab lugeda 1 kasutaja ning alla laadida kuni 6'de seadmesse (kõik autoriseeritud sama Adobe ID-ga).

    Vajalik tarkvara
    Mobiilsetes seadmetes (telefon või tahvelarvuti) lugemiseks peate installeerima selle tasuta rakenduse: PocketBook Reader (iOS / Android)

    PC või Mac seadmes lugemiseks peate installima Adobe Digital Editionsi (Seeon tasuta rakendus spetsiaalselt e-raamatute lugemiseks. Seda ei tohi segamini ajada Adober Reader'iga, mis tõenäoliselt on juba teie arvutisse installeeritud )

    Seda e-raamatut ei saa lugeda Amazon Kindle's. 

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 Michal Skrzypczak offers certainly what we expect from excellent mathematics: new unexpected connections between a priori distinct concepts, and proofs involving enlightening ideas." Thomas Colcombet.

Subclasses of regular languages.- Thin algebras.- Extensions of regular languages.

Arvustused

The author applies, with considerable success, a breadth of methods covering descriptive set theory, automata theory, logic and even some classical set theory, to questions on - and tree automata. ... he has managed to present basic material and his own results in such a way as to make these developments accessible to the reader. ... should be useful for those who wish to keep in touch with recent developments in automata theory. (Roger Villemaire, zbMATH 1375.03003, 2018)



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)

1 Basic Notions
1(28)
1.1 Structures
1(4)
1.1.1 Finite Words and co- words
2(1)
1.1.2 Infinite Trees
3(2)
1.2 Logic
5(1)
1.3 Games
6(1)
1.3.1 Positional Strategies
6(1)
1.3.2 Parity Games
7(1)
1.4 Automata
7(3)
1.4.1 Parity Index of an Automaton
10(1)
1.5 Algebra
10(4)
1.5.1 Semigroups and Monoids
11(1)
1.5.2 Wilke Algebras
11(2)
1.5.3 Recognition
13(1)
1.5.4 Ramsey's Theorem for Semigroups
13(1)
1.6 Topology
14(5)
1.6.1 Borel and Projective Hierarchy
14(2)
1.6.2 Topological Complexity
16(1)
1.6.3 Ranks
17(1)
1.6.4 The Boundedness Theorem
17(1)
1.6.5 Co-inductive Definitions
18(1)
1.7 Regular Languages
19(10)
1.7.1 Classes of Regular Tree Languages
21(1)
1.7.2 Index Hierarchies
22(1)
1.7.3 Topological Complexity of Regular Languages
23(1)
1.7.4 The languages Wi,j
23(1)
1.7.5 Separation Property
24(2)
1.7.6 Deterministic Languages
26(3)
Subclasses of Regular Languages
2 Introduction
29(8)
2.1 Motivations
30(3)
2.1.1 Definability in wmso
30(1)
2.1.2 Index Problem
30(1)
2.1.3 Bi-unambiguous Languages
31(1)
2.1.4 Borel Languages
32(1)
2.1.5 Topological Complexity vs. Decidability
32(1)
2.1.6 Separation Property
33(1)
2.2 Overview of the Parts
33(4)
2.2.1 Part I: Subclasses of Regular Languages
34(1)
2.2.2 Part II: Thin Algebras
35(1)
2.2.3 Part ITI: Extensions of Regular Languages
36(1)
3 Collapse for Unambiguous Automata
37(8)
3.1 Unique Runs
38(2)
3.2 Construction of the Automaton
40(3)
3.2.1 Soundness
41(1)
3.2.2 Completeness
42(1)
3.3 Conclusions
43(2)
4 When a Buchi Language Is Definable in wmso
45(26)
4.1 The Ordinal of a Buchi Automaton
46(6)
4.1.1 Truncated Runs
47(1)
4.1.2 The Reduction
48(2)
4.1.3 Ranks
50(2)
4.2 Extending Runs
52(4)
4.2.1 K-reach Implies Big Rank
53(1)
4.2.2 Big Rank Implies A-reach
54(2)
4.3 Automata for K-safe Trees
56(2)
4.4 Boundedness Game
58(4)
4.4.1 Rules of the Game
59(2)
4.4.2 Winning Condition
61(1)
4.5 Equivalence
62(6)
4.5.1 Implication (1)⇒ (2)
62(4)
4.5.2 Implication (2) ⇒ (1)
66(2)
4.6 Conclusions
68(3)
5 Index Problems for Game Automata
71(22)
5.1 Runs of Game Automata
72(2)
5.2 Non-deterministic Index Problem
74(2)
5.3 Partial Objects
76(3)
5.3.1 Trees
76(1)
5.3.2 Games
77(1)
5.3.3 Automata
77(1)
5.3.4 Composing Automata
78(1)
5.3.5 Resolving
78(1)
5.4 Alternating Index Problem
79(10)
5.4.1 The Algorithm
79(2)
5.4.2 Upper Bounds
81(3)
5.4.3 Lower Bounds
84(5)
5.5 Conclusions
89(4)
Thin Algebras
6 When a Thin Language Is Definable in wmso
93(28)
6.1 Basic Notions
95(7)
6.1.1 Thin Trees
95(1)
6.1.2 Automata
96(1)
6.1.3 Examples of Skurczyhski
97(1)
6.1.4 Ranks
98(2)
6.1.5 Skeletons
100(2)
6.2 Thin Algebra
102(3)
6.2.1 The Automaton Algebra
104(1)
6.3 Upper Bounds
105(5)
6.3.1 Embeddings and Quasi-skeletons
106(3)
6.3.2 Proof of Proposition 6.13
109(1)
6.4 Characterisation of WMSO-definable Languages
110(8)
6.4.1 Implication (2) ⇒ (3)
110(5)
6.4.2 Implication (5) ⇒ (1)
115(3)
6.5 Conclusions
118(3)
7 Recognition by Thin Algebras
121(16)
7.1 Prophetic Thin Algebras
122(3)
7.2 Bi-unambiguous Languages
125(5)
7.2.1 Prophetic Thin Algebras Recognise only Bi-unambiguous Languages
125(1)
7.2.2 Markings by the Automaton Algebra for an Unambiguous Automaton
126(3)
7.2.3 Every Bi-unambiguous Language is Recognised by a Prophetic Thin Algebra
129(1)
7.3 Consequences of Conjecture 2.1
130(1)
7.4 Decidable Characterisation of the Bi-unambiguous Languages
131(4)
7.4.1 Pseudo-syntactic Morphisms
132(2)
7.4.2 Decidable Characterisation
134(1)
7.5 Conclusions
135(2)
8 Uniformization on Thin Trees
137(22)
8.1 Basic Notions
138(1)
8.2 Transducer for a Uniformized Relation
139(4)
8.3 Choice Hypothesis
143(8)
8.3.1 Equivalence (1) ⇔ (2)
144(1)
8.3.2 Implication (2) ⇒ (3)
145(5)
8.3.3 Implication (4) ⇒ (2)
150(1)
8.4 Negative Results
151(5)
8.4.1 Green's Relations
151(1)
8.4.2 A Marking of a Thick Tree
152(2)
8.4.3 Non-uniformizability of Skeletons
154(1)
8.4.4 Ambiguity of Thin Trees
155(1)
8.5 Conclusions
156(3)
Extensions of Regular Languages
9 Descriptive Complexity of mso+u
159(14)
9.1 Basic Notions
160(3)
9.1.1 Languages IFi'
162(1)
9.2 Languages Hi
163(3)
9.3 Functions ci, di, and ri
166(2)
9.4 Reductions
168(1)
9.5 Upper Bounds
169(2)
9.5.1 Proof of Theorem 9.7
170(1)
9.6 Conclusions
171(2)
10 Undecidability of mso+u
173(10)
10.1 Basic Notions
175(2)
10.1.1 Godel's Constructible Universe
175(1)
10.1.2 Projective mso
176(1)
10.2 Reduction
177(1)
10.3 Projective Determinacy
178(2)
10.4 Undecidability of proj-Mso on {L, R}ω
180(1)
10.4.1 Proof of Theorem 10.88
180(1)
10.5 Conclusions
181(2)
11 Separation for ωB- and ωS-regular Languages
183(22)
11.1 Basic Notions
184(4)
11.1.1 Monoid of Runs
184(1)
11.1.2 Profinite Monoid
185(2)
11.1.3 Ramsey-Type Arguments
187(1)
11.1.4 Notation
188(1)
11.2 Automata
188(5)
11.2.1 ωB- and ωS-automata
189(1)
11.2.2 B-and S-automata
190(1)
11.2.3 Languages
191(2)
11.3 Separation for Profinite Languages
193(2)
11.4 Reduction
195(5)
11.4.1 Implication (1) ⇒ (2)
197(2)
11.4.2 Implication (2) ⇒ (3)
199(1)
11.4.3 Implication (3) ⇒ (1)
199(1)
11.5 Separation for ω-languages
200(2)
11.6 Conclusions
202(3)
12 Conclusions
205(2)
References 207
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. Mikoaj Bojaczyk (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.
Lisainfo e-raamatute kohta Lisainfo e-raamatute kohta
Püsilink: https://www.kriso.ee/db/97836625294782e.html
Märksõnad: