A lower bound for the intersection of regular forests
By: by Dennis M. Volpano
Contributors: Naval Postgraduate School (U.S.). Dept. of Computer Science
Publisher: Naval Postgraduate School; Available from National Technical Information Service
Published: 1993
Place of publication: Monterey, Calif; Springfield, Va
Language: eng
Subjects: FORESTS; PROGRAMMING LANGUAGES
Other titles: NPS-CS-94-005.
Description: 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.      Tree automata, Computational complexity.
Notes: Cover title.

"NPS-CS-94-005."

"October 1993."

AD A278 653.

Includes bibliographical references (p. 8-9)