Sequential relational decomposition

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 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.

اللغة الأصليةالإنجليزيّة
عنوان منشور المضيفProceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018
ناشرInstitute of Electrical and Electronics Engineers Inc.
عدد الصفحات10
رقم المعيار الدولي للكتب (الإلكتروني)9781450355834, 9781450355834
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 9 يوليو 2018
منشور خارجيًانعم
الحدث33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018 - Oxford, بريطانيا
المدة: ٩ يوليو ٢٠١٨١٢ يوليو ٢٠١٨

سلسلة المنشورات

الاسمProceedings - Symposium on Logic in Computer Science
رقم المعيار الدولي للدوريات (المطبوع)1043-6871


!!Conference33rd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2018

ملاحظة ببليوغرافية

Publisher Copyright:
© 2018 ACM.


أدرس بدقة موضوعات البحث “Sequential relational decomposition'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا