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. |

Abstract (English) |
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 Constraints Quantified linear implication Computational complexity Polynomial algorithm D.3.3 Language Constructs and Features |

1) Download Document PDF |

Open access Restricted Private