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
References in zbMATH (referenced in 20 articles , 1 standard article )
Showing results 1 to 20 of 20.
Sorted by year (- Tasharrofi, Shahab; Ternovska, Eugenia: PBINT, a logic for modelling search problems involving arithmetic (2010)
- Deville, Yves; Dooms, Grégoire; Zampelli, Stéphane: Combining two structured domains for modeling various graph matching problems (2008)
- Frisch, Alan M.; Harvey, Warwick; Jefferson, Chris; Martínez-Hernández, Bernadette; Miguel, Ian: Essence: A constraint language for specifying combinatorial problems (2008)
- Mitchell, David G.; Ternovska, Eugenia: Expressive power and abstraction in Essence (2008)
- 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)
- Calimeri, Francesco; Ianni, Giovambattista: Template programs for disjunctive logic programming: an operational semantics (2006)
- Ramani, A.; Markov, I.L.; Sakallah, K.A.; Aloul, F.A.: Breaking instance-independent symmetries in exact graph coloring (2006)
- Ågren, Magnus; Flener, Pierre; Pearson, Justin: Incremental algorithms for local search from existential second-order logic (2005)
- Cadolia, Marco; Schaerf, Andrea: Compiling problem specifications into SAT (2005)
- Ramani, Arathi; Markov, Igor L.: Automatically exploiting symmetries in constraint programming (2005)
- Abdennadher, Slim; Frühwirth, Thom: Integration and optimization of rule-based constraint solvers (2004)
- Flener, Pierre; Pearson, Justin; Ågren, Magnus: Introducing ESRA, a relational language for modelling combinatorial problems (2004)
- Simons, Patrik; Niemelä, Ilkka; Soininen, Timo: Extending and implementing the stable model semantics (2002)
- Komondoor, Raghavan; Horwitz, Susan: Tool demonstration: finding duplicated code using program dependences (2001)
- Cadoli, Marco; Ianni, Giovambattista; Palopoli, Luigi; Schaerf, Andrea; Vasile, Domenico: NP-SPEC: An executable specification language for solving all problems in NP (2000)
- Eiter, Thomas; Faber, Wolfgang; Leone, Nicola; Pfeifer, Gerald: Declarative problem-solving using the DLV system (2000)
- Niemelä, Ilkka; Simons, Patrik: Extending the Smodels system with cardinality and weight constraints (2000)
- Marek, Victor W.; Truszczyński, Mirosław: Stable models and an alternative logic programming paradigm (1999)
- Niemelä, Ilkka: Logic programs with stable model semantics as a constraint programming paradigm (1999)
- Niemelä, Ilkka; Simons, Patrik; Soininen, Timo: Stable model semantics of weight constraint rules (1999)