On the equivalence and range of applicability of graph-based representations of logic programs.

DOI10.1016/S0020-0190(02)00290-9MaRDI QIDQ1853147zbMATH OpenOpenAlexWikidataFDO

Authors Stefania Costantini, Ottavio M. D'Antona, Alessandro Provetti

Publication date 21 January 2003

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0020-0190(02)00290-9

zbMATH Keywords

Answer Set ProgrammingGraph algorithmsLogic Programming

Mathematics Subject Classification ID

Logic programming (68N17) Graph theory (including graph drawing) in computer science (68R10)

Review text

Logic programs under Answer Sets semantics can be studied, and actual computation can be carried out, by means of representing them by directed graphs. Several reductions of logic programs to directed graphs are now available. We compare our proposed representation, called extended dependency graph, to the block graph representation recently defined by \textit{Linke} [Proc. IJCAI-2001, 641--648 (2001)]. On the relevant fragment of well-founded irreducible programs, extended dependency and block graph turns out to be isomorphic. So, we argue that graph representation of general logic programs should be abandoned in favor of graph representation of well-founded irreducible programs, which are more concise, more uniform in structure while being equally expressive.

Recommendations

• Logic for Programming, Artificial Intelligence, and Reasoning
• Graph theoretical structures in logic programs and default theories
• Graph properties for normal logic programs
• scientific article; zbMATH DE number 177436
• On computing logic programs

Cites work

• Contributions to the stable model semantics of logic programs with negation
• Extremal problems in logic programming and stable model computation
• Graph theoretical structures in logic programs and default theories
• scientific article; zbMATH DE number 25190 (Why is no real title available?)
• scientific article; zbMATH DE number 1368933 (Why is no real title available?)
• scientific article; zbMATH DE number 1884391 (Why is no real title available?)
• Normal forms for answer sets programming
• On the Expressibility of Stable Logic Programming
• The expressive powers of the logic programming semantics
• The well-founded semantics for general logic programs
• Transformation-based bottom-up computation of the well-founded model

Cited in

(5)

• Justifications for logic programs under answer set semantics
• On the Expressive Power of Graph Logic
• Some (in)translatability results for normal logic programs and propositional theories
• Answering the ``why in answer set programming -- a survey of explanation approaches
• Logic for Programming, Artificial Intelligence, and Reasoning

This page was built for publication: On the equivalence and range of applicability of graph-based representations of logic programs.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1853147)