Dexter Kozen
Dexter Campbell Kozen (né le ) est un informaticien théoricien américain. Il travaille en théorie de la complexité, plus particulièrement sur des problèmes de décision en algèbre et en logique, en sémantique des langages de programmation et en sécurité informatique.
| Naissance | |
|---|---|
| Nationalité | |
| Formation | |
| Activité |
| A travaillé pour | |
|---|---|
| Directeur de thèse | |
| Distinctions | Liste détaillée Prix EATCS () W. Wallace McDowell Award (en) () Membre de l'AAAS ACM Fellow Bourse Guggenheim |
Carrière
Kozen étudie au Dartmouth College et obtient un bachelor de mathématique 1974, et en 1976 il obtient un Ph. D. en informatique sous la direction de Juris Hartmanis à l'université Cornell (« Complexity of finitely presented algebras »)[1].
Il travaille comme chercheur postdoctoral à l'université de Californie à Berkeley et ensuite, à partir de 1978, comme chercheur au centre IBM Research à Yorktown Heights. En 1981-82, il est professeur invité à l'université d'Aarhus (et une deuxième fois en 1991-92) et en 1984-85, il est « Adjunct Professor » à l'Université Columbia. À partir de 1985 il est professeur associé, puis en 1989 il devient professeur d'informatique à l'université Cornell, où il est depuis 1994 titulaire de la chaire Joseph Newton Pew.
Recherche
Kozen travaille en théorie de la complexité, plus particulièrement sur des problèmes de décision en algèbre et en logique, en sémantique des langages de programmation et en sécurité informatique. Il travaille en logique modale : avec Dana Scott et Jaco de Bakker, il est le fondateur du μ-calcul modal et un des créateurs de la logique dynamique avec David Harel.
En 1976 il introduit, indépendamment de Ashok Chandra et Larry Stockmeyer mais en même temps qu'eux, la notion de machine de Turing alternante, dont les trois auteurs font un exposé de référence quelques années plus tard dans le Journal de l'ACM. Il est un des pionniers de la sémantique probabiliste, et travaille sur la théorie de la mesure de la sémantique de programmes probabilistes. Il a des contributions importantes sur les algèbres de Kleene.
En 1989, il décrit, avec Susan Landau, un algorithme en temps polynomial pour la décomposition de polynôme (au sens de la représentation d'un polynôme p sous la forme p = g(f), où g et f sont des polynômes de degré plus grand que 1).
Dexter Kozen est auteur de plusieurs manuels d'enseignement en informatique théorique. Son spectre d'activités et ses intérêts multiples se reflètent aussi dans la variété des coauteurs de ses travaux : DBLP lui attribue 96 coauteurs différents. Il a également encadré une vingtaine des thèses de Ph. D.
Prix et distinctions
Kozen est Fellow de l'Association for Computing Machinery (ACM) et de l'Association américaine pour l'avancement des sciences. En 1991, il est Guggenheim Fellow. En 1980, il reçoit le « Outstanding Innovation Award » d'IBM pour son travail sur l'alternation, avec Ashok Chandra et Larry Stockmeyer. En 2016, il est récipiendaire du prix EATCS.
Publications (sélection)
- Articles
- « On parallelism in Turing machines », dans Proc. 17. Symp. Found. Comput. Sci. (FOCS), , p. 89-97
- (avec Ashok Chandra et Larry Stockmeyer), « Alternation », Journal of the ACM, vol. 28,‎ , p. 114-133
- « Semantics of probabilistic programs », J. Comp. Syst. Sci., vol. 22,‎ , p. 328-350
- (avec Rohit Parikh), « An elementary proof of the completeness of PDL », Theoretical Computer Science, vol. 14,‎ 1981 pages= 113-118
- « Results on the Propositional μ-Calculus », Theoretical Computer Science, vol. 27,‎ , p. 333–354.
- (avec Susan Landau), « Polynomial Decomposition Algorithms », Journal of Symbolic Computation, vol. 7,‎ , p. 445–456.
- « On Kleene algebras and closed semirings », dans B. Rovan (éditeur), Proc. Math. Found. Comput. Sci., Springer, coll. « Lecture Notes in Computer Science » (no 452), (lire en ligne), p. 26-47.
- Textes de synthèse
- (avec Jerzy Tiuryn), « Logics of programs », dans J. van Leeuwen (éditeur), Handbook of Theoretical Computer Science, vol. B, North Holland, , p. 789-840
- (avec David Harel et Jerzy Tiuryn), « Dynamic Logic », dans D. M. Gabbay, F. Guenther (éditeurs), Handbook of Philosophical Logic, vol. 4, Kluwer, , p. 99-217
- (avec David Harel et Jerzy Tiuryn), Dynamic Logic, Cambridge, Londres, The MIT Press, coll. « Foundation of Computing », (ISBN 0-262-08289-6)
- Livres d'enseignement
- (en) Theory of Computation, Londres, Springer, coll. « Texts in Computer Science », , xiii+419 (ISBN 978-1-84628-297-3, lire en ligne)
- Automata and computability, Springer, coll. « Undergraduate texts in computer science », , xiii +400 (ISBN 978-0-387-94907-9, lire en ligne)
- Design and Analysis of Algorithms, Springer, coll. « Texts and Monographs in Computer Science », , x+320 (ISBN 978-3-540-97687-5)
Notes et références
- (en) « Dexter Campbell Kozen », sur le site du Mathematics Genealogy Project