A lower bound for the intersection of regular forests
Volpano, Dennis M.
MetadataShow full item record
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.
Approved for public release; distribution is unlimited.
NPS Report NumberNPS-CS-94-005
Showing items related by title, author, creator and subject.
New motion planning and real-time localization methods using proximity for autonomous mobile robots Wahdan, Mahmoud A. (Monterey, California. Naval Postgraduate School, 1996-09);One of the most difficult theoretical problems in robotics--motion planning for rigid body robots-- must be solved before a robot can perform real- world tasks such as mine searching and processing. This dissertation ...
Design of an elevated roadway for relief of traffic congestion at intersection of River and Federal streets, Troy, N.Y. Manley, Robert Burleigh; Manley, Robert Burleigh (Rensselaer Polytechnic Institute, 1948-06);The purpose of this thesis is to analyze the traffic problem at the intersection of River and Federal Streets and the Troy terminus of the Green Island Bridge, and to present the design which I believe to be the most ...
Cornett, Annette P. (Monterey, California. Naval Postgraduate School, 1993-06);Multigrid methods were developed to solve partial differential equations. Research has shown that these methods are applicable to a broader range of problems. This thesis investigates the application of multigrid techniques ...