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)
|