Hostname: page-component-7c8c6479df-94d59 Total loading time: 0 Render date: 2024-03-27T16:11:54.023Z Has data issue: false hasContentIssue false

Improving intervals1

Published online by Cambridge University Press:  07 November 2008

W. Ken Jackson
Affiliation:
School of Computing Science, Simon Fraser University, Burnaby, British Columbia, CanadaV5A 1S6 (e-mail: jackson@cs.sfu.ca)
F. Warren Burton
Affiliation:
School of Computing Science, Simon Fraser University, Burnaby, British Columbia, CanadaV5A 1S6 (e-mail: jackson@cs.sfu.ca)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We show how improving values (Burton, 1991) can be extended to handle both upper and lower bounds. The result is a new data type, called improving intervals. We give a simple implementation of improving intervals that uses a list of successively tighter bounds to represent a value. A program using improving intervals can be evaluated as a parallel program using speculative evaluation. The utility of improving intervals is demonstrated through two programs: parallel alpha-beta and parallel branch-and-bound

Type
Articles
Copyright
Copyright © Cambridge University Press 1993

References

Akl, S., Barnard, D. and Doran, R. 1982. Design, analysis and implementation of a parallel tree search algorithm. IEEE Trans. Pattern Analysis & Machine Intelligence, 4(2): 192203.CrossRefGoogle ScholarPubMed
Bird, R. and Wadler, P. 1988. Introduction to Functional Programming. Prentice Hall.Google Scholar
Bird, R. S. and Hughes, J. 1987. The alpha-beta algorithm: An exercise in program transformation. Inf. Process. Lett., 24: 5357.CrossRefGoogle Scholar
Burton, F. W. 1985. Speculative computation, parallelism, and functional programming. IEEE Trans. Comput., 34(12): 11901193.CrossRefGoogle Scholar
Burton, F. W. 1991. Encapsulating nondeterminacy in an abstract data type with deterministic semantics. J. Functional Programming. 1(1): 320.CrossRefGoogle Scholar
Burton, F. W. and Jackson, W. K. 1990. Partially deterministic functions. IV Higher Order Workshop, Springer-Verlag Workshops in Computing, pp 110, Banff, Canada101409, Graham, Birtwistle (Ed.).Google Scholar
Hughes, J. 1989. Why functional programming matters. Comput. J., 32(2): 98107.CrossRefGoogle Scholar
Lai, T.-H. and Sahni, S. 1984. Anomalies in parallel branch-and-bound algorithms. Commun. ACM, 27(6): 594602.CrossRefGoogle Scholar
Li, G.-J. and Wah, B. W. 1990. Computational efficiency of parallel combinatorial or-tree searches. IEEE Trans. Softw. Eng., 16(1): 1331.Google Scholar
Powley, C., Ferguson, C. and Korf, R. E. 1989. Parallel heuristic search: Two approaches. In Kumar, V., Gopalakrishnan, P. and Kanal, L. N., editors, Parallel Algorithms for Machine Intelligence and Vision, pp. 4265. Springer-Verlag.Google Scholar
Turner, D. A. 1986. An overview of Miranda. SIGPLAN Notices, 21(12): 158166.CrossRefGoogle Scholar
Submit a response

Discussions

No Discussions have been published for this article.