Accession Number:

ADA278653

Title:

A Lower Bound for the Intersection of Regular Forests

Descriptive Note:

Final rept. Oct 1992-Sep 1993

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Volpano, Dennis M.

Report Date:

1993-10-05

Pagination or Media Count:

14.0

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.

Descriptors:

• *PROGRAMMING LANGUAGES
• *FORESTS
• COMPUTER PROGRAMMING
• SEQUENCES
• AUTOMATA
• GRAMMARS
• TREES
• LOGIC

Subject Categories:

• Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE