کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7108651 | 1460622 | 2018 | 5 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
Complexity of deciding detectability in discrete event systems
ترجمه فارسی عنوان
پیچیدگی تصمیم گیری تشخیص در سیستم های رویداد گسسته
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
سیستم های رویداد گسسته، اتوماتای محدود تشخیص پیچیدگی،
موضوعات مرتبط
مهندسی و علوم پایه
سایر رشته های مهندسی
کنترل و سیستم های مهندسی
چکیده انگلیسی
Detectability of discrete event systems (DESs) is a question whether the current and subsequent states can be determined based on observations. Shu and Lin designed a polynomial-time algorithm to check strong (periodic) detectability and an exponential-time (polynomial-space) algorithm to check weak (periodic) detectability. Zhang showed that checking weak (periodic) detectability is PSpace-complete. This intractable complexity opens a question whether there are structurally simpler DESs for which the problem is tractable. In this paper, we show that it is not the case by considering DESs represented as deterministic finite automata without non-trivial cycles, which are structurally the simplest deadlock-free DESs. We show that even for such very simple DESs, checking weak (periodic) detectability remains intractable. On the contrary, we show that strong (periodic) detectability of DESs can be efficiently verified on a parallel computer.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Automatica - Volume 93, July 2018, Pages 257-261
Journal: Automatica - Volume 93, July 2018, Pages 257-261
نویسندگان
TomáÅ¡ Masopust,