On Convexity of Right-Closed Integral Sets

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

[thumbnail of Salimi2012016BJMCS30348.pdf] Text
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

Actions (login required)

View Item
View Item