I have known Dexter for 30 years, which, of course, means that I was 9 when I first met him. At that time, Dexter was already “the man”. Although he was only a few years ahead of me, he had already made his name by independently defining the notion of alternating Turing machines, a deep contribution to complexity theory that made it possible to connect time and space complexity. The results were viewed as so significant that it was already being taught in a graduate course on complexity theory that I attended. Of even more interest to me at the time was Dexter’s work on modal logic, since a large part of my thesis was on dynamic logic. Finding a sound and complete axiomatization for dynamic logic had been an open problem for many years. Krister Segerberg had suggested an obviously sound axiomatization, but couldn’t prove it complete. Rohit Parikh  showed that it was indeed complete, but his proof was rather complicated. Dexter then came up with a much simpler proof, one that got at the essence of Rohit’s ideas; this version was published as . The proof is truly beautiful. I have taught it often, and used the ideas in a number of subsequent papers (e.g., [3,4]).
Weitere Kapitel dieses Buchs durch Wischen aufrufen
Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten
Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:
- Dexter Kozen: An Appreciation
Joseph Y. Halpern
- Springer Berlin Heidelberg
Neuer Inhalt/© ITandMEDIA