Show simple item record

dc.contributor.authorVolpano, Dennis M.
dc.date1993-10
dc.date.accessioned2013-02-27T23:23:27Z
dc.date.available2013-02-27T23:23:27Z
dc.date.issued1993-10
dc.identifier.urihttp://hdl.handle.net/10945/28758
dc.descriptionApproved for public release; distribution is unlimited.en_US
dc.description.abstractRegular 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.en_US
dc.description.urihttp://archive.org/details/lowerboundforint00volp
dc.format.extent9 p. ; 28 cm.en_US
dc.language.isoen_US
dc.publisherMonterey, California. Naval Postgraduate Schoolen_US
dc.rightsThis publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. As such, it is in the public domain, and under the provisions of Title 17, United States Code, Section 105, may not be copyrighted.en_US
dc.subject.lcshFORESTSen_US
dc.titleA lower bound for the intersection of regular forestsen_US
dc.typeReporten_US
dc.contributor.corporateNaval Postgraduate School (U.S.)
dc.contributor.departmentComputer Science
dc.subject.authorTree automataen_US
dc.subject.authorComputational complexityen_US
dc.identifier.oclcocn640481857
dc.identifier.npsreportNPS-CS-94-005


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record