Entry Hentenryck: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{Hentenryck: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",
  DOI =          "http://doi.acm.org/10.1145/178243.178488",
  ISSN =         "0362-1340 (print), 1523-2867 (print), 1558-1160 (electronic)",
  ISSN-L =       "0362-1340",
  bibdate =      "Wed Jun 18 16:26:55 MDT 2008",
  bibsource =    "http://portal.acm.org/",
  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(RLin) 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,
}

Related entries