๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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

โœ Scribed by Stefania Costantini; Ottavio D'Antona; Alessandro Provetti

Publisher
Elsevier Science
Year
2002
Tongue
English
Weight
97 KB
Volume
84
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 Linke [Proc. IJCAI-2001IJCAI- , 2001, pp. 641-648], pp. 641-648]. 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.

๐Ÿ“œ SIMILAR VOLUMES

On the equivalence of semantics for norm
On the equivalence of semantics for normal logic programs
โœ Jia-Huai You; Li Yan Yuan ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 699 KB

Despite the frequent comment that there is no general agreement on the semantics of logic programs, this paper shows that a number of independently proposed extensions to the stable model semantics coincide: the regular model semantics proposed by You and Yuan, the partial stable model semantics by

Program logic and equivalence in the pre
Program logic and equivalence in the presence of garbage collection
โœ Cristiano Calcagno; Peter O'Hearn; Richard Bornat ๐Ÿ“‚ Article ๐Ÿ“… 2003 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 220 KB

It is generally thought that reasoning about programs in memory safe, garbage collected languages is much easier than in languages where the programmer has more explicit control over memory. Paradoxically, existing program logics are based on a low-level view of storage that is sensitive to the pres

On the Equivalence of Recursive and Nonr
On the Equivalence of Recursive and Nonrecursive Datalog Programs
โœ Surajit Chaudhuri; Moshe Y Vardi ๐Ÿ“‚ Article ๐Ÿ“… 1997 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 591 KB

We study the problem of determining whether a given recursive Datalog program is equivalent to a given nonrecursive Datalog program. Since nonrecursive Datalog programs are equivalent to unions of conjunctive queries, we study also the problem of determining whether a given recursive Datalog program

The Logical Representation of Bincode an
The Logical Representation of Bincode and its Applications in Manipulating Binary Images
โœ Jung-Gen Wu; Kuo-Liang Chung ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 275 KB

The Logical Representation of Bincode and its Applications in Manipulating Binary Images E ncoding digital binary images by using bincodes is very simple and storage-saving. Many ecient algorithms have been developed for manipulating images represented by bincodes. Among these algorithms, however, s