License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICLP.2012.425
URN: urn:nbn:de:0030-drops-36420
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3642/
Go to the corresponding LIPIcs Volume Portal

Filardo, Nathaniel Wesley ; Eisner, Jason

A Flexible Solver for Finite Arithmetic Circuits

pdf-format:
40.pdf (0.6 MB)

Abstract

Arithmetic circuits arise in the context of weighted logic programming languages, such as Datalog with aggregation, or Dyna. A weighted logic program defines a generalized arithmetic circuit—the weighted version of a proof forest, with nodes having arbitrary rather than boolean values. In this paper, we focus on finite circuits. We present a flexible algorithm for efficiently querying
node values as they change under updates to the circuit's inputs. Unlike traditional algorithms, ours is agnostic about which nodes are tabled (materialized), and can vary smoothly between the traditional strategies of forward and backward chaining. Our algorithm is designed to admit future generalizations, including cyclic and infinite circuits and propagation of delta updates.

BibTeX - Entry

@InProceedings{filardo_et_al:LIPIcs:2012:3642,
  author =	{Nathaniel Wesley Filardo and Jason Eisner},
  title =	{{A Flexible Solver for Finite Arithmetic Circuits}},
  booktitle =	{Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)},
  pages =	{425--438},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-43-9},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{17},
  editor =	{Agostino Dovier and V{\'i}tor Santos Costa},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3642},
  URN =		{urn:nbn:de:0030-drops-36420},
  doi =		{10.4230/LIPIcs.ICLP.2012.425},
  annote =	{Keywords: arithmetic circuits, memoization, view maintenance, logic programming}
}

Keywords: arithmetic circuits, memoization, view maintenance, logic programming
Collection: Technical Communications of the 28th International Conference on Logic Programming (ICLP'12)
Issue Date: 2012
Date of publication: 05.09.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI