Sergei A. Grechanik, Ilya G. Klyuchnikov, Sergei A. Romanenko. Staged multi-result supercompilation: filtering before producing. Keldysh Institute Preprints, (70), 2013.
URL: http://library.keldysh.ru/preprint.asp?lg=e&id=2013-70 Agda code: https://github.com/sergei-romanenko/staged-mrsc-agda 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. C.А. Гречаник, И.Г. Ключников, С.А. Романенко. Стадированная многорезультатная суперкомпиляция: фильтрация результатов до их порождения. В случае применения суперкомпиляции в области решения задач, многорезультатная суперкомпиляция позволяет обнаруживать наилучшие решения благодаря тому, что порождается некоторое множество возможных остаточных графов конфигураций, которое затем фильтруется в соответствии с некоторыми критериями. К сожалению, пространство поиска при этом может получаться весьма обширным. Однако, мы показываем, что можно значительно уменьшить объем поиска разложив процесс многорезультатной суперкомпиляции в композицию из двух стадий. На первой стадии порождается компактное представление множества остаточных графов, которое получается в результате задержки некоторых операций по построению графов. Эти операции выполняются на второй стадии, когда компактное представление интерпретируется, в результате чего и генерируется множество графов. Основная идея предлагаемого подхода состоит в том, что вместо фильтрации множества графов можно выполнять анализ и чистку его компактного представления. Во многих случаях, представляющих практический интерес (таких, как отбор графов минимального размера или отбрасывание графов, содержащих ненадежные конфигурации) чистка может быть выполнена за линейное время.
