Non-Deterministic Algorithms
- 1 June 1979
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 11 (2) , 79-94
- https://doi.org/10.1145/356770.356773
Abstract
Prnmtive commands representing the concepts of choice, failure, and success are used to describe non-deterministic algorithms for solving a variety of problems. First, the role of the primitives is explained in a manner appealing to the reader's intuition. Then, a solution to the classmal 8-queens problem is presented as a non-deterministic program, and its implementation is described. Two examples follow, showing the usefulness of the primitwes m computer-reded problem solving: the first is a simple question-answering program, the other is a parser for a context-sensitive language. Finally, a brief survey of current and related work is presented whmh includes: additmnal desLrable prumtives, implementation, correctness, efficiency, and theoretical implicatmnsKeywords
This publication has 15 references indexed in Scilit:
- Two-level control structure for nondeterministic programmingCommunications of the ACM, 1977
- Language facilities for programmable backtrackingACM SIGPLAN Notices, 1977
- Backtrack programming techniquesCommunications of the ACM, 1975
- Embedding non-determinismSoftware: Practice and Experience, 1975
- Estimating the efficiency of backtrack programsMathematics of Computation, 1975
- New Programming Languages for Artificial Intelligence ResearchACM Computing Surveys, 1974
- Non-deterministic FORTRANThe Computer Journal, 1974
- A model and stack implementation of multiple environmentsCommunications of the ACM, 1973
- Non-deterministic programmingBIT Numerical Mathematics, 1967
- Backtrack ProgrammingJournal of the ACM, 1965