Nondeterministic Algorithms

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Nondeterministic Algorithms

Full text

Pdf (442 KB)

Source

Journal of the ACM (JACM) archive
Volume 14 , Issue 4 (October 1967) table of contents

Pages: 636 - 644

Year of Publication: 1967

ISSN:0004-5411

Author

Robert W. Floyd

Department of Computer Science, Carnegie Institute of Technology, Pittsburgh, Pennsylvania

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 31, Downloads (12 Months): 213, Citation Count: 63

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321420.321422 What is a DOI?

ABSTRACT

Programs to solve combinatorial search problems may often be simply written by using multiple-valued functions. Such programs, although impossible to execute directly on conventional computers, may be converted in a mechanical way into conventional backtracking programs. The process is illustrated with algorithms to find all solutions to the eight queens problem on the chessboard, and to find all simple cycles in a network.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	BALL, W.R. Mathematical Recreations and Essays (12th ed.). Macmillan, New York, 1947.
	2	FLOYD, R. W. The syntax of programming languages--a survey. IEEE Trans. EC-I3, 4 (Aug. 1964), 346-353.
	3	Solomon W. Golomb , Leonard D. Baumert, Backtrack Programming, Journal of the ACM (JACM), v.12 n.4, p.516-524, Oct. 1965 [doi>10.1145/321296.321300]
	4	Edgar T. Irons, A syntax directed compiler for ALGOL 60, Communications of the ACM, v.4 n.1, p.51-55, Jan. 1961 [doi>10.1145/366062.366083]

