NDLI: Backtracking without trailing in CLP $(R

Please wait, while we are loading the content...

Is continuation-passing useful for data flow analysis?

Separate compilation for Standard ML

Lazy functional state threads

VLIW compilation techniques in a superscalar environment

Link-time optimization of address calculation on a 64-bit architecture

Division by invariant integers using multiplication

Precise compile-time performance prediction for superscalar-based computers

Accurate static estimators for program optimization

Improving semi-static branch prediction by code replication

GIVE-N-TAKE—a balanced code placement framework

Counting solutions to Presburger formulas: how and why

Parallelizing complex scans and reductions

Partial dead code elimination

Effective partial redundancy elimination

The program structure tree: computing control regions in linear time

Memory access coalescing: a technique for eliminating redundant memory accesses

ATOM: a system for building customized program analysis tools

Cache performance of garbage-collected programs

A general data dependence test for dynamic, pointer-based data structures

Interprocedural may-alias analysis for pointers: beyond k-limiting

Context-sensitive interprocedural points-to analysis in the presence of function pointers

Zero-cost range splitting

Debugging of globally optimized programs using data flow analysis

Efficient detection of all pointer and array access errors

On slicing programs with jump statements

Optimal tracing and incremental reexecution for debugging long-running programs

Optimizing dynamically-dispatched calls with run-time type feedback

Type analysis of Prolog using type graphs

Backtracking without trailing in CLP $(R_{Lin})$

Content Provider	ACM Digital Library
Author	Van Hentenryck, Pascal Ramachandran, Viswanath
Abstract	Constraint logic programming (CLP) is a generalization of logicprogramming where unification is replaced by constraint solving as thebasic operation of the language. The combination of constraint solvingand nondeterminism (approximated by backtracking) makes these languagesappealing for a variety of combinatorial search problems. Existing CLPlanguages support backtracking by generalizing traditional Prologimplementations: modifications to the constraint system are trailed andrestored on backtracking. Although simple and efficient, trailing may bevery demanding in memory space, since the constraint system maypotentially be saved at each choice point. This paper proposes afundamentally new implementation scheme for backtracking inCLP languages over linear (rational or real) arithmetic. The newscheme, 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 CLPsystem CLP(RLin) and compared analytically and experimentally withan optimized trailing implementation. Experimental results indicate that semantic backtracking produces significant reduction in memory space, while keeping the time overhead reasonably small.
Starting Page	349
Ending Page	360
Page Count	12
File Format	PDF
ISBN	089791662X
DOI	10.1145/178243.178488
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1994-08-01
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Backtracking without trailing in CLP $(R_{Lin})$

Backtracking without trailing in CLP ( RLin )

Backtracking without Trailing inCI..P(!RL~n)

Backtracking without Trailing in ... (1994)

Building a backtracking facility in smalltalk without kernel support

$R_b$ and $R_{\ell}$ in MSSM without $R$-parity

A metalevel compiler of clp(fd) and its combination with intelligent backtracking.

Choices without Backtracking

Solving Fuzzy Temporal Problems Without Backtracking

Backtracking without trailing in CLP $(R_{Lin})$

Similar Documents

Backtracking without trailing in CLP $(R_{Lin})$

Backtracking without trailing in CLP ( RLin )

Backtracking without Trailing inCI..P(!RL~n)

Backtracking without Trailing in ... (1994)

Building a backtracking facility in smalltalk without kernel support

$R_b$ and $R_{\ell}$ in MSSM without $R$-parity

A metalevel compiler of clp(fd) and its combination with intelligent backtracking.

Choices without Backtracking

Solving Fuzzy Temporal Problems Without Backtracking

Backtracking without trailing in CLP $(R_{Lin})$