A Lower Bound for the Intersection of Regular Forests

Abstract

Regular Sigma X-forests continue to play an important role in programming languages, specifically in the design of type systems. They arise naturally as terms of constructor-based, recursive data types in logic and functional languages. Deciding whether the intersection of a sequence of regular Sigma X-forests is nonempty is an important problem in type inference. We show that this problem is PSPACE-hard and as a corollary that the problem of constructing a regular Sigma X-grammar representing their intersection is PSPACE-hard.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 05, 1993
Accession Number
ADA278653

Entities

People

  • Dennis M. Volpano

Organizations

  • Naval Postgraduate School

Tags

DTIC Thesaurus Topics

  • Alphabets
  • Automata
  • California
  • Classification
  • Computational Complexity
  • Computations
  • Computer Programming
  • Computer Science
  • Computers
  • Grammars
  • Language
  • Military Research
  • Notation
  • Programming Languages
  • Security
  • Sequences
  • Theoretical Computer Science

Readers

  • Artificial Intelligence
  • Graph Algorithms and Convex Optimization.

Technology Areas

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