1,721,021 research outputs found
On the Equivalence and Range of Applicability of Graph-based Representations of Logic Programs
No full textLogic 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 \cite{Lin01}. 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 as expressive
Reification, Reflection and Ontological Promiscuity in Temporal Reasoning
No full textGuarino N., Poli R. (editors
Normal forms for answer sets programming
No full textNormal forms for logic programs under stable/answer set semantics are introduced. We argue that these forms can simplify the study of program properties, mainly consistency. The first normal form, called the kernel of the program, is useful for studying existence and number of answer sets. A kernel program is composed of the atoms which are undefined in the Well-founded semantics, which are those that directly affect the existence of answer sets. The body of rules is composed of negative literals only. Thus, the kernel form tends to be significantly more compact than other formulations. Also, it is possible to check consistency of kernel programs in terms of colorings of the Extended Dependency Graph program representation which we previously developed. The second normal form is called 3-kernel. A 3-kernel program is composed of the atoms which are undefined in the Well-founded semantics. Rules in 3-kernel programs have at most two conditions, and each rule either belongs to a cycle, or defines a connection between cycles. 3-kernel programs may have positive conditions. The 3-kernel normal form is very useful for the static analysis of program consistency, i.e. the syntactic characterization of existence of answer sets. This result can be obtained thanks to a novel graph-like representation of programs, called Cycle Graph which presented in the companion article Costantini (2004b)
A Heuristic Approach to Proposal-Based Negotiation with Applications in Fashion Supply Chain Management
No full textWe reconsider and improve the formal, executable framework for automated multi-issue negotiation between two autonomous competitive software agents proposed by Cadoli, who introduced a proposal-based process of negotiation, which he modeled as a distributed constraint satisfaction problem (DCSP). His model is based on the view of negotiation spaces, representing the admissible values of the goods involved in the process, as convex regions: i.e., all points included in each agent’s individual region (or “area”) correspond to acceptable agreements. However, in order to speed-up the negotiation process and guarantee convergence, there was the assumption/limitation that, for one of the two agents, only vertices of individual negotiation space were considered as admissible offers. Therefore, only those vertices included in the intersection of the two areas where actual potential agreements. In this article, we present and assess experimentally an extension to Cadoli’s approach where, in particular, interaction is no longer vertex-based, or at least not necessarily. I.e., we allow both agents to potentially make offers that are an internal point of its negotiation space and then try to approach the opponent’s counter-proposal “step-by-step”. The algorithm presented here overcomes some problems of the original one, such as the asymmetry among the parties and the limitation to polyhedral negotiation areas. Also, the extension can be usefully integrated to Cadoli’s framework, thus obtaining a new algorithm that may be effective in many practical cases by introducing “local search,”, for instance around
“best-preferred” vertices. We present and discuss a number of experiments, aimed at assessing how parameters influence the performance of the algorithm, and they relate to each other. We report that the extended approach works properly, and in several cases yields a better solution than the original proposal, while the interaction complexity remains acceptable. We discuss its applicability in relevant application fields, such as for instance supply chain management in the fashion industry, which is a field of growing importance in economy and e-commerce
Conflict, Consistency and Truth-Dependencies in Graph Representations of Answer Set Logic Programs
No full textIn this paper we propose a formalization of the features that a
graph representation of logic programs under the answers set semantics should in our opinion exhibit
in order to be a satisfactory and useful representation formalism.
We introduce a concept of isomorphism between a program and the
corresponding graph. Isomorphic graph representations guarantee that
the graph corresponding to a program is unique, and that the
original program can be reconstructed from the graph. We prove that
the isomorphism is possible only if a graph representation formalism
is able to distinguish the cycles occurring in the program, and the
different connections among them. We consider and discuss some of the existing
graph representations. We argue that understanding cycles
and their connections is a key point for understanding program
behavior and for checking consistency, for being then able to
create, debug and combine good programs, and for developing program
analysis techniques
- …
