Skip to content
Research Article Open access CC BY 4.0

On Convexity of Right-Closed Integral Sets

E. Salimi, R.S. Sreenivas

Journal of Advances in Mathematics and Computer Science · pp. 1–11 · Published 10 Dec 2016

10.9734/BJMCS/2017/30348

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.

Convexity right-closed sets computational geometry

References (9)

  1. 1 Convex Optimization [DOI]
  2. 2 Integer Points in Polyhedra [DOI]
  3. 3 The residue of vector sets with applications to decidability problems in petri nets [DOI]
  4. 4 On the Existence of Supervisory Policies That Enforce Liveness in Partially Controlled Free-Choice Petri Nets [DOI]
  5. 5 On a Decidable Class of Partially Controlled Petri Nets With Liveness Enforcing Supervisory Policies [DOI]
  6. 6 On Deciding the Existence of a Liveness Enforcing Supervisory Policy in a Class of Partially Controlled General Free-Choice Petri Nets [DOI]
  7. 7 A software tool for the automatic synthesis of minimally restrictive liveness enforcing supervisory policies for a class of general Petri net models of manufacturing- and service-systems [DOI]
  8. 8 On Invariant-Based Monitors That Enforce Liveness in a Class of Partially Controlled General Petri Nets [DOI]
  9. 9 Computing the continuous discretely: integer-point enumeration in polyhedra [DOI]

Cited by 0

No indexed citations yet.

Related research

Article metrics

Real usage data collected on this platform.

14

Page views

0

PDF downloads

1

Outbound clicks

0

Citations

Views over time

Views by country

Approximate, from request IP at view time — not citizenship or institution. Countries with fewer than 5 views are grouped as "Other".

Traffic sources

Referring site, by host.

Views and downloads exclude known bots/crawlers. Citations combines this platform's own DOI-resolved index with each external source's own reported total — see Cited by above for individually listed citing works. Last refreshed 0 seconds ago.