Dror Fried ; Axel Legay ; Joël Ouaknine ; Moshe Y. Vardi - Sequential Relational Decomposition

lmcs:5250 - Logical Methods in Computer Science, March 3, 2022, Volume 18, Issue 1 - https://doi.org/10.46298/lmcs-18(1:37)2022
Sequential Relational Decomposition

Authors: Dror Fried ; Axel Legay ; Joël Ouaknine ; Moshe Y. Vardi

    The concept of decomposition in computer science and engineering is considered a fundamental component of computational thinking and is prevalent in design of algorithms, software construction, hardware design, and more. We propose a simple and natural formalization of sequential decomposition, in which a task is decomposed into two sequential sub-tasks, with the first sub-task to be executed before the second sub-task is executed. These tasks are specified by means of input/output relations. We define and study decomposition problems, which is to decide whether a given specification can be sequentially decomposed. Our main result is that decomposition itself is a difficult computational problem. More specifically, we study decomposition problems in three settings: where the input task is specified explicitly, by means of Boolean circuits, and by means of automatic relations. We show that in the first setting decomposition is NP-complete, in the second setting it is NEXPTIME-complete, and in the third setting there is evidence to suggest that it is undecidable. Our results indicate that the intuitive idea of decomposition as a system-design approach requires further investigation. In particular, we show that adding a human to the loop by asking for a decomposition hint lowers the complexity of decomposition problems considerably.

    Volume: Volume 18, Issue 1
    Published on: March 3, 2022
    Accepted on: September 24, 2021
    Submitted on: March 5, 2019
    Keywords: Computer Science - Logic in Computer Science
    Fundings :
      Source : OpenAIRE Graph
    • Analysis, Verification, and Synthesis for Infinite-State Systems; Funder: European Commission; Code: 648701


    Consultation statistics

    This page has been seen 615 times.
    This article's PDF has been downloaded 499 times.