ISSN:
1573-7640
Keywords:
Layered streams
;
logic programming
;
constraints
;
complexity
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
Notes:
Abstract A layered stream is a list of data structuresH*Ts whereTs is a layered stream containing all possible tails for headH. One performance advantage is the ability toeagerly construct a partial solution by binding headH before the tailsTs are known. This increases potential parallelism. A disadvantage of this facility is that eagerly bindingH can cause consumers of the layered stream to do extra computation if in factTs isuncompletable. In addition, the layered streams can grow very large, the bulk of which is garbage. To combat this space inefficiency, eager term construction can be restricted, thereby reducing parallelism. In this paper we show the trade-offs between potential parallelism, execution time, space and time complexity, for a group of benchmarks implemented with layered streams and streams. We also compare these algorithms to the related paradigms of candidates/noncandidates and fused generate & test.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01397626
Permalink