20:
125:(ASMs). The ASM Thesis says that, behaviorally, every algorithm is an ASM. A few convincing axioms enabled derivation of the sequential ASM thesis and the Church–Turing thesis. The ASM thesis has also been proven for some other classes of algorithms.
148:
demands for high-level executable specifications. Later, Gurevich worked with different
Microsoft groups on various efficiency, safety, and security issues, including access control, differential compression, and privacy.
152:
Since 1988, Gurevich has managed the column on Logic in
Computer Science in the Bulletin of the European Association for Theoretical Computer Science. Since 2013 Gurevich has worked primarily on
392:
N. Bjørner, A. Blass, and Y. Gurevich. Content-dependent chunking for differential compression: The local maximum approach. Journal of
Computer Systems Science 76(3-4), 2010, 154-203.
305:
Y. Gurevich. Toward logic tailored for computational complexity. In M Richter et al. (eds.), Computation and Proof Theory. Springer
Lecture Notes in Mathematics 1104, 1984, 175-216.
548:
110:, where he started to work on various aspects of computational complexity theory including average case complexity. He became one of the founders of the emerging field of
347:
and Y. Gurevich. Abstract State
Machines Capture Parallel Algorithms. ACM Transactions on Computational Logic 4(4), 2003, 578–651, and 9(3), 2008, article 19.
172:
278:
Y. Gurevich and L. Harrington. Automata, Trees, and Games. STOC '82: Proceedings of the
Fourteenth annual ACM Symposium on Theory of Computing, 1982, 60-65.
360:. Interactive Small-Step Algorithms II: Abstract State Machines and the Characterization Theorem. Logical Methods in Computer Science 3(4), 2007, paper 4.
160:
335:
N. Dershowitz and Y. Gurevich. A natural axiomatization of computability and proof of Church’s Thesis. Bulletin of
Symbolic Logic 14:3, 2008, 299-350.
383:
A. Blass, Y. Gurevich, M. Moskal, and I. Neeman. Evidential authorization. In S. Nanz (ed), The Future of
Software Engineering, Springer 2011, 77–99.
314:
Y. Gurevich. Evolving
Algebra 1993: Lipari Guide. In E. Börger (ed.), Specification and Validation Methods, Oxford University Press, 1995, 9–36.
24:
462:
326:
Y. Gurevich. Sequential
Abstract State Machines capture sequential algorithms. ACM Transactions on Computational Logic 1(1), 2000.
269:
Y. Gurevich. Monadic second-order theories. In J. Barwise and S. Feferman (eds.), Model-Theoretic Logics, Springer, 1985, 479-506.
568:
287:
Y. Gurevich and S. Shelah. Expected computation time for Hamiltonian Path Problem. SIAM Journal on Computing 16:3, 1987, 486-502.
455:
573:
543:
240:
219:
Blass, Andreas; Dershowitz, Nachum; Reisig, Wolfgang (2010), Blass, Andreas; Dershowitz, Nachum; Reisig, Wolfgang (eds.),
439:
227:, Lecture Notes in Computer Science, vol. 6300, Berlin, Heidelberg: Springer Berlin Heidelberg, pp. 1–48,
435:
423:
553:
523:
563:
88:
558:
82:
477:
414:. Efficient decomposition of single-qubit gates into V basis circuits. Physical Review A 88:1, 2013.
401:
Y. Gurevich, E. Hudis, and J.M. Wing. Inverse privacy. Communications of the ACM 59(7), 2016, 38-42.
296:
Y. Gurevich. Average case completeness. Journal of Computer and System Sciences 42:3, 1991, 346-398.
122:
55:
538:
107:
43:
192:
168:
8:
111:
494:
220:
184:
129:
85:
47:
39:
519:
260:
E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer, 1997.
370:
236:
176:
153:
137:
498:
451:
486:
357:
228:
103:
19:
459:
132:
where he founded a group on Foundations of Software Engineering. The group built
232:
475:"EATCS names 2014 fellows", Milestones: Computer Science Awards, Appointments,
145:
96:
78:
28:
532:
344:
180:
133:
70:
51:
136:
based on the theory of abstract state machines. The tool was adopted by the
411:
62:
164:
514:
141:
118:
490:
315:
188:
117:
Most importantly, he became interested in the problem of what an
196:
66:
73:
in 1982. The best-known work of his Soviet period is on the
549:
1997 fellows of the Association for Computing Machinery
156:, while continuing research in his traditional areas.
218:
173:
European Association for Theoretical Computer Science
530:
140:team; a modified version of the tool helped
356:A. Blass, Y. Gurevich, D. Rosenzweig, and
65:. He taught mathematics there and then in
463:John Simon Guggenheim Memorial Foundation
18:
531:
214:
212:
61:Gurevich was born and educated in the
128:From 1998 to 2018, Gurevich was with
440:Association for Computing Machinery
221:"Yuri, Logic, and Computer Science"
209:
102:From 1982 to 1998, Gurevich taught
13:
121:is. This led him to the theory of
77:. In Israel, Gurevich worked with
14:
585:
508:
316:https://arxiv.org/abs/1808.06255
468:
445:
429:
417:
404:
395:
386:
377:
363:
350:
338:
329:
225:Fields of Logic and Computation
569:University of Michigan faculty
410:A. Bocharov, Y. Gurevich, and
320:
308:
299:
290:
281:
272:
263:
254:
1:
524:Mathematics Genealogy Project
465:. Accessed February 16, 2010.
442:. Accessed February 16, 2010.
202:
171:, an inaugural fellow of the
93:Forgetful Determinacy Theorem
574:Members of Academia Europaea
544:American computer scientists
426:, retrieved on Jan 11, 2021.
7:
233:10.1007/978-3-642-15025-8_1
99:is of that period as well.
27:in May 2004, photograph by
16:American computer scientist
10:
590:
75:classical decision problem
478:Communications of the ACM
485:(1): 24, January 2015,
123:abstract state machines
56:abstract state machines
458:June 22, 2011, at the
108:University of Michigan
44:University of Michigan
32:
554:Formal methods people
193:Ural State University
69:before moving to the
22:
54:and the inventor of
564:Microsoft employees
515:Gurevich's Homepage
159:Gurevich is a 2020
112:finite model theory
185:Hasselt University
130:Microsoft Research
48:computer scientist
40:Professor Emeritus
33:
559:Russian inventors
242:978-3-642-15024-1
177:Academia Europaea
169:Guggenheim Fellow
154:quantum computing
46:, is an American
23:Yuri Gurevich at
581:
502:
501:
472:
466:
449:
443:
433:
427:
421:
415:
408:
402:
399:
393:
390:
384:
381:
375:
374:
371:"Google Patents"
367:
361:
354:
348:
342:
336:
333:
327:
324:
318:
312:
306:
303:
297:
294:
288:
285:
279:
276:
270:
267:
261:
258:
252:
251:
250:
249:
216:
104:computer science
589:
588:
584:
583:
582:
580:
579:
578:
529:
528:
511:
506:
505:
491:10.1145/2686734
474:
473:
469:
460:Wayback Machine
450:
446:
434:
430:
422:
418:
409:
405:
400:
396:
391:
387:
382:
378:
369:
368:
364:
355:
351:
343:
339:
334:
330:
325:
321:
313:
309:
304:
300:
295:
291:
286:
282:
277:
273:
268:
264:
259:
255:
247:
245:
243:
217:
210:
205:
163:Fellow, a 1997
17:
12:
11:
5:
587:
577:
576:
571:
566:
561:
556:
551:
546:
541:
527:
526:
517:
510:
509:External links
507:
504:
503:
467:
444:
428:
416:
403:
394:
385:
376:
362:
349:
337:
328:
319:
307:
298:
289:
280:
271:
262:
253:
241:
207:
206:
204:
201:
175:, a member of
146:European Union
79:Saharon Shelah
29:Bertrand Meyer
15:
9:
6:
4:
3:
2:
586:
575:
572:
570:
567:
565:
562:
560:
557:
555:
552:
550:
547:
545:
542:
540:
539:Living people
537:
536:
534:
525:
521:
520:Yuri Gurevich
518:
516:
513:
512:
500:
496:
492:
488:
484:
480:
479:
471:
464:
461:
457:
453:
448:
441:
437:
432:
425:
420:
413:
407:
398:
389:
380:
372:
366:
359:
353:
346:
341:
332:
323:
317:
311:
302:
293:
284:
275:
266:
257:
244:
238:
234:
230:
226:
222:
215:
213:
208:
200:
198:
194:
190:
186:
182:
181:Honoris Causa
178:
174:
170:
166:
162:
157:
155:
150:
147:
143:
139:
135:
134:Spec Explorer
131:
126:
124:
120:
115:
113:
109:
105:
100:
98:
94:
90:
87:
84:
80:
76:
72:
71:United States
68:
64:
59:
57:
53:
52:mathematician
49:
45:
41:
37:
36:Yuri Gurevich
30:
26:
21:
482:
476:
470:
452:Fellows List
447:
431:
424:AAAS Fellows
419:
406:
397:
388:
379:
365:
352:
340:
331:
322:
310:
301:
292:
283:
274:
265:
256:
246:, retrieved
224:
158:
151:
127:
116:
101:
95:of Gurevich–
92:
86:second-order
74:
63:Soviet Union
60:
35:
34:
436:ACM Fellows
533:Categories
412:K.M. Svore
358:B. Rossman
248:2023-07-05
203:References
179:, and Dr.
165:ACM Fellow
97:Harrington
25:ETH Zurich
167:, a 1995
144:meet the
142:Microsoft
119:algorithm
499:11485095
456:Archived
345:A. Blass
89:theories
191:and of
189:Belgium
138:Windows
106:at the
83:monadic
42:at the
497:
239:
197:Russia
91:. The
67:Israel
495:S2CID
237:ISBN
161:AAAS
50:and
487:doi
229:doi
195:in
187:in
183:of
81:on
535::
522:,
493:,
483:58
481:,
454:,
438:,
235:,
223:,
211:^
199:.
114:.
58:.
38:,
489::
373:.
231::
31:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.