Automatic synthesis of optimal-size concentrators by answer set programming. (English) Zbl 1491.68069

Balduccini, Marcello (ed.) et al., Logic programming and nonmonotonic reasoning. 14th international conference, LPNMR 2017, Espoo, Finland, July 3–6, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10377, 279-285 (2017).
Summary: A concentrator is a circuit with \(N\) inputs and \(M\leq N\) outputs that can route any given subset of \(K\leq M\) valid inputs to \(K\) of its \(M\) outputs. Concentrator circuits are important building blocks of many parallel algorithms. The design of optimal concentrator circuits is however a challenging task that has already been considered in many research papers. In this paper, we show how answer set programming can be used to automatically generate concentrator circuits of provably optimal size.
For the entire collection see [Zbl 1367.68005].


68Q06 Networks and circuits as models of computation; circuit complexity
68N17 Logic programming
68W10 Parallel algorithms in computer science


Full Text: DOI