Salimi, E and Sreenivas, R (2017) On Convexity of Right-Closed Integral Sets. British Journal of Mathematics & Computer Science, 20 (1). pp. 1-11. ISSN 22310851
Salimi2012016BJMCS30348.pdf - Published Version
Download (452kB)
Abstract
Let N denote the set of non-negative integers. A set of non-negative, n-dimensional integral vectors, M⊂Nn, is said to be right-closed, if ((x ∈ M) ∧ (y ≥ x) ∧ (y ∈Nn)) ⇒ (y ∈ M). In this paper, we present a polynomial time algorithm for testing the convexity of a right-closed set of integral vectors, when the dimension n is xed. Right-closed set of integral vectors are innitely large, by denition. We compute the convex-hull of an appropriately-dened nite subset of this innite-set of vectors. We then check if a stylized Linear Program has a non-zero optimal value for a special collection of facets of this convex-hull. 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. This observation plays an important role in the ecient synthesis of Supervisory Policies that avoid Livelocks in Discrete-Event/Discrete-State Systems.
Item Type: | Article |
---|---|
Subjects: | Open Research Librarians > Computer Science |
Depositing User: | Unnamed user with email support@open.researchlibrarians.com |
Date Deposited: | 15 May 2023 07:00 |
Last Modified: | 05 Feb 2024 04:51 |
URI: | http://stm.e4journal.com/id/eprint/898 |