2 Search Results for "Morak, Michael"

Document
DOI: 10.4230/LIPIcs.IPEC.2017.17
DynASP2.5: Dynamic Programming on Tree Decompositions in Action

Authors: Johannes K. Fichte, Markus Hecher, Michael Morak, and Stefan Woltran

Published in: LIPIcs, Volume 89, 12th International Symposium on Parameterized and Exact Computation (IPEC 2017)

Abstract
Efficient, exact parameterized algorithms are a vibrant theoretical research area. Recent solving competitions, such as the PACE challenge, show that there is also increasing practical interest in the parameterized algorithms community. An important research question is whether such algorithms can be built to efficiently solve specific problems in practice, that is, to be competitive with established solving systems. In this paper, we consider Answer Set Programming (ASP), a logic-based declarative modeling and problem solving framework. State-of-the-art ASP solvers generally rely on SAT-based algorithms. In addition, DynASP2, an ASP solver that is based on a classical dynamic programming on tree decompositions, has recently been introduced. DynASP2 outperforms modern ASP solvers when the goal is to count the number of solutions of programs that have small treewidth. However, for quickly finding one solutions, DynASP2 proved uncompetitive. In this paper, we present a new algorithm and implementation, called DynASP2.5, that shows competitive behavior compared to state-of-the-art ASP solvers on problems like Steiner tree for low-treewidth graphs, even when the task is to find just one solution. Our implementation is based on a novel approach that we call multi-pass dynamic programming.
Cite as

Johannes K. Fichte, Markus Hecher, Michael Morak, and Stefan Woltran. DynASP2.5: Dynamic Programming on Tree Decompositions in Action. In 12th International Symposium on Parameterized and Exact Computation (IPEC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 89, pp. 17:1-17:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fichte_et_al:LIPIcs.IPEC.2017.17,
  author =	{Fichte, Johannes K. and Hecher, Markus and Morak, Michael and Woltran, Stefan},
  title =	{{DynASP2.5: Dynamic Programming on Tree Decompositions in Action}},
  booktitle =	{12th International Symposium on Parameterized and Exact Computation (IPEC 2017)},
  pages =	{17:1--17:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-051-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{89},
  editor =	{Lokshtanov, Daniel and Nishimura, Naomi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2017.17},
  URN =		{urn:nbn:de:0030-drops-85739},
  doi =		{10.4230/LIPIcs.IPEC.2017.17},
  annote =	{Keywords: Parameterized algorithms, Fixed-parameter linear time, Tree decompositions, Multi-pass dynamic programming}
}
Document
DOI: 10.4230/LIPIcs.ICLP.2012.247
Preprocessing of Complex Non-Ground Rules in Answer Set Programming

Authors: Michael Morak and Stefan Woltran

Published in: LIPIcs, Volume 17, Technical Communications of the 28th International Conference on Logic Programming (ICLP'12) (2012)

Abstract
In this paper we present a novel method for preprocessing complex non-ground rules in answer set programming (ASP). Using a well-known result from the area of conjunctive query evaluation, we apply hypertree decomposition to ASP rules in order to make the structure of rules more explicit to grounders. In particular, the decomposition of rules reduces the number of variables per rule, while on the other hand, additional predicates are required to link the decomposed rules together. As we show in this paper, this technique can reduce the size of the grounding significantly and thus improves the performance of ASP systems in certain cases. Using a prototype implementation and the benchmark suites of the Answer Set Programming Competition 2011, we perform extensive tests of our decomposition approach that clearly show the improvements in grounding time and size.
Cite as

Michael Morak and Stefan Woltran. Preprocessing of Complex Non-Ground Rules in Answer Set Programming. In Technical Communications of the 28th International Conference on Logic Programming (ICLP'12). Leibniz International Proceedings in Informatics (LIPIcs), Volume 17, pp. 247-258, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{morak_et_al:LIPIcs.ICLP.2012.247,
  author =	{Morak, Michael and Woltran, Stefan},
  title =	{{Preprocessing of Complex Non-Ground Rules in Answer Set Programming}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{247--258},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Dovier, Agostino and Santos Costa, V{\'\i}tor},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2012.247},
  URN =		{urn:nbn:de:0030-drops-36263},
  doi =		{10.4230/LIPIcs.ICLP.2012.247},
  annote =	{Keywords: answer set programming, hypertree decomposition, preprocessing}
}
  • Refine by Author
  • 2 Morak, Michael
  • 2 Woltran, Stefan
  • 1 Fichte, Johannes K.
  • 1 Hecher, Markus

  • Refine by Classification

  • Refine by Keyword
  • 1 Fixed-parameter linear time
  • 1 Multi-pass dynamic programming
  • 1 Parameterized algorithms
  • 1 Tree decompositions
  • 1 answer set programming
  • Show More...

  • Refine by Type
  • 2 document

  • Refine by Publication Year
  • 1 2012
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact