KIAM Main page Web Library  •  Publication Searh  Русский 

KIAM Preprint № 70, Moscow, 2013
Authors: Grechanik S. A., Klyuchnikov I. G., Romanenko S. A.
Staged multi-result supercompilation: filtering before producing
When applying supercompilation to problem-solving, multi-result supercompilation enables us to find the best solutions by generating a set of possible residual graphs of configurations that are then filtered according to some criteria. Unfortunately, the search space may be rather large. However, we show that the search can be drastically reduced by decomposing multi-result supercompilation into two stages. The first stage produces a compact representation for the set of residual graphs by delaying some graph-building operation. These operations are performed at the second stage, when the representation is interpreted, to actually produce the set of graphs. The main idea of our approach is that, instead of filtering a collection of graphs, we can analyze and clean its compact representation. In some cases of practical importance (such as selecting graphs of minimal size and removing graphs containing unsafe configurations) cleaning can be performed in linear time.
Supercompilation, multi-result supercompilation, staging
Publication language: english,  pages: 28
Research direction:
Programming, parallel computing, multimedia
English source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
View statistics (updated once a day)
over the last 30 days — 4 (-1), total hit from 01.09.2019 — 101
About authors:
  • Grechanik Sergei Alexandrovich, RAS
  • Klyuchnikov Ilya Grigor'evich,  KIAM RAS
  • Romanenko Sergei Anatolievich, RAS