If you can read this, your browser provides insufficient
support for style sheets. The visual presentation of this document will
suffer.

Tim Priesnitz

Ph.D. student at the

Member of the Graduierten-

kolleg Leistungsgarantien für

Computersysteme, funded by

DFG German Science Foun-

dation doctoral fellowship

Publications

``I was gratified to be able

to answer promptly, and I

did. I said I didn't known.''

Mark Twain

## An Introduction to Modal Logic (1997)Modal logic is used in numerous areas of computer science. You can see it as the logic of necessity and possibility. On the one hand modal logic is a fragment of first-order logic, on the other hand having a look at frames it is more powerfull. In this issue we discuss propositional modal logic, an extension of classical logic.
## Entailment of Non-Structural Subtyping Constraints (1999)Entailment of subtyping constraints was introduced for constraint simplification in subtype inference systems. Designing an efficient algorithm for subtype entailment turned out to be surprisingly difficult. The situation was clarified by Rehof and Henglein who proved entailment of structural subtyping constraints to be coNP-complete for simple types and PSPACE-complete for recursive types. For entailment of non-structural subtyping constraints of both simple and recursive types they proved PSPACE-hardness and conjectured PSPACE-completeness but failed in finding a complete algorithm. In this paper, we investigate the source of complications and isolate a natural subproblem of non-structural subtype entailment that we prove PSPACE-complete. We conjecture (but this is left open) that the presented approach can be extended to the general case.
## Entailment von nicht-strukturellen Teiltyp-Constraints (2000) |