Skip to Content

TU Wien Fakultät für Informatik DBAI Database and Artificial Intelligence Group
Top-level Navigation: Current-level Navigation:

Path: DBAI > Research > Projects > DYNASP Project > dynASP

Tools: Print


dynASP - A Dynamic Programming-based Answer Set Programming Solver

A system for propositional Answer Set Programming that is based on dynamic programming and tree decompositions. dynASP is developed within the project "Dynamic Programming and Answer Set Programming".

Contents


News

Webpage online

05.03.2012

The separate dynASP software webpage is now online.

Top

Team

People involved in the development of dynASP: Top

About

dynASP is a solver for Answer Set Programming (ASP) programs. In general, solving ground logic programs is intractable. Standard-ASP solvers use techniques stemming from SAT or CSP, where intractability has been successfully tackled in practice. dynASP relies on a more theoretical approach to deal with intractable problems, namely parameterized complexity theory where the idea is to bind a certain parameter to a constant in order to obtain tractable fragments for the problems under consideration. One important parameter is treewidth, which measures the 'tree-likeliness' of a graph. The treewidth is defined on tree decompositions which in turn can be used by dynamic programming (DP) methods to solve the considered problem.

Internally, dynASP finds a tree decomposition for a given program and evaluates it based on a dynamic programming method. This entire process is hidden from the user. In fact, dynASP presents itself like a standard ASP solver. The overall goal is to improve the performance of ASP solving for logic programs with low treewidth.

Top

Usage

dynASP can be called with the following parameters:

Usage: 
./dynasp [-b] [-t] [-s <seed>] [-f <file>] [-a <alg>] [-o <output>]
-b	   print verbose and benchmark information
-t	   perform only tree decomposition step
-s seed	   initialize random number generator with <seed>.
-f file	   the file to read from
-a alg	   algorithm, one of {sat, minsat, asp (default), hcfasp, hcf}
-o output  output type, one of {enum (default), count, yesno}
Top

Download

The current version of the dynASP tool is available in binary, compiled form:

Version 1.0 (dynASP)

Top

Additional Software

Logic Program Optimization

The program lpopt allows for preprocessing complex non-ground rules for answer set programming (ASP) in such a way that the grounding of such a rule remains small. For a detailed documentation see [5,6].

Usage:
./lpopt < infile > outfile

Version 1.0 (lpopt + dynASP)

Top

Related Webpages

Top

Selected Publications

2012

[7] Evaluating Tree-Decomposition Based Algorithms for Answer Set Programming
Michael Morak, Nysret Musliu, Reinhard Pichler, Stefan Rümmele, Stefan Woltran
In Proceedings of the 6th International Conference on Learning and Intelligent Optimization (LION 2012), Pages 130-144, 2012 (link)
[6] Preprocessing of Complex Non-Ground Rules in Answer Set Programming
Michael Morak, Stefan Woltran
In Technical Communications of the 28th International Conference on Logic Programming (ICLP 2012), Pages 247-258, 2012 (link)

2011

[5] Preprocessing of Complex Non-Ground Rules in Answer Set Programming
Michael Morak, Stefan Woltran
Technical Report DBAI-TR-2011-72, Database and Artificial Intelligence Group,
Vienna University of Technology (link)
[4] Evaluating Tree-Decomposition Based Algorithms for Answer Set Programming
Michael Morak, Nysret Musliu, Reinhard Pichler, Stefan Rümmele, Stefan Woltran
Technical Report DBAI-TR-2011-73, Database and Artificial Intelligence Group,
Vienna University of Technology (link)
[3] A New Tree-Decomposition Based Algorithm for Answer Set Programming
Michael Morak, Nysret Musliu, Reinhard Pichler, Stefan Rümmele, Stefan Woltran
In Proceedings of the 23rd IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2011), Pages 916-918, 2011 (link)
[2] dynASP - A Dynamic-Programming Based Answer Set Programming Solver
Michael Morak, Master's Thesis, Vienna University of Technology, published January 2011 (thesis at obv, direct link)

2010

[1] A Dynamic-Programming Based ASP-Solver
Michael Morak, Reinhard Pichler, Stefan Rümmele, Stefan Woltran
In Proceedings of the 12th European Conference on Logics in Artificial Intelligence (JELIA 2010), LNCS, Volume 6341, Pages 369-372, 2010 (paper at SpringerLink)
Top
Last updated: 2012-03-05 18:11

Home / Kontakt / Webmaster / Offenlegung gemäß § 25 Mediengesetz: Inhaber der Website ist das Institut für Logic and Computation an der Technischen Universität Wien, 1040 Wien. Die TU Wien distanziert sich von den Inhalten aller extern gelinkten Seiten und übernimmt diesbezüglich keine Haftung. Disclaimer / Datenschutzerklärung