Sequential relational decomposition
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 w...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
Association for Computing Machinery
2018
|
| _version_ | 1797078437956943872 |
|---|---|
| author | Fried, D Legay, A Ouaknine, J Vardi, M |
| author_facet | Fried, D Legay, A Ouaknine, J Vardi, M |
| author_sort | Fried, D |
| collection | OXFORD |
| description | 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 out 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 human to the loop by asking for a decomposition hint lowers the complexity of decomposition problems considerably. |
| first_indexed | 2024-03-07T00:31:49Z |
| format | Conference item |
| id | oxford-uuid:80106596-3753-441d-bc97-86efbe0bdb24 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T00:31:49Z |
| publishDate | 2018 |
| publisher | Association for Computing Machinery |
| record_format | dspace |
| spelling | oxford-uuid:80106596-3753-441d-bc97-86efbe0bdb242022-03-26T21:20:56ZSequential relational decompositionConference itemhttp://purl.org/coar/resource_type/c_5794uuid:80106596-3753-441d-bc97-86efbe0bdb24Symplectic Elements at OxfordAssociation for Computing Machinery2018Fried, DLegay, AOuaknine, JVardi, MThe 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 out 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 human to the loop by asking for a decomposition hint lowers the complexity of decomposition problems considerably. |
| spellingShingle | Fried, D Legay, A Ouaknine, J Vardi, M Sequential relational decomposition |
| title | Sequential relational decomposition |
| title_full | Sequential relational decomposition |
| title_fullStr | Sequential relational decomposition |
| title_full_unstemmed | Sequential relational decomposition |
| title_short | Sequential relational decomposition |
| title_sort | sequential relational decomposition |
| work_keys_str_mv | AT friedd sequentialrelationaldecomposition AT legaya sequentialrelationaldecomposition AT ouakninej sequentialrelationaldecomposition AT vardim sequentialrelationaldecomposition |