English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

Directional Type Inference for Logic Programs

MPS-Authors
/persons/resource/persons44232

Charatonik,  Witold
Programming Logics, MPI for Informatics, Max Planck Society;

/persons/resource/persons45201

Podelski,  Andreas
Programming Logics, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

Charatonik, W., & Podelski, A. (1998). Directional Type Inference for Logic Programs. In G. Levi (Ed.), Proceedings of the 5th International Symposium in Static Analysis (SAS-98) (pp. 278-294). Berlin, Germany: Springer.


Cite as: https://hdl.handle.net/11858/00-001M-0000-000F-382C-5
Abstract
We follow the set-based approach to directional types proposed by Aiken and Lakshman$\:$\cite{AikenL:sas94}. Their type \emph{checking} algorithm works via set constraint solving and is sound and complete for given discriminative types. We characterize directional types in model-theoretic terms. We present an algorithm for \emph{inferring} directional types. The directional type that we derive from a logic program~$\P$ is uniformly at least as precise as any discriminative directional type of~$\P$, i.e., any directional type out of the class for which the type {\em checking\/} algorithm of Aiken and Lakshman is sound and complete. We improve their algorithm as well as their lower bound and thereby settle the complexity (D{\footnotesize EXPTIME}-complete) of the corresponding problem.