DROPS

Document

DOI: 10.4230/LIPIcs.ICLP.2010.64

Efficient Solving of Time-dependent Answer Set Programs

Authors: Timur Fayruzov, Jeroen Janssen, Dirk Vermeir, Chris Cornelis, and Martine De Cock

Published in: LIPIcs, Volume 7, Technical Communications of the 26th International Conference on Logic Programming (2010)

Abstract

Answer set programs with time predicates are useful to model systems whose properties depend on time, like for example gene regulatory networks. A state of such a system at time point t then corresponds to the literals of an answer set that are grounded with time constant t. An important task when modelling time-dependent systems is to find steady states from which the system's behaviour does not change anymore. This task is complicated by the fact that it is typically not known in advance at what time steps these steady states occur. A brute force approach of estimating a time upper bound tmax and grounding and solving the program w.r.t. that upper bound leads to a suboptimal solving time when the estimate is too low or too high. In this paper we propose a more efficient algorithm for solving Markovian programs, which are time-dependent programs for which the next state depends only on the previous state. Instead of solving these Markovian programs for a long time interval {0,...,tmax}, we successively find answer sets of parts of the grounded program. Our approach guarantees the discovery of all steady states and cycles while avoiding unnecessary extra work.

Cite as

Timur Fayruzov, Jeroen Janssen, Dirk Vermeir, Chris Cornelis, and Martine De Cock. Efficient Solving of Time-dependent Answer Set Programs. In Technical Communications of the 26th International Conference on Logic Programming. Leibniz International Proceedings in Informatics (LIPIcs), Volume 7, pp. 64-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fayruzov_et_al:LIPIcs.ICLP.2010.64,
  author =	{Fayruzov, Timur and Janssen, Jeroen and Vermeir, Dirk and Cornelis, Chris and De Cock, Martine},
  title =	{{Efficient Solving of Time-dependent Answer Set Programs}},
  booktitle =	{Technical Communications of the 26th International Conference on Logic Programming},
  pages =	{64--73},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-17-0},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{7},
  editor =	{Hermenegildo, Manuel and Schaub, Torsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICLP.2010.64},
  URN =		{urn:nbn:de:0030-drops-25841},
  doi =		{10.4230/LIPIcs.ICLP.2010.64},
  annote =	{Keywords: Answer set programming, time-dependent programs, gene regulation networks}
}

Search Results

Documents authored by Fayruzov, Timur

Efficient Solving of Time-dependent Answer Set Programs

Abstract

Cite as

Thanks for your feedback!

Could not send message