CITED BY 63

	Peter M. D. Gray , Suzanne M. Embury , Kit Y. Hui , Graham J. L. Kemp, The Evolving Role of Constraints in the Functional Data Model, Journal of Intelligent Information Systems, v.12 n.2-3, p.113-137, March 1999
	Jon Bentley , Bob Floyd, Programming pearls: a sample of brilliance, Communications of the ACM, v.30 n.9, p.754-757, Sept. 1987
	Burt M. Leavenoworth , Jean E. Sammet, An overview of nonprocedural languages, ACM SIGPLAN Notices, v.9 n.4, p.1-12, April 1974
	Jacques Cohen, A view of the origins and development of Prolog, Communications of the ACM, v.31 n.1, p.26-36, Jan. 1988
	James B. Morris, Jr. , Mark B. Wells, The specification of program flow in Madcap 6, Proceedings of the ACM annual conference, p.755-762, August 01-01, 1972, Boston, Massachusetts, United States
	Bruce Abramson , Mordechai M. Yung, Construction through decomposition: a divide-and-conquer algorithm for the N-queens problem, Proceedings of 1986 ACM Fall joint computer conference, p.620-628, November 1986, Dallas, Texas, United States
	Ralph E. Griswold, The Evaluation of Expressions in Icon, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.563-584, Oct. 1982
	Robert Kowalski, Algorithm = logic + control, Communications of the ACM, v.22 n.7, p.424-436, July 1979
	C. Montangero , G. Pacini , F. Turini, Two-level control structure for nondeterministic programming, Communications of the ACM, v.20 n.10, p.725-730, Oct. 1977
	Jacques Cohen, Non-Deterministic Algorithms, ACM Computing Surveys (CSUR), v.11 n.2, p.79-94, June 1979
	Daniel G. Bobrow, Requirements for advanced programming systems for list processing, Communications of the ACM, v.15 n.7, p.618-627, July 1972
	Michał Walicki , Sigurd Meldal, Algebraic approaches to nondeterminism—an overview, ACM Computing Surveys (CSUR), v.29 n.1, p.30-81, March 1997
	Ralph E. Griswold , David R. Hanson , John T. Korb, Generators in Icon, ACM Transactions on Programming Languages and Systems (TOPLAS), v.3 n.2, p.144-161, April 1981
	Ellis Horowitz, The art of the algorithmist, Proceedings of the annual conference, p.442-444, October 20-22, 1976, Houston, Texas, United States
	David R. Hanson, A procedure mechanism for backtrack programming, Proceedings of the annual conference, p.401-405, October 20-22, 1976, Houston, Texas, United States
	George B. Leeman, Jr., A formal approach to undo operations in programming languages, ACM Transactions on Programming Languages and Systems (TOPLAS), v.8 n.1, p.50-87, Jan. 1986
	Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973
	Cengiz Erbas , Seyed Sarkeshik , Murat M. Tanik, Different perspectives of the N-Queens problem, Proceedings of the 1992 ACM annual conference on Communications, p.99-108, March 03-05, 1992, Kansas City, Missouri, United States
	Guy Lewis Steele, Jr. , Gerald Jay Sussman, Constraints, ACM SIGAPL APL Quote Quad, v.9 n.4, p.208-225, June 1979
	Robert W. Lingard , David Wilczynski, A syntax directed approach for handling natural language relations, Proceedings of the ACM annual conference, p.118-128, August 01-01, 1972, Boston, Massachusetts, United States
	Albert L. Zobrist , Fredric R. Carlson, The USC chess program, Proceedings of the annual conference, p.209-212, August 27-29, 1973, Atlanta, Georgia, United States
	A. T. Berztiss, A Backtrack Procedure for Isomorphism of Directed Graphs, Journal of the ACM (JACM), v.20 n.3, p.365-377, July 1973
	Ch. Boitet , P. Chatelin , P. Daun Fraga, Present and future paradigms in the automatized translation of natural languages, Proceedings of the 8th conference on Computational linguistics, September 30-October 04, 1980, Tokyo, Japan
	Zohar Manna , Adi Shamir, The optimal fixedpoint of recursive programs, Proceedings of seventh annual ACM symposium on Theory of computing, p.194-206, May 05-07, 1975, Albuquerque, New Mexico, United States
	Gary Lindstrom, Backtracking in a Generalized Control Setting, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.1, p.8-26, July 1979
	Matthew M. Geller , Michael A. Harrison, Strict deterministic versus LR(0) parsing, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.22-32, October 01-03, 1973, Boston, Massachusetts
	B. M. Leavenworth, Programming with(out) the GOTO, Proceedings of the ACM annual conference, p.782-786, August 01-01, 1972, Boston, Massachusetts, United States
	Alain Colmerauer , Philippe Roussel, The birth of Prolog, ACM SIGPLAN Notices, v.28 n.3, p.37-52, March 1993
	Mordechai Ben-Ari , Zohar Manna , Amir Pnueli, The temporal logic of branching time, Proceedings of the 8th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.164-176, January 26-28, 1981, Williamsburg, Virginia
	Charles J. Prenner , Jay M. Spitzen , Ben Wegbreit, An implementation of backtracking for programming languages, ACM SIGPLAN Notices, v.7 n.11, November 1972
	Anthony I. Wasserman, Issues in programming language design: an overview, ACM SIGPLAN Notices, v.10 n.7, July 1975
	Barry K. Rosen, Note on semantics and optimization, ACM SIGPLAN Notices, v.9 n.11, November 1974
	Biographies, IEEE Annals of the History of Computing, v.26 n.2, p.75-83, April 2004
	B. M. Leavenworth, Programming with(out) the GOTO, ACM SIGPLAN Notices, v.7 n.11, November 1972
	C. A. R. Hoare, Some Properties of Predicate Transformers, Journal of the ACM (JACM), v.25 n.3, p.461-480, July 1978
	Gary Lindstrom, Control structure aptness: A case study using top-down parsing, Proceedings of the 3rd international conference on Software engineering, p.5-12, May 10-12, 1978, Atlanta, Georgia, United States
	John C. Reynolds, G/EDANKEN—a simple typeless language based on the principle of completeness and the reference concept, Communications of the ACM, v.13 n.5, p.308-319, May 1970
	Robert W. Floyd, The paradigms of programming, Communications of the ACM, v.22 n.8, p.455-460, Aug. 1979
	James B. Morris , Mark B. Wells, The specification of program flow in Madcap 6, ACM SIGPLAN Notices, v.7 n.11, November 1972
	David A. Fisher, A survey of control structures in programming languages, ACM SIGPLAN Notices, v.7 n.11, November 1972
	Tankut Akgul , Vincent J. Mooney III, Assembly instruction level reverse execution for debugging, ACM Transactions on Software Engineering and Methodology (TOSEM), v.13 n.2, p.149-198, April 2004
	Bernard Lang, Parallel non-deterministic bottom-up parsing, ACM SIGPLAN Notices, v.6 n.12, p.56-57, December 1971
	Mathew N. Matelan, MPACT: microprocessor application to control-firmware translator, ACM SIGDA Newsletter, v.5 n.1, p.13-41, March 1975
	T. E. Cheatham, Jr , Ben Wegbreit, A laboratory for the study of automating programming, ACM SIGSAM Bulletin
	Alain Colmerauer , Philippe Roussel, The birth of Prolog, History of programming languages---II, ACM Press, New York, NY, 1996
	Gary D. Knott, A proposal for certain process management and intercommunication primitives, ACM SIGOPS Operating Systems Review, v.8 n.4, p.7-44, October 1974
	Robert Glück , Masahiko Kawabe, Revisiting an automatic program inverter for Lisp, ACM SIGPLAN Notices, v.40 n.5, p.8-17, May 2005
	Juan Echagüe , Jesús Villadangos , Vicent Cholvi , Manuel Prieto, Transforming general networks into feed-forward by using turn-prohibition, Computer Communications, v.31 n.9, p.1824-1831, June, 2008
	Jack B. Dennis, Bibliography, Record of the Project MAC conference on concurrent systems and parallel computation, ACM, New York, NY, 1970
	Joan Boyar, Inferring sequences produced by pseudo-random number generators, Journal of the ACM (JACM), v.36 n.1, p.129-141, Jan. 1989
	Charles J. Prenner , Jay M. Spitzen , Ben Wegbreit, An implementation of backtracking for programming languages, Proceedings of the ACM annual conference, p.763-771, August 01-01, 1972, Boston, Massachusetts, United States
	Torben Ægidius Mogensen, Semi-inversion of functional parameters, Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation, January 07-08, 2008, San Francisco, California, USA
	Robert Glück , Masahiko Kawabe, A Method for Automatic Program Inversion Based on LR(0) Parsing, Fundamenta Informaticae, v.66 n.4, p.367-395, December 2005
	Dennis E. Hamilton, We have met the enemy and she is us: a mixup'd search for software engineering, ACM SIGSOFT Software Engineering Notes, v.6 n.2, p.18-22, April 1981
	Jacques Cohen, A tribute to Alain Colmerauer, Theory and Practice of Logic Programming, v.1 n.6, p.637-646, November 2001
	Robert W. Floyd, The paradigms of programming, ACM Turing award lectures, ACM, New York, NY, 2007
	T. E. Cheatham, Jr. , Ben Wegbreit, A laboratory for the study of automating programming, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada
	Anthony I. Wasserman, Issues in programming language design: an overview, Proceedings of the May 19-22, 1975, national computer conference and exposition, May 19-22, 1975, Anaheim, California
	Joseph M. Morris , Alexander Bunkenburg , Malcolm Tyrrell, Term transformers: A new approach to state, ACM Transactions on Programming Languages and Systems (TOPLAS), v.31 n.4, p.1-42, May 2009
	Daniel G. Bobrow , Ben Wegbreit, A model for control structures for artificial intelligence programming languages, Proceedings of the 3rd international joint conference on Artificial intelligence, p.246-253, August 20-23, 1973, Stanford, USA
	David Canfield Smith , Horace J. Enes, Backtracking in MLISP2: an efficient backtracking method for LISP, Proceedings of the 3rd international joint conference on Artificial intelligence, p.677-685, August 20-23, 1973, Stanford, USA
	Gregory Dean Gibbons, POPS: an application of heuristic search methods to the processing of a nondetermlnistic programming language, Proceedings of the 3rd international joint conference on Artificial intelligence, p.589-600, August 20-23, 1973, Stanford, USA
	Michal Armoni , Mordechai Ben-Ari, The concept of nondeterminism: its development and implications for teaching, ACM SIGCSE Bulletin, v.41 n.2, June 2009