2026-09-20T13:03:22Z https://www.ideals.illinois.edu/oai-pmh

oai:www.ideals.illinois.edu:2142/88056 2023-07-11 col_2142_5131 col_2142_16359 com_2142_5130 com_2142_16358 com_2142_234

Sreenivas, Ramavarapu S. Sreenivas, Ramavarapu S. Basar, Tamer Nagi, Rakesh Beck, Carolyn L. Kiyavash, Negar Salimi, Ehsan 2015-09-29T20:38:30Z 2015-09-29T20:38:30Z 2015-08 2015-07-16 2015-8 A set of n-dimensional integral vectors, Nn, is said to be right-closed if for any x 2 , any vector y x also belongs to it. An integral-set Nn is convex if and only if there is a convex set C Rn such that = Int(C), where Int( ) denotes the integral points in the set argument. In this dissertation, we show that the problem of verifying convexity of a right-closed set is decidable. Following this, we present a polynomial time, LP-based algorithm, for verifying the convexity of a right-closed set of integral vectors, when the dimension n is xed. This result is to be viewed against the backdrop of the fact that checking the convexity of a real-valued, geometric set can only be accomplished in an approximate sense; and, the fact that most algorithms involving sets of real-valued vectors do not apply directly to their integral counterparts. Also, we discuss a grid-search based algorithm for verifying the convexity of such a set, although not a polynomial time procedure, it is a method that veri es the convexity of right-closed sets in a reasonable time complexity. On the application side, right-closed sets feature in the synthesis of Liveness Enforcing Supervisory Policies (LESPs) for a large family of Petri Nets (PNs). For any PN structure N from this family, the set of initial markings, (N), for which there is a LESP, is right-closed. A LESP determines the transitions of a PN that are to be permitted to re at any marking in such a manner that, irrespective of the past, every transition can be red at some marking in the future. A system that is modeled by a live PN does not experience livelocks, which serves as the motivation for investigating implementation paradigms for LESPs in practice. If a transition is prevented from ring at a marking by a LESP, and all LESPs, irrespective of the implementation-paradigm that is chosen, prescribe the same control for the marking, then it is a minimally restrictive LESP. It is possible to synthesize the minimally restrictive LESP for any instance N of the aforementioned family that uses the right-closed set of markings (N). The literature also contains an implementation paradigm called invariant-based monitors for liveness enforcement in PNs. This paradigm is popular due to the fact that the resulting supervisor can be directly incorporated into the semantics of the PN model of the controlled system. In this work, we show that there is an invariant-based monitor that is equivalent to the minimally restrictive LESP that uses the right-closed set (N) if and only if (N) is convex. This result serves as the motivation behind exploring the convexity of right-closed sets. Submission original under an indefinite embargo labeled 'Open Access'. The submission was exported from vireo on 2015-09-29 without embargo terms The student, Ehsan Salimi, accepted the attached license on 2015-07-15 at 16:23. The student, Ehsan Salimi, submitted this Dissertation for approval on 2015-07-15 at 16:38. This Dissertation was approved for publication on 2015-07-16 at 10:22. DSpace SAF Submission Ingestion Package generated from Vireo submission #8482 on 2015-09-29 at 13:22:54 Made available in DSpace on 2015-09-29T20:38:30Z (GMT). No. of bitstreams: 2 SALIMI-DISSERTATION-2015.pdf: 1474659 bytes, checksum: 8be156baa2487e27493a045c6b42cbc7 (MD5) LICENSE.txt: 4209 bytes, checksum: d0ff73087c4b9f7f0e6df2bacbb12e6c (MD5) Previous issue date: 2015-07-16 application/pdf http://hdl.handle.net/2142/88056 en Copyright 2015 Ehsan Salimi Right-closed set convexity integer convexity polyhedral theory Petri Nets Liveness On the convexity of right-closed sets and its application to liveness enforcement in Petri Nets text text Industrial&Enterprise Sys Eng Industrial Engineering University of Illinois at Urbana-Champaign Dissertation Ph.D.