Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-23T13:03:42.690Z Has data issue: false hasContentIssue false
  • English
  • Français

Algebras for combinatorial search

Part of: JFP Research Articles

Published online by Cambridge University Press:  01 July 2009

J. MICHAEL SPIVEY
J. MICHAEL SPIVEY*
Affiliation:
Oxford University Computing Laboratory, Wolfson Building, Parks Road, Oxford OX1 3QD, UK (e-mail: mike@comlab.ox.ac.uk)
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.

Combinatorial search strategies including depth-first, breadth-first and depth-bounded search are shown to be different implementations of a common algebraic specification that emphasizes the compositionality of the strategies. This specification is placed in a categorical setting that combines algebraic specifications and monads.

Type
Articles
Information
Journal of Functional Programming , Volume 19 , Issue 3-4 , July 2009 , pp. 469 - 487
Copyright
Copyright © Cambridge University Press 2009

References

Bird, R. S. (1987) An introduction to the theory of lists. In Calculi of Discrete Design, Broy, M. (ed.), NATO ASI Series F, vol. 36. Springer, pp. 5–42.Google Scholar
Gibbons, J. & Jones, G. (1998) The under-appreciated unfold. In Proceedings of the 3rd ACM SIGPLAN International Conference on Functional Programming, ICFP '98 (Baltimore, MD, Sept. 1998). ACM Press, pp. 273–279.Google Scholar
Hinze, R. (2001) Prolog's control constructs in a functional setting – axioms and implementation, Int. J. Found. Comput. Sci., 12 (2): 125–170.Google Scholar
Kiselyov, O., Shan, C.-C., Friedman, D. P. & Sabry, A. (2005) Backtracking, interleaving and terminating monad transformers, In Proceedings of the 10th ACM SIGPLAN International Conference on Functional Programming, ICFP '05 (Tallinn, Sept. 2005). ACM Press, pp. 192–203.Google Scholar
MacLane, S. (1971) Categories for the Working Mathematician, Graduate Texts in Mathematics, vol. 5. Springer.Google Scholar
Meertens, L. G. L. T. (1986) Algorithmics – towards programming as a mathematical activity. In Proceedings of the CWI Symposium on Mathematics and Computer Science, de Bakker, J., Hazewinkel, M. & Lenstra, J. K. (eds), CWI Monographs, vol. 1. CWI, pp. 289–334.Google Scholar
Russell, S. J. & Norvig, P. (2003) Artificial Intelligence: A Modern Approach, 2nd ed. Prentice Hall.Google Scholar
Spivey, J. M. (2000) Combinators for breadth-first search, J. Funct. Program., 10 (4): 397–408.CrossRefGoogle Scholar
Spivey, J. M. & Seres, S. (2003) Combinators for logic programming. In The Fun of Programming, Gibbons, J. & de Moor, O. (eds), Cornerstones of Computing. Palgrave MacMillan, pp. 177–200.CrossRefGoogle Scholar
Sutherland, W. A. (1975) Introduction to Metric and Topological Spaces. Oxford University Press.Google Scholar
Wand, M. & Vaillancourt, D. (2001) Relating models of backtracking. In Proceedings of the 9th International Conference on Functional Programming, ICFP '04 (Snowbird, UT, Sept. 2004). ACM Press, pp. 54–65.Google Scholar
Submit a response

Discussions

No Discussions have been published for this article.