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

Programming Systems Lab,

Universität des Saarlandes

Member of the Graduierten-

kolleg Leistungsgarantien für

Computersysteme, funded by

DFG German Science Foun-

dation doctoral fellowship

Main Page




The Game Go

``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.

Postscript File

BibTeX Entry

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.

Postscript File

BibTeX Entry

New Version (fit to 11+2 pages):

Postscript File

BibTeX Entry

News of research

Announcement of a talk at the Workshop CCL'99 in France:

Plan of the Talk

Entailment von nicht-strukturellen Teiltyp-Constraints (2000)