A lower bound for the intersection of regular forests
Loading...
Authors
Volpano, Dennis M.
Subjects
Tree automata
Computational complexity
Computational complexity
Advisors
Date of Issue
1993-10
Date
1993-10
Publisher
Monterey, California. Naval Postgraduate School
Language
en_US
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.
Type
Technical Report
Description
Series/Report No
Department
Computer Science
Identifiers
NPS Report Number
NPS-CS-94-005
Sponsors
Funder
Format
9 p. ; 28 cm.
Citation
Distribution Statement
Approved for public release; distribution is unlimited.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.