Dexter Kozen
Dexter Campbell Kozen (* 20. Dezember 1951) ist ein US-amerikanischer theoretischer Informatiker.
Kozen studierte am Dartmouth College mit dem Bachelor-Abschluss in Mathematik summa cum laude 1974 und wurde 1977 bei Juris Hartmanis an der Cornell University in Informatik promoviert (Complexity of finitely presented algebras)[1]. Als Postdoktorand war er an der University of California, Berkeley und danach ab 1978 Wissenschaftler bei IBM Research in Yorktown Heights. 1981/82 war er Gastprofessor an der Universität Aarhus (und nochmals 1991/92) und 1984/85 Adjunct Professor an der Columbia University. Ab 1985 war er Associate Professor und ab 1989 Professor für Informatik an der Cornell University (seit 1994 als Joseph Newton Pew Professor).
Kozen befasst sich mit Komplexitätstheorie, speziell von Entscheidungsproblemen in Algebra und Logik, mit Logik und Semantik von Programmiersprachen und Computersicherheit.
Er leistete Beiträge zur Modallogik und ist mit Dana Scott und Jaco de Bakker Begründer des modalen -Kalküls und einer der Begründer der Dynamischen Logik (mit David Harel).
1976 führte er den Begriff der alternierenden Turingmaschine ein, unabhängig von Ashok Chandra und Larry Stockmeyer. Er war ein Pionier in probabilistischer Semantik und befasste sich mit maßtheoretischer Semantik für probabilistische Programme und arbeitete über Kleene-Algebren.
1989 fand er mit Susan Landau einen Algorithmus zur Kompositions-Zerlegung von Polynomen (das heißt Auflösung von h=g(f), mit g, f, Polynomen höheren als ersten Grades und h der Komposition aus den gesuchten g und f), der in polynomialer Zeit erfolgreich war.
Er ist Fellow der Association for Computing Machinery (ACM) und der American Association for the Advancement of Science und war 1991 Guggenheim Fellow. 1980 erhielt er den Outstanding Innovation Award von IBM (für die Arbeit zur Alternierung mit Ashok Chandra und Larry Stockmeyer). 2016 erhielt er den EATCS-Award und den W. Wallace McDowell Award.
Schriften
- On parallelism in Turing machines, Proc. 17. Symp. Found. Comput. Sci. (FOCS), 1976, S. 89–97
- mit Ashok Chandra, Larry Stockmeyer: Alternation, J. ACM, Band 28, 1981, S. 114–133
- Semantics of probabilistic programs, J. Comp. Syst. Sci., Band 22, 1981, S. 328–350
- mit Rohit Parikh: An elementary proof of the completeness of PDL, Theoretical Computer Science, Band 14, 1981, S. 113–118
- Results on the Propositional μ-Calculus, Theoretical Computer Science, Band 27, 1983, S. 333–354.
- mit Susan Landau: Polynomial Decomposition Algorithms, Journal of Symbolic Computation, Band 7, 1989, S. 445–456
- mit Jerzy Tiuryn: Logics of programs, in: J. van Leeuwen, Handbook of Theoretical Computer Science, Band B, North Holland 1990, S. 789–840
- mit David Harel, Jerzy Tiuryn: Dynamic Logic, MIT Press 2000
- mit David Harel, Jerzy Tiuryn: Dynamic Logic, in: D. M. Gabbay, F. Guenther, Handbook of Philosophical Logic, Band 4, Kluwer 2002, S. 99–217
- Theory of Computation, Springer 2006