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 ${\displaystyle \mu }$-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.