NP-SPEC

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.

Keywords for this software

Anything in here will be replaced on browsers that support the canvas element

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)