Istituto di Scienza e Tecnologie dell'Informazione     
Ruggieri S. Deciding membership in a class of polyhedra. In: ECAI 2012 - 20th European Conference on Artificial Intelligence (Montpellier, Francia, 27-31 agosto 2012). Proceedings, pp. 702 - 707. Luc De Raedt et al.. (Frontiers in Artificial Intelligence and Applications, vol. 242). IOS, 2012.
Parameterized linear systems allow for modelling and reasoning over classes of polyhedra. Collections of squares, rectangles, polytopes, and so on can readily be defined by means of linear systems with parameters in constant terms. In this paper, we consider the membership problem of deciding whether a given polyhedron belongs to the class defined by a parameterized linear system. As an example, we are interested in questions such as: "does a given polytope belong to the class of hypercubes?" We show that the membership problem is NP-complete, even when restricting to the 2-dimensional plane. Despite the negative result, the constructive proof allows us to devise a concise decision procedure using constraint logic programming over the reals, namely CLP(R), which searches for a characterization of all instances of a parameterized system that are equivalent to a given polyhedron.
URL: http://ebooks.iospress.nl/publication/7056
DOI: 10.3233/978-1-61499-098-7-702
Subject Entailment
Parameterized linear constraint
Quantified linear program
Quantified linear implication
Computational complexity
Polynomial algorithm
D.3.3 Language Constructs and Features

Icona documento 1) Download Document PDF

Icona documento Open access Icona documento Restricted Icona documento Private


Per ulteriori informazioni, contattare: Librarian http://puma.isti.cnr.it

Valid HTML 4.0 Transitional