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.
Zhan, J.; Maltz, D.; Zhang, H.; Greenberg, A.; Hjalmtysson, G.; Rexford, J.; Xie, Geoffrey (2005-03);The primary purpose of a network is to provide reachability between applications running on end hosts. In this paper, we describe how to compute the reachability a network provides from a snapshot of the configuration state ...
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 ...