Remarks on the difficulty of top-down supervisor synthesis
This paper shows that language based top-down supervisor synthesis of Ramadge-Wonham supervisory control theory is in general not feasible. We show this as a direct consequence of the undecidability result of Decomposable Subset problem (and its prefix closed version), which in turn is a corollary o...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Conference Paper |
| Language: | English |
| Published: |
2013
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/84647 http://hdl.handle.net/10220/11738 |
| _version_ | 1826117704401027072 |
|---|---|
| author | Lin, Liyong. Su, Rong. Stefanescu, Alin. |
| author2 | School of Electrical and Electronic Engineering |
| author_facet | School of Electrical and Electronic Engineering Lin, Liyong. Su, Rong. Stefanescu, Alin. |
| author_sort | Lin, Liyong. |
| collection | NTU |
| description | This paper shows that language based top-down supervisor synthesis of Ramadge-Wonham supervisory control theory is in general not feasible. We show this as a direct consequence of the undecidability result of Decomposable Subset problem (and its prefix closed version), which in turn is a corollary of the undecidability result of Trace Closed Subset problem. Essentially, it is in general not possible to decide in finite amount of time whether there exists a string in a regular language such that all those strings indistinguishable from it are contained in the same language. We bring these results to the attention of control community and investigate the decidability status of some other related problems. |
| first_indexed | 2024-10-01T04:31:58Z |
| format | Conference Paper |
| id | ntu-10356/84647 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T04:31:58Z |
| publishDate | 2013 |
| record_format | dspace |
| spelling | ntu-10356/846472020-03-07T13:24:44Z Remarks on the difficulty of top-down supervisor synthesis Lin, Liyong. Su, Rong. Stefanescu, Alin. School of Electrical and Electronic Engineering International Conference on Control Automation Robotics & Vision (12th : 2012 : Guangzhou, China) DRNTU::Engineering::Electrical and electronic engineering This paper shows that language based top-down supervisor synthesis of Ramadge-Wonham supervisory control theory is in general not feasible. We show this as a direct consequence of the undecidability result of Decomposable Subset problem (and its prefix closed version), which in turn is a corollary of the undecidability result of Trace Closed Subset problem. Essentially, it is in general not possible to decide in finite amount of time whether there exists a string in a regular language such that all those strings indistinguishable from it are contained in the same language. We bring these results to the attention of control community and investigate the decidability status of some other related problems. 2013-07-17T06:34:35Z 2019-12-06T15:48:54Z 2013-07-17T06:34:35Z 2019-12-06T15:48:54Z 2012 2012 Conference Paper Lin, L., Su, R., & Stefanescu, A. (2012). Remarks on the difficulty of top-down supervisor synthesis. 2012 12th International Conference on Control Automation Robotics & Vision (ICARCV), 270-275. https://hdl.handle.net/10356/84647 http://hdl.handle.net/10220/11738 10.1109/ICARCV.2012.6485170 en © 2012 IEEE. |
| spellingShingle | DRNTU::Engineering::Electrical and electronic engineering Lin, Liyong. Su, Rong. Stefanescu, Alin. Remarks on the difficulty of top-down supervisor synthesis |
| title | Remarks on the difficulty of top-down supervisor synthesis |
| title_full | Remarks on the difficulty of top-down supervisor synthesis |
| title_fullStr | Remarks on the difficulty of top-down supervisor synthesis |
| title_full_unstemmed | Remarks on the difficulty of top-down supervisor synthesis |
| title_short | Remarks on the difficulty of top-down supervisor synthesis |
| title_sort | remarks on the difficulty of top down supervisor synthesis |
| topic | DRNTU::Engineering::Electrical and electronic engineering |
| url | https://hdl.handle.net/10356/84647 http://hdl.handle.net/10220/11738 |
| work_keys_str_mv | AT linliyong remarksonthedifficultyoftopdownsupervisorsynthesis AT surong remarksonthedifficultyoftopdownsupervisorsynthesis AT stefanescualin remarksonthedifficultyoftopdownsupervisorsynthesis |