Dexter Kozen

from Wikipedia, the free encyclopedia

Dexter Campbell Kozen (born December 20, 1951 ) is an American theoretical computer scientist.

Kozen graduated from Dartmouth College with a bachelor's degree in mathematics summa cum laude in 1974 and received his doctorate in computer science under Juris Hartmanis at Cornell University in 1977 (Complexity of finitely presented algebras). He was a postdoctoral fellow at the University of California, Berkeley and then from 1978 a scientist at IBM Research in Yorktown Heights. In 1981/82 he was visiting professor at Aarhus University (and again in 1991/92) and in 1984/85 Adjunct Professor at Columbia University . From 1985 he was Associate Professor and from 1989 Professor of Computer Science at Cornell University (since 1994 as Joseph Newton Pew Professor).

Kozen deals with complexity theory , especially decision problems in algebra and logic, with logic and semantics of programming languages ​​and computer security.

He made contributions to modal logic and, together with Dana Scott and Jaco de Bakker, is the founder of the modal calculus and one of the founders of dynamic logic (with David Harel ).

In 1976 he introduced the concept of the alternating Turing machine , independently of Ashok Chandra and Larry Stockmeyer. He was a pioneer in probabilistic semantics and dealt with measure theoretical semantics for probabilistic programs and worked on Kleene algebras.

In 1989, together with Susan Landau, he found an algorithm for the compositional decomposition of polynomials (i.e. the resolution of h = g (f), with g, f, polynomials higher than the first degree and h of the composition from the sought g and f), which in polynomial time was successful.

He is a Fellow of the Association for Computing Machinery (ACM) and the American Association for the Advancement of Science, and was a Guggenheim Fellow in 1991 . In 1980 he received the Outstanding Innovation Award from IBM (for work on alternating with Ashok Chandra and Larry Stockmeyer). In 2016 he received the EATCS Award and the W. Wallace McDowell Award .

Fonts

  • On parallelism in Turing machines, Proc. 17. Symp. Found. Comput. Sci. (FOCS), 1976, pp. 89-97
  • with Ashok Chandra, Larry Stockmeyer: Alternation, J. ACM, Volume 28, 1981, pp. 114-133
  • Semantics of probabilistic programs, J. Comp. Syst. Sci., Vol. 22, 1981, pp. 328-350
  • with Rohit Parikh: An elementary proof of the completeness of PDL, Theoretical Computer Science, Volume 14, 1981, pp. 113-118
  • Results on the Propositional µ-Calculus, Theoretical Computer Science, Volume 27, 1983, pp. 333-354.
  • with Susan Landau: Polynomial Decomposition Algorithms, Journal of Symbolic Computation, Volume 7, 1989, pp. 445-456
  • with Jerzy Tiuryn : Logics of programs, in: J. van Leeuwen, Handbook of Theoretical Computer Science, Volume B, North Holland 1990, pp. 789-840
  • with David Harel , Jerzy Tiuryn: Dynamic Logic, MIT Press 2000
  • with David Harel, Jerzy Tiuryn: Dynamic Logic, in: DM Gabbay, F. Guenther, Handbook of Philosophical Logic, Volume 4, Kluwer 2002, pp. 99–217
  • Theory of Computation, Springer 2006

Web links

References and comments

  1. ↑ Dexter Kozen in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
personal data
SURNAME Kozen, Dexter
ALTERNATIVE NAMES Kozen, Dexter Campbell
BRIEF DESCRIPTION American computer scientist
DATE OF BIRTH December 20, 1951