NP-SPEC: An executable specification language for solving all problems in NP. A logic-based specification language, called NP-SPEC, is presented. The language is obtained by extending DATALOG through allowing a limited use of some second-order predicates of predefined form. NP-SPEC programs specify solutions to problems in a very abstract and concise way, and are executable. In the present prototype they are compiled to PROLOG code, which is run to construct outputs. Second-order predicates of suitable form allow to limit the size of search spaces in order to obtain reasonably efficient construction of problem solutions. NP-SPEC expressive power is precisely characterized as to express exactly the problems in the class NP. The specification of several combinatorial problems in NP-SPEC is shown, and the efficiency of the generated programs is evaluated.

References in zbMATH (referenced in 20 articles , 1 standard article )

Showing results 1 to 20 of 20.
Sorted by year (citations)

  1. Tasharrofi, Shahab; Ternovska, Eugenia: PBINT, a logic for modelling search problems involving arithmetic (2010)
  2. Deville, Yves; Dooms, Grégoire; Zampelli, Stéphane: Combining two structured domains for modeling various graph matching problems (2008)
  3. Frisch, Alan M.; Harvey, Warwick; Jefferson, Chris; Martínez-Hernández, Bernadette; Miguel, Ian: Essence: A constraint language for specifying combinatorial problems (2008)
  4. Mitchell, David G.; Ternovska, Eugenia: Expressive power and abstraction in Essence (2008)
  5. Samuel, Ken; Obrst, Leo; Stoutenberg, Suzette; Fox, Karen; Franklin, Paul; Johnson, Adrian; Laskey, Ken; Nichols, Deborah; Lopez, Steve; Peterson, Jason: Translating OWL and semantic web rules into Prolog: moving toward description logic programs (2008)
  6. Calimeri, Francesco; Ianni, Giovambattista: Template programs for disjunctive logic programming: an operational semantics (2006)
  7. Ramani, A.; Markov, I.L.; Sakallah, K.A.; Aloul, F.A.: Breaking instance-independent symmetries in exact graph coloring (2006)
  8. Ågren, Magnus; Flener, Pierre; Pearson, Justin: Incremental algorithms for local search from existential second-order logic (2005)
  9. Cadolia, Marco; Schaerf, Andrea: Compiling problem specifications into SAT (2005)
  10. Ramani, Arathi; Markov, Igor L.: Automatically exploiting symmetries in constraint programming (2005)
  11. Abdennadher, Slim; Frühwirth, Thom: Integration and optimization of rule-based constraint solvers (2004)
  12. Flener, Pierre; Pearson, Justin; Ågren, Magnus: Introducing ESRA, a relational language for modelling combinatorial problems (2004)
  13. Simons, Patrik; Niemelä, Ilkka; Soininen, Timo: Extending and implementing the stable model semantics (2002)
  14. Komondoor, Raghavan; Horwitz, Susan: Tool demonstration: finding duplicated code using program dependences (2001)
  15. Cadoli, Marco; Ianni, Giovambattista; Palopoli, Luigi; Schaerf, Andrea; Vasile, Domenico: NP-SPEC: An executable specification language for solving all problems in NP (2000)
  16. Eiter, Thomas; Faber, Wolfgang; Leone, Nicola; Pfeifer, Gerald: Declarative problem-solving using the DLV system (2000)
  17. Niemelä, Ilkka; Simons, Patrik: Extending the Smodels system with cardinality and weight constraints (2000)
  18. Marek, Victor W.; Truszczyński, Mirosław: Stable models and an alternative logic programming paradigm (1999)
  19. Niemelä, Ilkka: Logic programs with stable model semantics as a constraint programming paradigm (1999)
  20. Niemelä, Ilkka; Simons, Patrik; Soininen, Timo: Stable model semantics of weight constraint rules (1999)