Entry VanHentenryck:1994:BTC from sigplan1990.bib

Last update: Thu Apr 12 03:37:15 MDT 2012                Valid HTML 3.2!

Index sections

Top | Symbols | Numbers | Math | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

BibTeX entry

@Article{VanHentenryck:1994:BTC,
  author =       "Pascal {Van Hentenryck} and Viswanath Ramachandran",
  title =        "Backtracking without trailing in {CLP($R_{\rm
                 Lin}$)}",
  journal =      j-SIGPLAN,
  volume =       "29",
  number =       "6",
  pages =        "349--360",
  month =        jun,
  year =         "1994",
  CODEN =        "SINODQ",
  ISBN =         "0-89791-598-4",
  ISBN-13 =      "978-0-89791-598-4",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Thu May 13 12:37:27 MDT 1999",
  bibsource =    "http://www.acm.org/pubs/contents/proceedings/pldi/178243/index.html",
  URL =          "http://www.acm.org:80/pubs/citations/proceedings/pldi/178243/p349-van_hentenryck/",
  abstract =     "Constraint logic programming (CLP) is a generalization
                 of logic programming where unification is replaced by
                 constraint solving as the basic operation of the
                 language. The combination of constraint solving and
                 nondeterminism (approximated by backtracking) makes
                 these languages appealing for a variety of
                 combinatorial search problems. Existing CLP languages
                 support backtracking by generalizing traditional Prolog
                 implementations: modifications to the constraint system
                 are trailed and restored on backtracking. Although
                 simple and efficient, trailing may be very demanding in
                 memory space, since the constraint system may
                 potentially be saved at each choice point. This paper
                 proposes a fundamentally new implementation scheme for
                 backtracking in CLP languages over linear (rational or
                 real) arithmetic. The new scheme, called semantic
                 backtracking, does not use trailing but rather exploits
                 the semantics of the constraints to undo the effect of
                 newly added constraints. Semantic backtracking reduces
                 the space complexity by an order of magnitude compared
                 to implementations based on trailing and makes space
                 complexity essentially independent of the number of
                 choice points. In addition, semantic backtracking
                 introduces negligible space and time overhead on
                 deterministic programs. The price for this improvement
                 is an increase in backtracking time, although
                 constraint-solving time may actually decrease. The
                 scheme has been implemented as part of a complete CLP
                 system CLP({\em R\/}{\em Lin\/}) and compared
                 analytically and experimentally with an optimized
                 trailing implementation. Experimental results indicate
                 that semantic backtracking produces significant
                 reduction in memory space, while keeping the time
                 overhead reasonably small.",
  acknowledgement = ack-nhfb,
  annote =       "Published as part of the Proceedings of PLDI'94.",
  classification = "C1160 (Combinatorial mathematics); C4240
                 (Programming and algorithm theory); C6110L (Logic
                 programming); C6140D (High level languages)",
  conflocation = "Orlando, FL, USA; 20-24 June 1994",
  conftitle =    "ACM SIGPLAN '94 Conference on Programming Language
                 Design and Implementation (PLDI)",
  corpsource =   "Brown Univ., Providence, RI, USA",
  keywords =     "algorithms; backtracking; CLP languages; combinatorial
                 search problems; computational complexity; constraint
                 handling; constraint logic programming; constraint
                 solving; deterministic programs; experimentation;
                 languages; logic programming languages; memory space;
                 nondeterminism; search problems; semantic backtracking;
                 semantic CLP languages; space complexity; trailing",
  sponsororg =   "ACM",
  subject =      "{\bf F.4.1} Theory of Computation, MATHEMATICAL LOGIC
                 AND FORMAL LANGUAGES, Mathematical Logic, Logic and
                 constraint programming. {\bf I.2.8} Computing
                 Methodologies, ARTIFICIAL INTELLIGENCE, Problem
                 Solving, Control Methods, and Search, Backtracking.
                 {\bf G.1.3} Mathematics of Computing, NUMERICAL
                 ANALYSIS, Numerical Linear Algebra, Linear systems
                 (direct and iterative methods).",
  treatment =    "P Practical",
}

Related entries