Automata Theory and its Applications

Front Cover
Springer Science & Business Media, Jun 8, 2001 - Mathematics - 432 pages
2 Reviews
The theory of finite automata on finite stings, infinite strings, and trees has had a dis tinguished history. First, automata were introduced to represent idealized switching circuits augmented by unit delays. This was the period of Shannon, McCullouch and Pitts, and Howard Aiken, ending about 1950. Then in the 1950s there was the work of Kleene on representable events, of Myhill and Nerode on finite coset congruence relations on strings, of Rabin and Scott on power set automata. In the 1960s, there was the work of Btichi on automata on infinite strings and the second order theory of one successor, then Rabin's 1968 result on automata on infinite trees and the second order theory of two successors. The latter was a mystery until the introduction of forgetful determinacy games by Gurevich and Harrington in 1982. Each of these developments has successful and prospective applications in computer science. They should all be part of every computer scientist's toolbox. Suppose that we take a computer scientist's point of view. One can think of finite automata as the mathematical representation of programs that run us ing fixed finite resources. Then Btichi's SIS can be thought of as a theory of programs which run forever (like operating systems or banking systems) and are deterministic. Finally, Rabin's S2S is a theory of programs which run forever and are nondeterministic. Indeed many questions of verification can be decided in the decidable theories of these automata.
 

What people are saying - Write a review

User Review - Flag as inappropriate

very nice book for students

Contents

II
vii
III
xi
IV
xii
V
3
VI
6
VII
9
VIII
11
IX
16
LXXX
201
LXXXI
202
LXXXIII
204
LXXXIV
207
LXXXV
210
LXXXVII
212
LXXXVIII
214
LXXXIX
216

X
19
XI
22
XII
24
XIII
27
XIV
28
XV
31
XVI
32
XVII
34
XVIII
38
XX
42
XXI
48
XXII
50
XXIV
54
XXV
58
XXVI
59
XXVII
62
XXVIII
64
XXIX
68
XXXI
71
XXXII
73
XXXIII
77
XXXIV
85
XXXVI
87
XXXVII
89
XXXVIII
93
XL
95
XLI
97
XLIII
98
XLIV
101
XLV
103
XLVI
104
XLVII
109
XLVIII
113
L
114
LI
115
LII
117
LIII
119
LIV
120
LV
131
LVI
135
LVIII
139
LIX
142
LXI
143
LXII
146
LXIII
152
LXIV
154
LXV
155
LXVI
159
LXVII
162
LXVIII
167
LXX
171
LXXI
176
LXXII
179
LXXIV
181
LXXV
183
LXXVI
186
LXXVII
190
LXXVIII
193
LXXIX
194
XC
217
XCI
218
XCII
223
XCIII
228
XCIV
231
XCV
235
XCVI
241
XCVII
242
XCVIII
251
XCIX
254
C
255
CI
257
CII
262
CIII
264
CIV
266
CV
268
CVI
273
CVII
279
CVIII
282
CIX
284
CX
287
CXI
292
CXII
293
CXIII
296
CXIV
298
CXV
300
CXVI
310
CXVIII
311
CXIX
319
CXX
321
CXXI
322
CXXII
325
CXXIII
328
CXXIV
330
CXXV
331
CXXVI
332
CXXVII
333
CXXVIII
335
CXXIX
338
CXXX
341
CXXXI
342
CXXXII
346
CXXXIV
350
CXXXV
353
CXXXVII
355
CXXXVIII
357
CXXXIX
361
CXLI
364
CXLII
366
CXLIII
370
CXLIV
374
CXLVI
377
CXLVII
380
CXLVIII
382
CXLIX
384
CL
389
CLI
395
CLII
415
Copyright

Other editions - View all

Common terms and phrases

References to this book

All Book Search results »