Lower Bounds on Type Checking Overloading

Abstract

Smith has proposed an elegant extension of the ML type system for polymorphic functional languages with overloading. Type inference in his system requires solving a satisfiability problem that is undecidable if no restrictions are imposed on overloading. This short note explores the effect of recursion and the structure of type assumptions in overloadings on the problem's complexity.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 1996
Accession Number
ADA492255

Entities

People

  • Dennis M. Volpano

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Alphabets
  • Automata
  • Computational Complexity
  • Computer Architecture
  • Computer Programming
  • Computer Science
  • Computers
  • Hardness
  • Information Operations
  • Information Processing
  • Language
  • Machines
  • Materials
  • Programming Languages
  • Sequences

Fields of Study

  • Computer science

Readers

  • Computational Linguistics
  • Mathematical Modeling and Probability Theory.

Technology Areas

  • AI & ML
  • AI & ML - Machine Learning Algorithms
  • AI & ML - Neural Networks