A complexity perspective on entailment of parameterized linear constraints (Articolo in rivista)

Type

• Prodotto della ricerca (Classe)
• Articolo in rivista (Classe)

Label

• A complexity perspective on entailment of parameterized linear constraints (Articolo in rivista) (literal)

Anno

• 2012-01-01T00:00:00+01:00 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#doi

• 10.1007/s10601-012-9127-x (literal)

Alternative label

• Eirinakis P., Ruggieri S., Subramani K., Wojciechowski P. (2012)
  A complexity perspective on entailment of parameterized linear constraints
  in Constraints (Dordrecht. Online); Springer, London (Regno Unito)
  (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#autori

• Eirinakis P., Ruggieri S., Subramani K., Wojciechowski P. (literal)

Pagina inizio

• 461 (literal)

Pagina fine

• 487 (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#url

• http://link.springer.com/article/10.1007%2Fs10601-012-9127-x (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroVolume

• 17 (literal)

Rivista

• Constraints (Rivista)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#numeroFascicolo

• 4 (literal)

Note

• ISI Web of Science (WOS) (literal)
• Scopu (literal)
• PuMa (literal)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#affiliazioni

• LDCSEE, West Virginia University, USA Computer Science Department, University of Pisa, Italy LDCSEE, West Virginia University, USA LDCSEE, West Virginia University, USA (literal)

Titolo

• A complexity perspective on entailment of parameterized linear constraints (literal)

Abstract

• Extending linear constraints by admitting parameters allows for more abstract problem modeling and reasoning. A lot of focus has been given to conducting research that demonstrates the usefulness of parameterized linear constraints and implementing tools that utilize their modeling strength. However, there is no approach that considers basic theoretical tools related to such constraints that allow for reasoning over them. Hence, in this paper we introduce satisf iability with respect to polyhedral sets and entailment for the class of parameterized linear constraints. In order to study the computational complexities of these problems, we relate them to classes of quantified linear implications. The problem of satisfiability with respect to polyhedral sets is then shown to be co-NP hard. The entailment problem is also shown to be co-NP hard in its general form. Nevertheless, we characterize some subclasses for which this problem is in P. Furthermore, we examine a weakening and a strengthening extension of the entailment problem. The weak entailment problem is proved to be NP complete. On the other hand, the strong entailment problem is shown to be co-NP hard. (literal)

Editore

• Springer (Editore)

Prodotto di

• Istituto di scienza e tecnologie dell'informazione \"Alessandro Faedo\" (ISTI) (Istituto)
• Knowledge Discovery and Data Mining (ICT.P08.009.003) (Modulo)

Autore CNR

• SALVATORE RUGGIERI (Persona)

Insieme di parole chiave

• Keywords of "A complexity perspective on entailment of parameterized linear constraints" (Insieme di parole chiave)

Incoming links:

Prodotto

• Istituto di scienza e tecnologie dell'informazione \"Alessandro Faedo\" (ISTI) (Istituto)
• Knowledge Discovery and Data Mining (ICT.P08.009.003) (Modulo)

Autore CNR di

• SALVATORE RUGGIERI (Persona)

Http://www.cnr.it/ontology/cnr/pubblicazioni.owl#rivistaDi

• Constraints (Rivista)

Editore di

• Springer (Editore)

Insieme di parole chiave di

• Keywords of "A complexity perspective on entailment of parameterized linear constraints" (Insieme di parole chiave)